L'énoncé
Répondez aux questions suivantes
Question 1
Calculer le PGCD de 69 et 15.
$69 = 15 \times 4 +9$
$15 = 9 \times 1 +6$
$9 = 6 \times 1 + 3$
$6 = 3 \times 2 + 0$
Le PGCD de 69 et 15 est 3
Utilisez l'algorithme d'Euclide
Question 2
Calculez le PGCD de 72 et 39
$72 = 39\times 1 + 33$
$39 = 33 \times 1 + 6$
$33 = 6 \times 5 +3$
$6 = 3 \times 2 +0$
Le PGCD de 72 et 39 est 3
Utilisez l'algorithme d'Euclide
Question 3
Calculez le PGCD de 91 et 22
$91 = 22 \times 4 + 9$
$22 = 9 \times 2 + 4$
$9 = 4 \times 2 +1$
$ 4 = 1 \times 4 + 0$
Le PGCD de 91 et 22 est 1.
Question 4
Soit $n \in \mathbb{N}$ Démontrez que PGCD(n,n+1) = 1
En écrivant l'algorithme d'Euclide :
$n+1 = n \times 1 +1$
$n = 1 \times n + 0$
Le PGCD de n et n+1 est donc 1.
Utilisez l'algorithme d'Euclide.
Question 5
Ecrivez l'algorithme d'Euclide en Python
def euclide(a,b):
x = max(a,b)
y = min(a,b)
quotient = x//y
reste = x%y
while reste !=0 :
x = quotient
y = reste
quotient = x//y
reste = x%y
return resteUtilisez une boucle while qui tourne tant que le reste est non nul.
Si l'on considère la division euclidienne de a par b, le quotient s'écrit a//b et le reste a%b