PGCD et PPCM de deux entiers

Description

PGCD et PPCM de deux entiers : Table desmatières I Plus grand commun diviseur de deux entiers : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 II Détermination du PGCD par l'algorithme d'Euclide . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 III Entiers premiers entre eux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 IV Théorème de Gauss et applications : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 V Petit théorème de Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 VI Plus petit commun multiple de deux entiers . . . . . . . . . . . . . . . . .

• naturels supérieurs


• théorème de bézout


• table des matières


• r3 ·


• diviseur


• couple solution


• entier naturel


• exposant


• définition de ?

Sujets

• exercice
• exercices

Informations

• Publié par: Ecole-pour-tous
• Nombre de lectures: 366
• Langue: Français

Extrait

PGCD et PPCM de deux entiers :

Table des matières

I

I II III IV V VI

Plus grand commun diviseur de deux entiers :. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Détermination du PGCD par l’algorithme d’Euclide. . . . . . . . . . . . . . . . . . . . . . . . . . . . Entiers premiers entre eux. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . Théorème de Gauss et applications :. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . Petit théorème de Fermat. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . Plus petit commun multiple de deux entiers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Plus grand commun diviseur de deux entiers :

1 3 4 6 8 9

Définition : Soientaetbdeux entiers naturels non nuls. On noteD(a) l’ensemble des diviseurs dea. Le plus grand élément deD(a)∩D(b), ensemble des diviseurs positifs communs àaet àb, est leplus grand commun diviseurdeaetb, ou encore PGCD deaetb. On le note pgcd(a;b) ou PGCD(a;b)

Cas particuliers : pgcd(a;a)=a;p g cd; pgcd((1 ; a)=1 a; 0)=apouranon nul. Remarque :le PGCD de deux entiers naturels est un entier au moins égal à 1.

Propriété : Soientaetbdeux entiers naturels au moins égaux à 2. Le PGCD deaetbest égal au produit des facteurs premiers communs deaet deb, avec pour chacun d’eux, l’exposant le plus petit de ceux qu’il a dansaet dansb.

Démonstration :: Soitdle PGCD deaet deb, naturels supérieurs ou égaux à 2. Commeddivisea, sa décomposition en facteurs premiers est formée des facteurs premiers deaavec un exposant au plus égal à celui qu’ils sont dans dansa. De même pourb. Ainsi, la décomposition dedcomprend les facteurs premiers àaet àb, avec un exposant au plus égal au plus petit des exposants dans les décompositions deaet deb. Commedest le plus grand des diviseurs communs, ces exposants sont égaux au plus petit de ceux se trouvant dans la décomposition deaet deb.

Exemple :cherchons le PGCD de 700 et de 90.

Remarque :Soienaetbdes entiers relatifs non nuls simultanément. CommeD(a)=D(−a), le PGCD deaetbest le même que celui de|a|et de|b|.

1

On peut ainsi se restreindre aux entiers naturels.

TABLE DES MATIÈRES

Propriété : 1. Siadiviseb, alors pgcd(a;b)=a 2.Propriété fondamentale :Soitanon nul tel quea=bq+r. (division euclidienne deaparb). Alors :D(a)∩D(b)=D(b)∩D(r) et pgcd(a;b)=pgcd(b;r).

Démonstration ::

1. Siadiviseb, tout diviseur deaest un diviseur deb. Par conséquent :D(a)∩D(b)=D(a) et le plus grand élément deD(a) esta. 2. Pour démontrer l’égalité des deux ensemblesE=D(a)∩D(b) etF=D(b)∩D(r), on montre queEest inclus dansFet queFest inclus dansE. •Soitd∈E. Alorsddiviseb, doncddivisebqet commeddivisea,ddivisea−bq=r, doncd∈F. •Soitd∈F.ddivisebdoncbq. Commeddiviser,ddivisebq+r=adoncd∈E. Les ensemblesEetFsont égaux, donc ils ont le même plus grand élément. Ainsi : pgcd(a;b)=pgcd(b;r).

Exercice 1 Déterminer le PGCD de 1960 et de 34300. 3 1 2 2 2 3 On a : 1 960=2×5×7 et 34 300=2×5×7 . 2 1 2 On en déduit que PGCD(1960 ; 34300)=2×5×7=980

Exercice 2 Déterminer le PGCD de deux entiers dépendant den: Déterminer, selon les valeurs den, le PGCD deA=2n+1 et deB=n−5.

Méthode :on utilise la propriété fondamentale. Pour éliminern, on calculeA−2B.A−2B=2n+1−2(n−5)=11 doncA=2B+11. PGCD(A;B)=PGCD(B; 11). Comme 11 est un nombre premier, le PGCD deBet de 11 ne peut valoir que 1 ou 11. PGCD(B; 11)=11 si et seulement si 11 diviseB. PGCD(B; 11)=11⇔B≡0(11)⇔n−5≡0(11)⇔n≡5(11). On en conclut que le PGCD deAetBest 11 lorsquenest congru à 5 modulo 11 et à 1 dans les autres cas.

Exercice 3 Égalité de deux PGCD : Soientaetbdeux entiers naturels non nuls. Soientx=7a+5bety=4a+3b. Montrer que le PGCD dexet deyest égal au PGCD deaet deb.

Première méthode :7a+5b=(4a+3b)+(3a+2b) donc pgcd(7a+5b; 4a+3b)=pgcd(4a+3b; 3a+2b). 3a+2b=2(a+b)+adonc pgcd(4a+3b; 3a+2b)=pgcd(a+b;a)=pgcd(a;b)=pgcd(a;b). On en déduit que : pgcd(x;y)=pgcd(a;b).

Deuxième méthode :Soitdle PGCD deaetb. Alorsddiviseaetb, donc 7a+5bet 4a+3bdoncd ′ divise le PGCDddexety. ′ ′ ′ Commeddivise 7a+5bet 4a+3b,ddivise 7(4a+3b)−4(7a+5b)=b. De même,ddivise 3(7a+

Page 2/10

II

′ 5b)−5(4a+3b)=a. Puisqueddiviseaetb, il divise leur PGCDd. ′ ′ ′ ddivisedetddivised. Doncd=d.

Détermination du PGCD par l’algorithme d’Euclide

TABLE DES MATIÈRES

(Cet algorithme, c’estàdire une suite d’instructions, fut décrit par Euclide au IIIıème siècle avant JC)

Description de l’algorithme d’Euclide Soientaetbdeux entiers naturels non nuls, aveca>b. On diviseaparb.a=bq 1 +r 1 , avec 0≤r 1 <b. Sir 1 =0, alors pgcd(a;b)=bpuisquebdivisea. Sir 1 6=0, pgcd(a;b)=pgcd(b;r 1 ). On effectue alors la division debparr 1 . On a :b=r 1 q 2 +r 2 , avec 0≤r 2 <r 1 . Sir 2 =0, alors pgcd(a;b)=pgcd(b;r 1 )=r 1 . Sir 2 6=0, pgcd(b;r 1 )=pgcd(r 1 ;r 2 ). On continue la suite de divisions euclidiennes en divisant un reste par le reste suivant. On obtient une suite de restesr 1 ,r 2 . ., . r n , avecr 1 >r 2 >r 3 ≥∙ ∙ ∙ 0. Comme ce sont des entiers, il existe un reste qui est nul. Notonsr n le dernier reste non nul. Alors : pgcd(a;b)=pgcd(b;r 1 )=pgcd(r 1 ;r 2 )=. . .=pgcd(r n−1 ;r n )=r n carr n diviser n−1

Propriété : Le PGCD de deux entiers non nulsaetbtels quebne divise pasaest le dernier reste non nul de la suite des divisions de l’algorithme d’Euclide.

Corollaires : 1. L’ensemble des diviseurs communs à deux entiersaetbest l’ensemble des diviseurs de leur PGCD. 2. Soitaetbdeux entiers non nuls. Sikest un entier naturel non nul, pgcd (k a;kb)=k×pgcd (a;b).

Démonstration : 1.D(a)∩D(b)=D(b)∩D(r 1 )=D(r 1 )∩D(r 2 )= ∙ ∙ ∙ =D(r n )∩D(0)=D(r n )=D(d) puisqued=r n . ′ 2. On notedle PGCD deaetbetdcelui dek aetkb. ′ ′ Commeddiviseaetb,kddivisek aetkb, donckddivise leur PGCDd, donckddivised. ′ ′ ′ d=k(kd). (kentier) ′ ′ ′ ′ ddivisek aetkb, donck kddivisek aetkb; on en déduit quek ddiviseaetb, donc leur PGCDd.k d ′ ′ divised, donck=1 etd=kd.

Page 3/10

III

Entiers premiers entre eux

Définition : Deux entiers sont premiers entre eux lorsque leur PGCD est égal à 1.

Remarques : •Cela revient à dire que leurs seuls diviseurs sont 1 et 1.

TABLE DES MATIÈRES

•Il ne faut pas confondre nombre premiers et nombres premiers entre eux. Par exemple, 15 et 22 sont pre miers entre eux, mais pas premiers.

Propriété : ′ ′ Soientaetbdes naturels non nuls etdun diviseur commun deaetb. On posea=d aetb=d b. ′ ′ Le PGCD deaetbestdsi et seulement siaetbsont premiers entre eux.

Démonstration :: ′ ′ •Sidest le PGCD deaetb, soita=d aetb=d b. On en déduit que : ′ ′ ′ ′ ′ ′ ′ ′ d=pgcd(a;b)=pgcd(d a;d b)=d pgcd(a;b). Commedest non nul, pgcd(a;b)=1 etaetbsont premiers entre eux.

′ ′ ′ ′ •Si pgcd(a;b)=1, alors pgcd(a;b)=dpgcd(a;b)=d

Exercice 1 Déterminer le PGCD de 8 870 et de 3 120.

Réponse :on utilise l’algorithme d’Euclide : on trouve un PGCD égal à 10.

Exercice 2 Écrire l’algorithme d’Euclide pour une calculatrice. Solution :

– Entreraetb – Tant queb6=0 (début de la boucle) ³ ´ a –E→q b –a−bq→r –b→aLe nouveau dividende estb. –r→b(Le nouveau diviseur estr) – Fin Tant que – Affichera(C’est le dernier reste non nul, donc le PGCD cherché) Exercice 3 Déterminer les naturels dont la somme est 600 et dont le PGCD est 50.

Solution : On chercheaetbtels que :a+b=600 et pgcd(a;b)=50. ′ ′ ′ ′ ′ ′ Soientaetbles entiers tels que :a=50aetb=50b; alorsaetbsont premiers entre eux. ′ ′ ′ ′ ′ ′ a+b=600⇔50a+50b=600⇔50(a+b)=600⇔a+b=12. On cherche tous les couples d’entiers naturels vérifiant cette relation et on ne garde que les couples

Page 4/10

TABLE DES MATIÈRES

d’entiers premiers entre eux. (1 ; 11) ; (5 ; 7) ; (7 ; 5) et (11 ; 1). On en déduit les couples solutions : (50 ; 150) ; (250 ; 350) ; (350 ; 250) et (550 ; 50).

Théorème de Bézout : Deux entiersaetbsont premiers entre eux si, et seulement si, il existe deux entiers relatifsuetvtels que au+bv=1. Démonstration ::

•On supposeaetbpremiers entre eux, donc pgcd(a;b)=1. L’un des deux nombres est non nul, par exemple a. •On considère l’ensemble des nombres entiers de la formeau+bv, avecuetventiers. Cet ensemble n’est pas vide, puisqu’il contient par exemplea, (avecu=1 etv=0). •Si E contienta, il contient−aet l’un de ces deux entiers est positifs, donc E contient un entier positif. •Soitβexiste; il le plus petit de ces entiers positifs de E. u 0 etv 0 tels que :β=au 0 +bv 0 . •La division euclidienne deaparβs’écrit :a=βq+r, avec 0≤r<βd’où r=a−βq=a−(au 0 +bv 0 )q=a(1−u 0 q)+b(−v 0 q). Ainsi,rappartient à E puisqu’il est de la formeau+bv avecuetventiers. Par définition deβqui est le plus petit entier positif de E, on a :r=0. On en déduit :a=βq, doncβdivisea. •On montre de même queβdiviseb, doncβ=1 puisque le PGCD deaet debest 1. Par conséquent, il existe bien deux entiersu 0 etv 0 tels queau 0 +bv 0 =1. Réciproque : S’il existe des entiersuetvtels queau+bv=1, alors, sidest le PGCD deaetb, il diviseaetb, doncau+bv donc 1 ; par conséquent,d=1 etaetbsont premiers entre eux.

Exemples : 1. 5 et 12 sont premiers entre eux car 7×(−5)+3×12=1. 2. (n+1)−n=1 doncnetn+1 sont toujours premiers entre eux.

Corollaire Sidest le PGCD de deux entiersaetb, alors il existe des entiersuetvtels queau+bv=d.

Démonstration :: ′ ′ ′ ′ a=d aetb=d boùaetbsont premiers entre eux. On applique alors lethéorème de Bézout.

Propriété : Un nombre premier est premier avec tous les nombres qu’il ne divise pas.

Démonstration :: Soitpun nombre premier. Soitaun entier non divisible parp. On notedle PGCD depet a.dvaut 1 oup, puisquepest premier.

Page 5/10

dne peut pas être égal àp, sinonpdiviseraita. Par conséquent :d=1.

TABLE DES MATIÈRES

Exercice fondamental : Montrer que les nombres 3 920 et 1 089sont premiers entre eux et déterminer des entiersuetvtels que 3920u+1089v=1.

Méthode :reporte alors chaque reste obtenu enon écrit toutes les divisions de l’algorithme d’Euclide ; on partant de la fin. On obtient : 3920=1089×3+653 1089=653×1+436 653=436×1+217 436=217×2+2 217=2×108+1 2=1×2+1 Par conséquent : le dernier reste non nul est 1, donc les deux nombres sont premiers entre eux. On a alors : •217−2×108=1 (1) •2=436−217×2 donc en reportant dans (1) : 217−(436−217×2)×108=1 d’où 217×217−436×108=1 (2) •217=653−436×1. On remplace dans (2) : (653−436×1)×217−436×108=1 d’où 653×217−436×325=1 (3) •436=1089−653. On remplace dans (3) : 653×217−(1089−653)×325=1 d’où 653×542−1089×325=1 (4) •653=3920−1089×3. On remplace dans (4) : (3920−1089×3)×542−1089×325=1 soit : 3920×542−1089×1951=1.

Propriété : Si un entier est premier avec deux entiers, il est entier avec leur produit.

Démonstration : Soitaun entier premier avecbetc. D’après le théorème de Bézout, il existe deux entiersuetvtels queau+bv=1 ′ ′ ′ ′ et des entiersuetvtels queau+c v1. On effectue le produit membre à membre. On obtient : ′ ′2′ ′ ′ ′ ′ ′ ′ ′ (au+bv)(au+c v)=1⇔a uu+acu v+abv u+bc v v=1⇔a(auu+cu v+bv u)+bc(v v)=1. Comme ′ ′ ′ ′ auu+cu v+bv uetv vsont des entiers, on en déduit queaetbcsont premiers entre eux.

Exemples : 1. 4 est premier avec 9 et avec 35, donc 4 est premier avec 315. 2 2. Pour toutn,nest premier avecn+1 et avecn−1, doncnest premier avecn−1.

Page 6/10

IV

Théorème de Gauss et applications :

TABLE DES MATIÈRES

Théorème Soienta,betctrois entiers. Siadivise le produitbcet siaest premier avecb, alorsadivisec.

Démonstration :: Siaest premier avecb, il existeuetvtels que :au+bv=1. On en déduit :acu+bc v=c. Or,adiviseacuetbcpar hypothèse, doncadivisec.

Exemple :Soientaetbdeux entiers tels que 5a=14b. 14 divise le produit 5a, les entiers 14 et 5 sont premiers entre eux, donc 14 divisea. De même, 5 diviseb.

Corollaires : 1. Si un entier est divisible par des entiersaetbpremiers entre eux, alors il est divisible par leur produit ab. 2. Si un entier premier divise un produit de facteursab, alors il divise au moins un des facteursaetb.

Démonstration ::

′ ′ ′ 1. Soitnentier divisible paraetb. Il existe des entiersketktels quen=k aetn=k bdoncn=k a=k b. ′ adivise donck b. Commeaetbsont premiers entre eux, on en déduit (d’après le théorème de Gauss) que ′ ′ adivisekdonc il existeqtel quek=q a. On a alorsn=q abetnest divisible parab. 2. Soitpun nombre premier divisantab. Sipdivisea, alors la condition est vérifiée. Supposons quepne divise pasa. Alorsaetpcommesont premiers entre eux ; pdiviseab, alorspdivise bd’après le théorème de Gauss. Exercices : 2 1. Résoudre une équation du typeax+b y=0 dansZ. Exemple :Déterminer les entiersxetytels que 7x+5y=0. Cette équation s’écrit 7x= −5y. 7 et−5 sont premiers entre eux. 7 divise−5ydonc 7 diviseyd’après le théorème de Gauss. Ainsiy=7kaveckentier. En reportant : 7x= −5×7kd’oùx= −5k. Les solutions sont les couples (−5k; 7k) oùk∈Z. 2 2. Résoudre une équation du typeax+b y=cdansZ, avecaetbpremiers entre eux.

(a)Exemple :Déterminer les entiersxetytels que 5x+7y=1 Comme 5 et 7 sont premiers entre eux, il existe d’après le théorème de Bezout deux nombresuetv tels que : 5u+7v=1. Pour détermineruetv, on peut utiliser l’algorithme d’Euclide ou remarquer que 5×10−7×7=1 donc on peut prendreu=10 etv= −7. Le couple (10 ;−7) est une solution particulière de cette équation. Alors : 5x+7y=1⇔5x+7y=5×10−7×7⇔5(x−10)=7(−y−7). 5 divise 7(−y−5 et 7 sont premiers entre eux. D’après le théorème de Gauss, on en déduit que 57) ; divise−y−7. Par conséquent :−y−7=5k,k∈Z, doncy= −7−5k. On reporte dans l’équation 5(x−10)=7(−y−7). On obtient : 5(x−10)=7×5kd’oùx−10=7ksoit

Page 7/10