Méthode pour le PGCD

Description

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.

Sujets

• Plus grand commun diviseur
• cours de math

Informations

• Publié par: Oliv94
• Publié le: 17 octobre 2013
• Nombre de lectures: 579
• Langue: Français

Extrait

1

2

Résultats

à retenir.

PGCD

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)

:

méthodes

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

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. Pour tout entier natureln, on recherched=pgcd(n2+ 2n−3;n2+ 5n+ 6).

3.

On remarque que les deux nombres peuvent se factoriser :
En effet pour toutn∈N, on an+ 2n−3 = (n−1)(n et+ 3)n2+ 5n+ 6 = (n+ 3)(n+ 2).
Doncd=pgcd[(n−1)(n+ 3); (n+ 3)(n+ 2)] =|n+ 3|pgcd(n−1;n+ 2).

Ensuite on peut facilement se débarasser d’unnà 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).
Commen∈N, on an+ 3>0 donc|n+ 3|=n+ 3.

On a doncd=pgcd(n−1; 3). Il convient alors de discuter le résultat en fonction den:
Sin≡ alors0 (3)d= 3.
Sin≡1 (3) alorsd= 1.
Sin≡ alors2 (3)d= 1.
2−y2= 5 440
Résoudre dansZle système :pxgcd(x;y .) = 8
C’est classique : il s’agit d’utiliser la troisième propriété puis de se ramener à une équation diophantienne.

Il existex0ety0dansZtels quex= 8x0ety= 8y0et pgcd(x0;y0) = 1.
On a donc 5 440 =x2−y2= (8x0)2−(8y0)2= 64(x02−y02).
C’est à dire :x02−y02 64 440 = 5 puisque= 85×85.
Il s’agit de trouver les couples d’entiers relatifs premiers entre eux qui vérifient :x02−

On ax02−y02= (x0−y0)(x0+y0) = 85 = 5×17.

1

y02= 85.

On doit donc avoir :
xx00−+yy00=517ou=xx00+−yy005==71
C’est à direx01+5==172t1ey0 2= 17−5 = ou 6x071=211te=+5y0= 5−=172−6
On vérifie que pgcd(11; 6) = pgcd(11;−6) = 1 et que 112−62= 112−(−6)2= 121−36 = 85.

Donc on ax= 8×11 ety= 8×6 oux= 8×11 ety= 8×(−6)
Les solutions sont donc les couples{ (11;(11; 6) ;−6)}.

3 Exercices nécessitant l’utilisation des deux dernières p ropriétés.

Il arrive souvent que les relations à démontrer soient trop compliquées pour être justifiées à l’aide des trois premières
propriétés.
Pour utiliser les deux autres propriétés, je propose les raisonements suivants :

1.

d= pgcd(a;b) diviseaetbdonc divise toute combinaison linéaire deaetb.

(a)rertnoM71e1qunnuotrlbpecuitrrdéoutties+2+3n∈N.

(b)

Soitd= pgcd(11n+ 3; 7n+ 2).
Alorsd|11n+ 3 etd|7n+ 2.
Doncddivise 7(11n+ 3)−11(7n+ 2) =−1.
Doncd= 1 et la fraction est bien irréductible pour toutn.

Les calculs à l’aide des premieres formules à partir de pgcd(11n+ 3; 7n ne sont pas aisés.+ 2)
Il est préférable et en fin de compte bien plus clair d’utiliser une combinaison linéaire bien choisie.

Existe-t-il deux entiers naturelsaetbtelsquea+b= 500 et pgcd(a;b ?) = 7

Soitd= pgcd(a;b).
Alorsd|aetd|b.

Doncd|a+b(difficile de trouver plus simple . . . )
On veut doncd= 7|500.

Mais 500 = 490 + 10 et 10 n’est pas un multiple de 7.
Conclusion : il est impossible de déterminer de tels entiers .

(c)Soita= 5n2+ 7 etb=n2 avec+ 2n∈Ndémontrer que pgcd(a;b) divise 3.

Soitd= pgcd(a;b).
Alorsddivisea= 5n2+ 7.
Etddiviseb=n2+ 2.
Doncddivise 5b−a(on cherche une combinaison linéaire qui élimine « le plus denpossible »).
Orb−a= 3.
Conclusion : on a biend|3.

2

2.

d1=d2

(a)

(b)

⇐⇒

d1|d2etd2|d1.

Soitd= pgcd(a bc). Sid|balorsd= pgcd(a;b).

Résultat proposé par Dimitri PYRON, T7.

Appelonsd0= pgcd(a;b), on veut prouver qued=d0.
Pour cela raisonnons en deux étapes comme proposé dans ce paragraphe :
i.d0= pgcd(a;b) doncd0|aetd0|bdoncd0|aetd0|bcdoncd0|d= pgcd(a;bc).
On a utilisé la dernière propriété.
ii.d= pgcd(a;bc) doncd|a, maisd|bpar hypothèse. Doncd|d0= pgcd(a;b).
Même argument.
iii. Il ne reste plus qu’à conclure.
Commed|d0etd0|d, on ad=d0donc pgcd(a;bc) = pgcd(a;b) si pgcd(a;bc)|b.

Soita∈N∗etb∈N, on posem= 3a+ 4betn= 2a+ 3b. Démontrer que pgcd(a;b) = pgcd(m;n).

Posonsd1= pgcd(a;b) etd2= pgcd(m;n) et travaillons comme ci-dessus en deux étapes :
i.d1= pgcd(a;b) doncd1|aetd1|b.
Doncd1|3a+ 4betd1|2a+ 3b(méthode des combinaisons linéaires vue ci-dessus).
Doncd1|metd1|nc’est à dired1|d2.
ii. On remarque quea= 3m−4netb= 3n−2m a cherché cette combinaison linéaire).. (on
Ord2= pgcd(m;n) doncd2|metd2|n.
Doncd2|3m−4netd2|3n−2m(méthode des combinaisons linéaires vue ci-dessus).
Doncd2|aetd2|bc’est à dired2|d1.
iii. Finalementd1|d2etd2|d1d’oùd2=d1, c.à.d. pgcd(a;b) = pgcd(3a+ 4b; 2a+ 3b).

3