Méthode pour le PGCD

PGCD : méthodes 1 Résultats à retenir. On considère trois entiers relatifs a, b et c. pgcd(a;b)=pgcd(a-b;b) pgcd(ca;cb)=|c|pgcd(a-b;b) Soit d=pgcd(a;b) alors a=d× a’ et b=d× b’ avec pgcd(a’;b’)=1 Soit d=pgcd(a;b), d est le plus grand diviseur commun de a et de b Soit d=pgcd(a;b), tous les diviseur commun de a et de b sont des diviseurs de d 2 Calculs à l’aide des trois premières propriétés. 1. La première formule est la base de la démonstration de l’algorithme d’Euclide du pgcd. En effet, on peut considérer une division euclidienne comme une une série de soustractions succéssives. Le pgcd apparaît alors naturellement comme le dernier reste non nul de l’algorithme. 2 22. Pour tout entier naturel n, on recherche d =pgcd(n +2n−3;n +5n+6). On remarque que les deux nombres peuvent se factoriser : 2En effet pour tout n∈N, on a n+2n−3 = (n−1)(n+3) et n +5n+6 = (n+3)(n+2). Donc d =pgcd[(n−1)(n+3);(n+3)(n+2)] =|n+3|pgcd(n−1;n+2). Ensuite on peut facilement se débarasser d’un n à l’aide de soustraction : d =|n+3|pgcd(n−1;n+2) =|n+3|pgcd[n−1;n+2−(n−1)] =|n+3|pgcd(n−1;3). Comme n∈N, on a n+3> 0 donc|n+3| = n+3. On a donc d =pgcd(n−1;3). Il convient alors de discuter le résultat en fonction de n : Si n≡ 0 (3) alors d = 3. Si n≡ 1 (3) alors d = 1. Si n≡ 2 (3) alors d = 1. 2 2x −y = 5440 3. Résoudre dansZ le système : . pgcd(x;y) = 8 C’est classique : il s’agit d’utiliser la troisième propriété puis de se ramener à une équation diophantienne.