Recherche du pgcd de deux nombres par un algorithme

algorithme :	mot savant pour désigner une technique qui permet de trouver un résultat en répétant des actions et des tests.

Le plus connu des algorithmes est celui qu'on utilise pour poser une division euclidienne à la main (mais personne ne parle d'algorithme) et on utilisait aussi un algorithme pour extraire une racine carrée à la main.

L'algorithme le plus célèbre est l'algorithme d'Euclide : il permet d'obtenir le plus grand commun diviseur à deux entiers naturels non nuls (reste à savoir si Euclide y est pour quelque chose).

Un autre algorithme (dit "des différences") permet d'obtenir le même résultat. A noter que les auteurs du livre de maths Triangle de 3e les prennent l'un pour l'autre (ce qui prouve qu'il ne faut pas trop se fier aux manuels)

1) Si un nombre est un diviseur commun à deux entiers naturels non nuls , alors il divise aussi leur somme, leur différence et le reste de la division euclidienne de l'un par l'autre.

Preuve :

Soient a et b deux entiers naturels non nuls tels que et soit p un diviseur commun à a et à b.

a étant un nombre entier, b étant un entier non nul, il existe deux entiers q et r (le quotient et le reste euclidiens de a par b) tels que avec .

p étant un diviseur commun à a et à b, p divise a et p divise b donc il existe deux entiers n et m tels que et .

D'où

Donc p divise à la fois , et r.

2) Le plus grand diviseur commun à deux entiers naturels non nuls a et b avec est le plus grand diviseur commun à b et à .

Preuve :

Soit p le pgcd de deux entiers a et b avec , et soit p' le pgcd de b et

D'après le 1) p étant un diviseur de b et de , p est un diviseur commun à b et . Donc (un diviseur commun est inférieur ou égal au plus grand diviseur commun)

D'après le 1) p' est un diviseur de et de b donc p' est un diviseur commun à a et b et par conséquent

Donc comme et , on a

3) Calcul du pgcd de deux nombres non nuls par l'algorithme des différences

Début

Entrer les nombres a et b.

Appeler X le plus grand de ces deux nombres. '

Appeler Y le plus petit de ces deux nombres. '.

Répéter tant que

Calculer la différence .

Remplacer X par .

Remplacer Y par .

Fin répéter

Sortir Z	'la dernière différence non nulle est le pgcd de a et b.

Fin

Exemple 1 : (détaillé)

Calcul du pgcd de 72 et 51 avec l'algorithme des différences

Étape n°	X	Y		Commentaires
1	72	51	21	X¬max(Y,Z) =51 Y¬min(Y,Z) =21
2	51	21	30	X¬max(Y,Z) =30 Y¬min(Y,Z) =21
3	30	21	9	X¬max(Y,Z) =21 Y¬min(Y,Z) =9
4	21	9	12	X¬max(Y,Z) =12 Y¬min(Y,Z) =9
5	12	9	3	X¬max(Y,Z) =9 Y¬min(Y,Z) =3
6	9	3	6	X¬max(Y,Z) =6 Y¬min(Y,Z) =3
7	6	3	3	X¬max(Y,Z) =6 Y¬min(Y,Z) =3
8	3	3	0	X¬max(Y,Z) =3 Y¬min(Y,Z) =3 Sortir la dernière différence non nulle

La dernière différence non nulle 3 est le pgcd de 72 et 51

Exemple 2: (rédaction simplifiée)

Calcul du pcgd de 540 et 1800 avec l'algorithme des différences

On a	1800 – 540 = 720

720 – 540 = 180

540 – 180 = 360

360 – 180 = 180

180 – 180 = 0

La dernière différence non nulle est 180.

Donc le pgcd de 1080 et 540 est 180.

4) Le plus grand diviseur commun à deux entiers naturels non nuls a et b avec est le plus grand diviseur commun à b et au reste r de la division euclidienne de a par b.

Preuve :

Soit p le pgcd de deux entiers a et b avec , soient q et r le quotient et le reste euclidiens de a par b, et soit p' le pgcd de b et du reste r de la division euclidienne de a par b

D'après le 1) p est un diviseur de b et de r donc

p' est un diviseur de b donc p' est un diviseur de D'après le 1) p' est un diviseur de et de b donc p' est un diviseur commun à a et b et par conséquent

Donc comme et , on a

5) Calcul du pgcd de deux nombres non nuls par l'algorithme des divisions euclidiennes successives (ou par l'algorithme d'Euclide)

Début

Entrer les nombres a et b.

Appeler X le plus grand de ces deux nombres. '

Appeler Y le plus petit de ces deux nombres. '.

Répéter tant que Y n'est pas nul

Calculer le reste r de la division euclidienne de X par Y.

Remplacer X par Y

Remplacer Y par r

Fin répéter

Sortir X	'le dernier reste non nul X est le pgcd de a et b.

Fin

Exemple 1 : (détaillé)

Calcul du pgcd de 504 et 1800 avec l'algorithme d'Euclide

Étape n°	X	Y	Quotient euclidien	reste	Commentaires
1	1800	504	3	288	X¬504 Y¬288
2	504	288	1	216	X¬288 Y¬216
3	288	216	1	72	X¬216 Y¬72
4	216	72	3	0	X¬72 Y¬0 : Sortir X ou le dernier reste non nul

Le dernier reste non nul 72 est le pgcd de 504 et 1800

Exemple 2: (rédaction simplifiée)

Calcul du pcgd de 504 et 1800 avec l'algorithme des divisions euclidiennes successives :

On a	1800 = 504 × 3 + 288

504 = 288 × 1 + 216

288 = 216 × 1 + 72

216 = 72 × 3 + 0

Le dernier reste non nul 72 est le pgcd de 504 et 1800.

6) Fractions irréductibles

Deux nombres entiers naturels sont premiers entre eux s'ils n'ont qu'un seul diviseur commun (le nombre 1), autrement dit si leur pgcd est égal à 1.

On dit qu'une fraction est irréductible quand ses deux termes (le numérateur et le dénominateur) sont premiers entre eux.

Exercice 1 : Prouver que la fraction est irréductible

Calcul du PGCD de 1728 et 3325 avec l'algorithme des divisions successives :

On a	3325 = 1728 × 1 + 1597

1728 = 1597 × 1 + 131

1597 = 131 × 12 + 25

131 = 25 × 5 + 6

25 = 6 × 4 + 1

6 = 1 × 6 + 0

Donc le pgcd de 1728 et 3325 est le dernier reste non nul : 1

Donc la fraction est irréductible.

Exercice 2 : Rendre irréductible la fraction

Calcul du PGCD de 18144 et 26568 avec l'algorithme des divisions successives :

On a	26568 = 18144 × 1 + 8424

18144 = 8424 × 2 + 1296

8424 = 1296 × 6 + 648

1296 = 648 × 2 + 0

Le pgcd de 18144 et 26568 est le dernier reste non nul : 648

Par conséquent 18144 = 648 × 28 ; 26568 = 648 × 41

et le pgcd de 28 et 41 est égal à 1.

Donc et cette écriture est irréductible.

2005-01-15T21:33:18