Cours Stage - PGCD, algorithme d'Euclide

Exercice : PGCD de deux entiers et algorithme d'Euclide.

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 reste

Utilisez 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