Diviseurs et PGCD, exercice 2

1. Déterminez le PGCD de 770 et 198 par l'algorithme par soustractions

L'algorithme par soustractions repose sur la propriété suivante :

« a et b étant deux nombres entiers positifs tels que , on a PGCD (a ; b) = PGCD(b ; a-b) »

Nous allons donc appliquer cette propriété pas à pas et présenter les résultats dans un tableau.

a	b	a-b
770	198	572
572	198	374
374	198	176
198	176	22
176	22	154
154	22	132
132	22	110
110	22	88
88	22	66
66	22	44
44	22	22
22	22	0

De la propriété appliquée 12 fois successivement, on déduit que :
PGCD(770 ; 198) = PGCD (22 ; 22) = 22
Le PGCD (770 ; 198) est la dernière différence non nulle obtenue par l'algorithme par soustractions.

2. Déterminez le PGCD de 7830 et 12818 par l'algorithme d'Euclide
L'algorithme par divisions encore appelé algorithme d'Euclide repose sur la propriété suivante :

« a et b étant deux nombres entiers positifs tels que , on a PGCD (a ; b) = PGCD(b ; reste de a : b) »

Nous allons donc appliquer cette propriété pas à pas et présenter les résultats dans un tableau.
On effectue successivement les divisions euclidiennes et on note les restes successifs.

a	b	Reste de a:b
12818	7830	4988
7830	4988	2842
4988	2842	2146
2842	2146	696
2146	696	58
696	58	0

De la propriété ci-dessus appliquée 6 fois successivement on déduit que :
PGCD (12818 ; 7830) = PGCD(696 ; 58) = 58
Remarque :

Le PGCD(1281 ; 7830) est le dernier reste non nul obtenu dans l'algorithme d'Euclide donc PGCD(7830 ; 1281) = 58