[PDF] Cinématique des fluides
[PDF] CHAPITRE I TRIGONOMETRIE
[PDF] E = m c2 l 'équation de Poincaré, Einstein et Plan
[PDF] Démonstrations exigibles au bac - Math France
[PDF] SECOND DEGRÉ - Maths-et-tiques
[PDF] SECOND DEGRÉ - Maths-et-tiques
[PDF] Démonstrations combinatoires
[PDF] 1 Démonstrations du formulaire de trigonométrie -
[PDF] Primitives et intégrales
[PDF] Charlemagne sur Internet - Statim
[PDF] ROC - Math France
[PDF] III- Raisonnement par récurrence
[PDF] Raisonnement par récurrence - Math France
[PDF] Planche no 2 Raisonnement par récurrence : corrigé
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.