Méthode pour le PGCD

icon

3

pages

icon

Français

icon

Documents

2013

Lire un extrait
Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris
icon

3

pages

icon

Français

icon

Ebook

2013

Lire un extrait
Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

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.
Voir Alternate Text

Publié par

Publié le

17 octobre 2013

Nombre de lectures

579

Langue

Français

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

Voir Alternate Text
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents
Alternate Text