La lecture à portée de main
Découvre YouScribe en t'inscrivant gratuitement
Je m'inscrisDécouvre YouScribe en t'inscrivant gratuitement
Je m'inscrisDescription
Sujets
Informations
Publié par | Oliv94 |
Publié le | 17 octobre 2013 |
Nombre de lectures | 426 |
Langue | Français |
Extrait
1
1.1
Plus grand
PGCD-
PPCM
diviseur commun
Dénition - Exemples
de deux entiers
Dénition 1Soientaetbdeux élément deZ.aZ+bZest un sous-groupe deZdonc il existe2N
tel queaZ+bZ=Z appelle. Onle plus grand diviseur commun deaetbet on note=pgcd(a; b)
ou=a^b.
Exemple 2On a vu dans le chapitre précédent pgcd(2;3) = 1et pgcd(10;25) = 5.
Remarque 3
Pour toutaetbdansZ, pgcd(a; b) =pgcd(b; a) =pgcd(jaj;jbj).
Soienta; b2Nalors
ajb()pgcd(a; b) =a
Démonstration.Le premier point découle du fait quejaj=aZ. Montrons le second on a
ajb()bZaZ()aZ+bZ=aZ()pgcd(a; b) =a
Proposition 4Soientaetb Soitdeux entiers relatifs.2N. Alors=pgcd(a; b)si et seulement
si
snieldtreitesdiviseudnvisieaeutdrbeaet debalorsddivise
Cela explique le nom de plus grand diviseur commun pour.
Démonstration.Notons=pgcd(a; b). On aaZZdoncja, de mêmebZZdoncjb.
Doncest un diviseur commun àaetb.
Soitdun diviseur deaetb, alorsaZdZetbZdZdoncaZ[bZdZdonc (par dénition
de la somme de deux sous-groupes)aZ+bZdZdoncZdZet doncdj.
Réciproquement soitun entier positif vériant :
lentierdiviseaetb
sidest un diviseur deaet debalorsddivise
Il faut montrer que=pgcd(a; b).
On aaZZetbZZdoncaZ+bZZetaZ+bZ=pgcd(a; b)Zdoncjpgcd(a; b).
Dautre partpgcd(a; b)est un diviseur deaet debdonc par dénition deon apgcd(a; b)j.
Exemple 5On a pgcd(4;6) = 2; pgcd(4;7) = 1
pgcd(57;711) = 7
pgcd(312;319) = 312
pgcd(2153852;293207) = 2938
1
1.2
Méthode de calcul : Algorithme dEuclide
Lemme 6Soitaetbdeux entiers naturels non nuls. Soitrle reste de la division euclidienne dea
parb. Alors pgcd(a; b) =pgcd(b; r).
Démonstration.On va montrer que lensemble des diviseurs deaetb:Div(a)\Div(b)et
lensemble des diviseurs debetr:Div(b)\Div(r)sont égaux, ce qui donnera le résultat.
Écrivons la division euclidienne deaparb, donca=bq+ravec0r < b. Comme
r=abq
si un nombreddiviseaetbalorsddiviser. DoncDiv(a)\Div(b)Div(b)\Div(r).
Réciproquement, siddivisebetralorsddivisea=bq+rdoncDiv(b)\Div(r)Div(a)\
Div(b).
Remarque 7Si lon a une expression du typeA=B+CouA+B+C= 0entre trois entiers
A; BetC. Alors tout nombre divisant deux de ces entiers divise automatiquement le troisième.
Proposition 8Algorithme dEuclide. Soitaetb construitdeux entiers naturels non nuls. On
par récurrence une suite dentiers naturels(rn)n2Nde la façon suivante :r0=a,r1=b,r2est le
reste de la division euclidienne der0parr1, et de proche en proche, tant quern6= 0,rn+1est égal
au reste de la division euclidienne dern1parrn. Alors il existe un entierNtel querN6= 0et
rN+1= 0 pgcd. Alors(a; b)est égal au dernier reste non nulrN.
Démonstration.Tant que les restes sont non nuls, on dénit une suite telle que0rn< rn1<
< r2< r1dtunu.etnobuAroécsaisemcttdenersltsireisranutitedentcdunesunodtigaslI.
nombre ni détapes on obtient alors un reste nul (on aNb utilisant le lemme précédent, on). En
obtient
pgcd(a; b) =pgcd(b; r2) =pgcd(r2; r3) = =pgcd(rN1; rN) =pgcd(rN;0) =rN
Exemple 9Soienta= 144etb= 84. On calcule
On a donc pgcd(144;84) = 12.
1.3
Relation de Bézout
144 = 184 + 60
84 = 160 + 24
60 = 224 + 12
24 = 212 + 0
r2= 60
r3= 24
r4= 12
r5= 0
Théorème 10Relation de Bézout.
Soientaetb Alorsdeux entiers relatifs. il existe des entiers relatifsuetvtels que
pgcd(a; b) =au+bv
Démonstration.Notons=pgcd(a; b)on a2Z=aZ+bZdonc=x+yoùx2aZet
y2bZ, donc il existeuetvtels que=au+bv.
2
Remarque 11Soit2N venons de montrer que si. Nous=pgcd(a; b)alors il existe un couple
dentiers(u; v)tel que=au+bv. La Par réciproque est fausse dans le cas général. exemple, pour
a= 4,b= 2et= 6, on a6 = 41 + 21et66=pgcd(4;2) = 2. Plus généralement, sil existe un
couple dentiers(u; v)tel qued=au+bvalors pgcd(a; b)divised.
Exemple 12Soienta= 63etb= 37. On calcule
63 = 371 + 26r2= 26
37 = 261 + 11r3= 11
26 = 112 + 4r4= 4
11 = 42 + 3r5= 3
4 = 31 + 1r6= 1
On part de la dernière relation et on remplace les restes en utilisant les formules de bas en haut de
la façon suivante :
1 = 431
1= 4(1142) =11 + 43
1 =11 + (26112)3 =711 + 263
1 =7(37261) + 263 =737 + 2610
1 =737 + (63371)10 =1737 + 1063
Finalement la relation de Bézout est :
10631737 = 1 =pgcd(63;37)
Départ
On a remplacér5
On a remplacér4
On a remplacér3
On a remplacér2
Proposition 13Soientaetb pour tout Alorsdeux entiers relatifs.k2N, pgcd(ka; kb) =kpgcd(a; b).
Démonstration.Sik= 0légalité est vériée. Supposonsk6= 0. SoitD=pgcd(ka; kb)et=
pgcd(a; b). Commediviseaetb,kdivisekaetkbdonckdiviseD.
Par ailleurs,kdivisekaetkbdonckdiviseD. Il existeq2Ztel queD=kq. Commekqdivise
kaetkb,qdiviseaetbdoncqdivise en déduit que. OnDdivisek.
Finalement on a donck=D.
Exemple 14pgcd(42;56) = 7pgcd(6;8) = 72 = 14.
2 Éléments premiers entre eux
Dénition 15On dit que les entiersaetbsont premiers entre eux si et seulement si pgcd(a; b) = 1
(noté aussia^b= 1).
Proposition 16Soientaetbentiers relatifs non tous les deux nuls. Soitdeux un diviseur positif
deaet deb. Il existea02Ztel quea=a0et il existeb02Ztel queb=b0. Alorsest le pgcd de
aetbsi et seulement sia0etb0sont premiers entre eux.
Démonstration.Le diviseur Commeest nécessairement non nul.a=a0etb=b0,
pgcd(a; b) =pgcd(a0; b0) =pgcd(a0; b0)
Par conséquent,pgcd(a; b) =()pgcd(a0; b0) = 1.
Théorème 17Théorème de Bézout.Les entiersaetbsont premiers entre eux si et seulement
sil existe deux entiers relatifsuetvtels que1 =au+bv.
3
Démonstration.Sipgcd(a; b) = 1alors il existe un couple dentiers(u; v)tel que1 =au+bv
(relation de Bézout). Réciproquement, supposons quil existe deux entiersuetvtels que1 =au+bv.
Soitdun diviseur deaet deb. Alorsddivise1doncjdj= 1ùo.Dpgcd(a; b) = 1.
Proposition 18Soitn2N,n2. Soita1; : : : ; andes entiers relatifs. Siaest premier avec chacun
desai(i= 1: : : n)alorsaest premier avec leur produit.
Démonstration.Commepgcd(a; a1) = 1, il existe des entiersu1etv1tels que1 =au1+a1v1.
De même, il existeu2etv2tels que1 =au2+a2v2. En multipliant ces deux termes, on obtient
1 =a(au1u2+u1a2v2+a1v1u2) +a1a2(v1v2)Doù.pgcd(a; a1a2) = 1 propriété est donc. La
vraie pourn= 2.
Supposons la propriété vraie à lordren. Soita1; : : : ; an+1n+ 1entiers premiers séparément avec
a utilisant lhypothèse de récurrence avec. Ena1; : : : ; an, on obtient queaest premier avec le produit
a1 an conclut . Onen utilisant la propriété avec les deux entiersa1 anetan+1.
Exemple 19Comme pgcd(3;5) = 1et pgcd(3;8) = 1, on a pgcd(3;40) = 1.
Corollaire 20Soientaetbdeux entiers relatifs. Siaetbsont premiers entre eux alors pour tout
n2Netp2N,anetbpsont premiers entre eux.
Théorème 21Théorème de Gauss.Soita,betc Sitrois entiers relatifs.adivisebcet siaetb
sont premiers entre eux alorsadivisec.
Démonstration.Commepgcd(a; b) = 1, il existe un couple dentiers(u; v)tels que1 =au+bv.
En multipliant cette égalité parc, on obtientc=a(cu) + (bc)v. Commeadivisebc,adivisec.
Proposition 22Soitn2N,n2. Soita1; : : : ; andes entiers relatifs premiers entre eux deux à
deux. Siaest divisible par chacun desai(i= 1: : : n)alorsaest divisible par leur produit.
Démonstration.La démonstration se fait par récurrence surn. Pourn= 2, il existe deux
entiersq1etq2tels quea=a1q1=a2q2. Donca2divisea1q1 comme. Maispgcd(a2; a1) = 1, on
obtient quea2diviseq