Cela revient à dire que leurs seuls diviseurs sont -1 et 1 • Il ne faut pas confondre nombre premiers et nombres premiers entre eux Par exemple, 15 et 22 sont pre
| Previous PDF | Next PDF |
[PDF] PGCD et PPCM Nombres premiers entre eux
L'idée de l'algorithme d'Euclide : soit a et b deux entiers naturels avec b
[PDF] PGCD, PPCM, nombres premiers, décomposition en produit de
PGCD, PPCM, nombres premiers, décomposition en produit de facteurs Par exemple : • deux nombres premiers distincts sont toujours premiers entre eux ;
[PDF] Nombres premiers pgcd et ppcm - Lycée dAdultes
27 jui 2016 · Nombres premiers pgcd et ppcm Table des matières 3 3 Nombres premiers entre eux il admet exactement deux diviseurs 1 et lui-même
[PDF] LES NOMBRES PREMIERS – PPCM - Pierre Lux
La multiplication de deux nombres, même très grands, n'est pas compliquée : avec du papier et un Si a et b sont premiers entre eux, on a PPCM(a ; b) = a × b
[PDF] PGCD et PPCM de deux entiers : - Blog Ac Versailles
Cela revient à dire que leurs seuls diviseurs sont -1 et 1 • Il ne faut pas confondre nombre premiers et nombres premiers entre eux Par exemple, 15 et 22 sont pre
[PDF] I PGCD et PPCM de deux nombres entiers - My MATHS SPACE
Deux nombres premiers distincts n'ont pas de diviseurs communs On dit que deux entiers relatifs non nuls a et b sont premiers entre eux lorsque leur PGCD
[PDF] PPCM et PGCD
cherche des multiples communs à deux nombres on peut, même si l'énoncé ne demande pas de trouver le plus petit d'entre eux, chercher le PPCM des deux
[PDF] Chapitre 2 Cours Nombres premiers et PPCM
savoir déterminer le PPCM et le PGCD de deux entiers naturels à partir de leur décomposition en facteurs premiers • savoir utiliser le lien entre le PPCM et le
[PDF] Arithmétique - Annuaire IMJ-PRG
Soient a et b deux nombres entiers strictement positifs ppcm (opposés l'un `a l' autre) Lorsque pgcd(a, b) = 1, on dit que a et b sont premiers entre eux
[PDF] montrer qu'il existe une infinité de nombres premiers de la forme 4n+1
[PDF] extraction du charbon
[PDF] origine du charbon
[PDF] le charbon
[PDF] 3 conditions necessaires a la formation du charbon
[PDF] la formation des combustibles fossiles schéma
[PDF] origine des combustibles fossiles seconde
[PDF] formation du charbon schéma
[PDF] somme de racine carré
[PDF] calcul avec racine carré seconde
[PDF] formation du sac embryonnaire chez les spermaphytes
[PDF] formation du grain de pollen pdf
[PDF] fusion partielle et cristallisation fractionnée
[PDF] magmatisme de dorsale
PGCD et PPCM de deux entiers :
Table des matières
IPlus grand commun diviseur de deux entiers :. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
IIDéterminationdu PGCD par l"algorithmed"Euclide. . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
IIIEntierspremiers entre eux. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
IVThéorème de Gauss et applications:. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
VPetit théorème de Fermat. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
VIPlus petit commun multiplede deux entiers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
I Plus grand commun diviseur de deux entiers :
Définition :
Soientaetbdeux entiers naturels non nuls. On noteD(a) l"ensemble des diviseurs dea.Le plusgrandélémentdeD(a)D(b), ensembledesdiviseurspositifscommunsàaet àb,est leplusgrand
commun diviseurdeaetb, ou encore PGCD deaetb. On le note pgcd(a;b) ou PGCD(a;b)Casparticuliers :
pgcd(a;a)a;pgcd(1; a)=1 ; pgcd(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 produitdesfacteurspremierscommunsdeaet deb,avec pourchacund"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écompositiondeaet 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 deaet deb. 1TABLE DES MATIÈRES
On peut ainsi se restreindre aux entiers naturels.Propriété :
1. Siadiviseb, alors pgcd(a;b)a
2. Propriété fondamentale :Soitanon nul tel queabqr. (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. Pourdémontrerl"égalitédesdeuxensemblesED(a)D(b) etFD(b)D(r), onmontrequeEestinclus
dansFet queFest inclus dansE. SoitdE. Alorsddiviseb, doncddivisebqet commeddivisea,ddiviseabqr, doncdF. SoitdF.ddivisebdoncbq. Commeddiviser,ddivisebqradoncdE.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.On a : 1960235172et 34300225273.
On en déduit que PGCD(1960 ; 34300)225172980
Exercice 2 Déterminer le PGCD de deux entiers dépendant den: Déterminer,selon les valeurs den, le PGCD deA2n1 et deBn5. Méthode :on utilisela propriétéfondamentale. Pouréliminern,oncalculeA2B.A2B2n12(n5)11doncA2B11.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)11B0(11)n50(11)n5(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. Soientx7a5bety4a3b. Montrer que le PGCD dexet deyest égal au PGCD deaet deb. Premièreméthode:7a5b(4a3b)(3a2b)doncpgcd(7a5b; 4a3b)=pgcd(4a3b; 3a2b).3a2b2(ab)adonc pgcd(4a3b; 3a2b)=pgcd(ab;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 7a5bet 4a3bdoncd divise le PGCDddexety. Commeddivise 7a5bet 4a3b,ddivise 7(4a3b)4(7a5b)b. De même,ddivise 3(7aPage 2/
10TABLE DES MATIÈRES
5b)5(4a3b)a. Puisqueddiviseaetb, il divise leur PGCDd.
ddivisedetddivised. Doncdd. II Détermination du PGCD par l"algorithme d"Euclide(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, avecab.
On diviseaparb.abq1r1, avec 0r1b.
Sir10, alors pgcd(a;b)bpuisquebdivisea.
Sir10, pgcd(a;b)=pgcd(b;r1). On effectue alors la division debparr1.On a :br1q2r2, avec 0r2r1.
Sir20, alors pgcd(a;b)=pgcd(b;r1)r1.
Sir20, pgcd(b;r1)=pgcd(r1;r2).
Oncontinuela suitede divisionseuclidiennesendivisantunreste par lerestesuivant.Onobtientunesuite de restesr1,r2, ...rn, avecr1r2r3 0. Comme ce sont des entiers, il existe un reste qui est nul. Notonsrnle dernier reste non nul. Alors : pgcd(a;b)=pgcd(b;r1)=pgcd(r1;r2)=...=pgcd(rn1;rn)rn carrndivisern1Propriété :
Le PGCD de deux entiers non nulsaetbtels quebne divise pasaest le dernier reste non nul de la suite des divisions de l"algorithmed"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 (ka;kb)kpgcd (a;b).
Démonstration :
1.D(a)D(b)D(b)D(r1)D(r1)D(r2)D(rn)D(0)D(rn)D(d) puisquedrn.
2. On notedle PGCD deaetbetdcelui dekaetkb.
Commeddiviseaetb,kddivisekaetkb, donckddivise leur PGCDd, donckddivised. d k(kd). (kentier) d divisekaetkb, donckkddivisekaetkb; on en déduit quekddiviseaetb, donc leur PGCDd.kd divised, donck1 etdkd.Page 3/
10TABLE DES MATIÈRES
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.Il ne faut pas confondre nombre premiers et nombres premiersentre 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 poseadaetbdb. Le PGCD deaetbestdsi et seulement siaetbsont premiers entre eux.Démonstration::
Sidest le PGCD deaetb, soitadaetbdb. On en déduit que : d=pgcd(a;b)=pgcd(da;db)=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 8870 et de 3120. Réponse :on utilise l"algorithmed"Euclide : on trouve un PGCD égal à 10. Exercice 2 Écrire l"algorithmed"Euclide pour une calculatrice.Solution:
- Entreraetb - Tant queb0 (début de la boucle) -E?a b? q -abqr -baLe nouveau dividende estb. -rb(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 :ab600 et pgcd(a;b)50.
Soientaetbles entiers tels que :a50aetb50b; alorsaetbsont premiers entre eux. ab60050a50b60050(ab)600ab12.On cherche tous les couples d"entiers naturels vérifiant cette relation et on ne garde que les couples
Page 4/
10TABLE 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 deBézout :
Deux entiersaetbsont premiers entre eux si, et seulement si, il existe deux entiers relatifsuetvtels que
aubv1.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 formeaubv, avecuetventiers. Cet ensemble n"est pas vide, puisqu"il contient par exemplea, (avecu1 etv0).Si E contienta, il contientaet l"un de ces deux entiers est positifs, donc E contient un entier positif.
Soitβle plus petit de ces entiers positifs de E. ; il existeu0etv0tels que :βau0bv0. La division euclidienne deaparβs"écrit :aβqr, avec 0rβd"où raβqa(au0bv0)qa(1u0q)b(v0q). Ainsi,rappartient à E puisqu"il est de la formeaubv avecuetventiers. Par définition deβqui est le plus petit entier positif de E, on a :r0.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 entiersu0etv0tels queau0bv01.Réciproque :
S"il existe des entiersuetvtels queaubv1, alors, sidest le PGCD deaetb, il diviseaetb, doncaubv donc 1 ; par conséquent,d1 etaetbsont premiers entre eux.Exemples:
1. 5 et 12 sont premiers entre eux car 7(5)3121.
2. (n1)n1 doncnetn1 sont toujours premiers entre eux.
Corollaire
Sidest le PGCD de deux entiersaetb, alors il existe des entiersuetvtels queaubvd.Démonstration::
adaetbdboù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/
10TABLE DES MATIÈRES
dne peut pas être égal àp, sinonpdiviseraita.Par conséquent :d1.
Exercice fondamental :
Montrer que les nombres 3920 et 1089sont premiers entre eux et déterminer des entiersuetvtels que3920u1089v1.
Méthode :on écrit toutes les divisions de l"algorithme d"Euclide ; onreporte alors chaque reste obtenu en
partant de la fin.On obtient :
392010893653
10896531436
6534361217
43621722
21721081
2121Par conséquent : le dernier reste non nul est 1, donc les deux nombres sont premiers entre eux.
On a alors :
21721081 (1)
24362172 donc en reportant dans (1) :
217(4362172)1081 d"où 2172174361081 (2)
2176534361. On remplace dans (2) :
(6534361)2174361081 d"où 6532174363251 (3)4361089653.On remplace dans (3) :
653217(1089653)3251 d"où 65354210893251 (4)
653392010893.On remplace dans (4) :
(392010893)54210893251 soit : 3920542108919511.Propriété :
Si un entier est premier avec deux entiers, il est entier avecleur produit.Démonstration :
et des entiersuetvtels queaucv1. On effectue le produit membre à membre. On obtient : (aubv)(aucv)1a2uuacuvabvubcvv1a(auucuvbvu)bc(vv)1. Comme auu cuvbvuetvvsont 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. Pour toutn,nest premier avecn1 et avecn1, doncnest premier avecn21.
Page 6/
10TABLE DES MATIÈRES
IV Théorème de Gausset applications:
Théorème
Soienta,betctrois entiers. Siadivise le produitbcet siaest premier avecb, alorsadivisec.Démonstration ::
Siaest premier avecb, il existeuetvtels que :aubv1. On en déduit :acubcvc.Or,adiviseacuetbcpar hypothèse, doncadivisec.
Exemple:Soientaetbdeuxentierstelsque5a14b.14 diviseleproduit5a, les entiers14et 5 sontpremiers entre eux, donc 14 divisea.De même, 5 diviseb.
Corollaires :
1. Si un entier est divisiblepar des entiersaetbpremiersentre eux,alors il est divisiblepar 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 quenkaetnkbdoncnkakb.
adivise donckb. Commeaetbsont premiers entre eux, on en déduit (d"après le théorèmedeGauss) que
adivisekdonc il existeqtel quekqa. On a alorsnqabetnest divisible parab.2. Soitpun nombre premier divisantab.
Sipdivisea, alors la conditionest vérifiée.
Supposons quepne divise pasa. Alorsaetpsont premiers entre eux; commepdiviseab, alorspdivise bd"après le théorème de Gauss.Exercices:
1. Résoudre une équation du typeaxby0 dansZ2.
Exemple :Déterminer les entiersxetytels que 7x5y0.Cette équation s"écrit 7x 5y. 7 et5 sont premiers entre eux. 7 divise5ydonc 7 diviseyd"après le
théorème de Gauss. Ainsiy7kaveckentier.En reportant : 7x57kd"oùx5k.
Les solutionssont les couples (5k; 7k) oùkZ.
2. Résoudre une équation du typeaxbycdansZ2, avecaetbpremiers entre eux.
(a) Exemple :Déterminer les entiersxetytels que 5x7y1Comme 5 et 7 sont premiers entre eux, il existe d"après le théorème de Bezout deux nombresuetv
tels que : 5u7v1. Pour détermineruetv, on peut utiliser l"algorithme d"Euclide ou remarquer que 510771 donc on peut prendreu10 etv 7. Le couple (10 ;7) est une solution particulièrede cette équation.Alors : 5x7y15x7y510775(x10)7(y7).
5 divise 7(y7); 5 et 7 sont premiers entre eux. D"après le théorème de Gauss, on en déduit que 5
divisey7. Par conséquent :y75k,kZ, doncy75k. On reporte dans l"équation 5(x10)7(y7). On obtient : 5(x10)75kd"oùx107ksoitPage 7/
10TABLE DES MATIÈRES
x107k.Les solutionssont de la forme (107k;75k),kZ.
(b) Déterminer les entiersxetytels que 5x7y3. Comme510771, on a 5307213. Ainsi, (30 ;21) est une solutionparticulièrede cetteéquation.
On trouve alors les solutionsen utilisant la même méthode que ci-dessus.Les couples solutionssont (307k;215k).
3. Montrer la divisibilité par un produit d"entiers.
Exemple : Montrer queAn(n1)(n2) est divisible par 6 pour toutnentier. n(n1) est divisiblepar 2 ;n(n1)(n2)est divisiblepar 3, car il y atoujoursun multiplede 3 parmitrois nombres consécutifs. Aest divisible par 2 et par 3, donc divisible par 6 car 2 et 3 sontpremiers entre eux.V Petit théorème deFermat
Petit théorème de Fermat
pest un nombre premier,aest un entier tel quea2 et non divisible parp. Alorsapl1 est divisible parp, c"est-à-direap11 (modp).Démonstration :
pest un nombre premier,doncpest premier avec 1, 2, ...,p1 (sinonpadmettraitun diviseur positifautre que
1) et donc premier avec (p1)!
Sikest un entier tel que 1kp1 , alors le resterkde la division dekaparpest non nul. En effet, sipdiviseka, alorspdiviseacarpest premier aveck; or ceci est impossiblecar par hypothèse,an"est pas divisible parp. Sikest un entier distinct dek(par exemplekk) tel que 1kp1, alors les restesrketrkdes divisions respectives dekaetkaparpsont distincts. En effet, sirkrk, alorspdivisekakac"est-à-dire (kk)aavec 1kkp1, ce qui est impossiblecar an"est pas divisible parp.Ainsi, lesp1 restesr1,r2,...,rp1des divisions respectives dea, 2a, ..., (pl)aparpsont donc des entiers
naturels non nuls, strictement inférieursàpet tous distincts. Donc l"un de ces restes est égal à 1, l"autre à 2, ..., l"autre àp1.D"où en utilisantle produit des congruences :
a2a(p1)ar1r2rp1(modp) c"est-à- dire (p1)!ap1(p1)! (modp). Doncpdivise (p1)!ap1(p1)! c"est-à-dire (p1)!?ap11?. Orpest premier avec (pl)!, doncpdiviseap11 d"après le théorème de Gauss. EXEMPLE7 est premier et ne divise pas 12, donc 1261 est divisible par 7.Conséquence
pest un nombre premier,aest un entier supérieur ou égal à 2. Alorsapaest divisible parpc"est-à-direapa(modp).DÉMONSTRATION
apaa(ap11).Page 8/
10TABLE DES MATIÈRES
Siaest divisible parp, alorsa(ap11) est divisible parp.Sian" est pas divisible parp, alors, d"après le petit théorème de Fermat,ap11 est divisible parpet donc
a(apl1) est divisible parp.VI Plus petit commun multiple dedeux entiers
Étant donné un naturela, notonsM(a) l"ensemble des multiplesdeastrictement positifs.Définition
Le plus petit commun multiple des naturels non nulsaetbest le plus petit élément deM(a)M(b), ensemble des multiplescommuns strictement positifs deaet deb. On l"appelle aussi PPCM deaet deb.Remarques:
Le PPCM de deux entiers naturelsnon nuls est un entier au moins égal à 1.PPCM(a;a)a; PPCM(1 ;a)a.
Le seul multiplede 0 est 0, onc PPCM(a; 0)0.
Le PPCM de deux entiers quelconques est celui de leurs valeurs absolues.Propriété :
Soientaetbdeux entiers au moins égaux à 2. Le PPCM deaetbest égal au produit de tous les facteurs
premiers deaet de tous ceux deb, avec pour chacun d"eux l"exposant le plus grand de ceux qu"il a dans la
décomposition deaet deb.Démonstration :
Soitmle PPCM de deux naturelsaetbsupérieurs ou égaux à 2. Commemest un multiple dea, sa décomposi-
tionenfacteurspremierscomprendtouslesfacteurspremiersdeaavecunexposantau moinségal àcelui qu(ils
ont dans la décomposition dea; de même, elle comprend tous les facteurs premiers debavec un exposant au
moins égal à celui qu"ils ont dans la décompositiondeb.Ainsi,mcomprend tous les facteurs premiers deaet tous ceux deb, avec un exposant au mois égal à au plus
grand de ceux qu"il a dansaet dansb.