-
c Christophe Bertault - MPSI
Arithmtique des entiers relatifs
1 Division dans Z
1.1 Relation de divisibilit
Dfinition (Divisibilit, diviseur, multiple) Soient a, b Z. On
dit que a divise b, ou que a est un diviseur de b, ouque b est
divisible par a, ou que b est un multiple de a, sil existe k Z tel
que b = ak. Cette relation se note a|b.
Thorme (Proprits de la relation de divisibilit) Soient a, b, c,
d Z.
(i) La relation de divisibilit | est rflexive et transitive sur
Z, cest mme une relation dordre sur N, mais elle nestpas
antisymtrique sur Z car : a|b et b|a |a| = |b| a = b ou a = b.
(ii) Si d|a et si d|b, alors d(au+ bv) pour tous u, v Z.
(iii) Si a|b et si c|d, alors ac|bd. En particulier, si a|b,
alors ak|bk pour tout k N.
Dmonstration
(i) Dj prouv au chapitre Relations dordre .
(ii) Si d|a et d|b, alors a = dk et b = dl pour certains k, l Z,
donc au+ bv = d(ku+ vl) avec ku+ vl Z pourtous u, v Z, donc enfin
d
(au+ bv).(iii) Si a|b et c|d, alors b = ak et d = cl pour
certains k, l Z, donc bd = (ac)(kl) avec kl Z, bref ac|bd.
1.2 Relation de congruence modulo un entier
Dfinition (Relation de congruence modulo un entier) Soient n N
et a, b Z. On dit que a est congru b modulon si n
(b a), i.e. sil existe k Z tel que b = a+ kn. Cette relation se
note a b [n].
Explication Les relations de congruence gnralisent la relation
de divisibilit : n|a a 0 [n].
Thorme (Proprits de la relation de congruence) Soient a, a, b, b
Z et m,n N.
(i) Relation dquivalence : La relation [n] est rflexive,
symtrique et transitive.
(ii) Somme : Si a b [n] et si a b [n], alors a+ a b+ b [n].
(iii) Produit : Si a b [n] et si a b [n], alors aa bb [n].En
particulier, si a b [n], alors ak bk [n] pour tout k N.
(iv) Multiplication/division par un entier non nul : Si m 6= 0 :
a b [n] am bm [mn].
Dmonstration
(i) Rflexivit et symtrie sont immdiates, montrons seulement la
transitivit. Soient a, b, c Z. Si a b [n]et b c [n], alors n
(b a) et n(c b), donc par somme n(c a), i.e. a c [n].(ii) Si a b
[n] et a b [n], alors n
(b a) et n(b a), donc par somme n((b + b) (a + a)), i.e.a+ a b+
b [n].
(iii) Remarque : bb aa = b(b a) + a(b a). Du coup, si a b [n] et
a b [n], alors n(b a) et
n(b a), donc n(b(b a) + a(b a)), i.e. n(bb aa), ou encore aa bb
[n].
(iv) Enfin : a b [n] n(b a) m6=0 mnm(b a) am bm [mn].
1
-
c Christophe Bertault - MPSI
1.3 Division euclidienne
Thorme (Division euclidienne) Soient a Z et b N. Il existe un et
un seul couple (q, r) Z N tel que :
a = bq + r et 0 6 r 6 b 1 (ou encore : 0 6 r < b).
On appelle a le dividende de la division euclidienne de a par b,
b son diviseur, q son quotient et r son reste.
Par ailleurs : q =ab
et r a [b].
Explication
Le thorme de la division euclidienne est un rsultat dexistence
et dunicit : voil lessentiel.
En termes de congruences, le thorme de la division euclidienne
affirme simplement que tout entier relatif a est congrumodulo b un
unique entier r compris entre 0 et b 1. Par exemple, on peut
ramener lentier a = 123 lun desentiers 0, 1, 2, 3 ou 4 modulo b =
5. Prcisment : 123
a
= 5b
24q
+ 3r
, et donc 123 3 [5].
Dmonstration
Existence : Lide de la preuve est simple. Si a est positif, on
lui retranche b une fois, deux fois, trois fois. . .jusqu ce que a
ait presque compltement fondu, cest--dire jusquau moment o le
rsultat est comprisentre 0 et b 1. Si a est ngatif, on fait pareil
mais en ajoutant b au lieu de le retrancher.
Lensemble D ={a bk
}kZ
N est une partie non vide de N il contient a si a > 0 et a(1
b) si a < 0
donc possde un plus petit lment r. Pour un certain q Z, on peut
donc crire ceci : a = bq + r,et bien sr r > 0. Se peut-il quon
ait r > b ? Si ctait le cas, a b(q + 1) = r b serait un lment de
Dstrictement plus petit que r = minD impossible. Conclusion : 0 6 r
6 b 1.
Unicit : Soient (q, r) et (q, r) deux couples de la division
euclidienne de a par b. Aussitt |r r| 6 b 1,mais par ailleurs b(q
q) = r r.Supposons q 6= q. Dans ce cas |q q| > 1, donc : b 6 b|q
q| = |r r| 6 b 1, donc b 6 b 1 contradiction. Conclusion : q = q,
donc aussitt r = a bq = a bq = r.
Pour finir, comme 0 6 r = a bq < b, alors :a
b 1 < q 6
a
b, donc en effet q =
a
b
.
En pratique (Algorithme de la division euclidienne) On vient de
le voir, le couple (q, r) de la divisioneuclidienne de a par b se
calcule partir de a par une srie dadditions/soustractions. Hlas, si
le principe est simple, sa miseen uvre parat pnible. Pour diviser
1000 par 3, sommes-nous vraiment obligs deffectuer 333
soustractions ? Oui et non. Enralit, vous pratiquez sans le savoir
la division euclidienne depuis votre plus tendre enfance.
Tchons de le comprendre sur la division de 347 par 5. Dans un
premier temps, on retranche en apparence6 5 = 30 de 34, mais en
fait on retranche 60 5 = 300 de 347 puisque le 6 apparat comme
chiffre desdizaines dans le quotient. Dans un second temps, on
retranche 9 5 = 45 de 47. Au total, on a donc effectu69
soustractions mais en deux fois seulement : dabord 60, puis 9. Le
reste obtenu est 2.
3 4 7 3 0 (0)
4 7 4 5
2
5
6 9
Conclusion : diviser, cest soustraire. Pour un ordinateur, un
grand nombre de soustractions nest pas un
problme. Pour nous autres cerveaux cen est un. Nous compensons
en apprenant et en utilisant les tables de multiplication,car a
nous le faisons vite et bien. Cest grce aux tables de
multiplication que nous avons trouv les chiffres 6 et 9 duquotient
dans lexemple prcdent.
Exemple Soient x, y, z Z trois entiers solutions de lquation de
Fermat x3 + y3 = z3. Alors lun des entiers x, y ou z estdivisible
par 3.
En effet Raisonnons par labsurde en supposant que ni x ni y ni z
nest divisible par 3.
x [9] x2 [9] x3 [9]
1 1 1
2 4 8 1
4 16 2 8 1
5 4 16 2 8 1
7 2 4 8 1
8 1 1 1
Alors le reste de la division euclidienne de x par 9 est lun
desentiers 1, 2, 4, 5, 7, 8 on peut rejeter les cas 0, 3 et 6.
Etudionsun un ces diffrents cas dans le tableau ci-contre. Il en
ressortque x3 1 [9]. On montrerait de mme que y3 1 [9] et quez3 1
[9].
Or par hypothse x3 + y3 z3 [9]. A gauche on a modulo 9 soit1 + 1
= 2, soit 1 1 = 0, soit 1 + 1 = 0, soit 1 1 = 2, et droite 1.
Impossible !
2
-
c Christophe Bertault - MPSI
Exemple Le reste de la division euclidienne de 265362 par 7 est
2.
En effet La dmonstration de ce rsultat est trs longue si on
applique lalgorithme prcdent comme unrustre, car lentier 265362
possde prs de 20000 dcimales. Or on remarque que 23 8 1 [7]. Cest
lide-pharede cet exemple : dnicher, si elle existe, la premire
puissance de 2 congrue 1 modulo 7.
On divise alors 65362 par 3 : 65362 = 3 21787 + 1 et aussitt
265362 (23)21787 21 121787 2 2 [7].
2 Diviseurs et multiples communs
Rappelons toutes fins utiles que la relation de divisibilit est
une relation dordre sur N.
Dfinition (Diviseur commun, multiple commun) Soient a, b Z.
On appelle diviseur commun de a et b tout entier relatif qui est
la fois un diviseur de a et un diviseur de b.
On appelle multiple commun de a et b tout entier relatif qui est
la fois un multiple de a et un multiple de b.
Explication Dans le cas o a et b sont positifs, alors au sens de
la divisibilit :
lensemble des diviseurs communs positifs de a et b est aussi
lensemble des minorants de{a, b
},
lensemble des multiples communs positifs de a et b est aussi
lensemble des majorants de{a, b
}.
2.1 PGCD
Dfinition (PGCD) Soient a, b Z. On appelle plus grand commun
diviseur (ou PGCD) de a et b tout entier d Zsatisfaisant les deux
assertions :
d est un diviseur commun de a et b, tout diviseur commun de a et
b divise d.
Explication Rappelons que lorsque a et b sont positifs, alors au
sens de la divisibilit :
Borne infrieure = Plus grand minorant = Plus grand commun
diviseur = PGCD.
Existe-t-il toujours des PGCD ? Combien ? Les deux thormes qui
suivent sont essentiels. Nous les prouverons simultanment.
Thorme (Existence et unicit du PGCD) Soient a, b Z.
Existence : Lensemble des diviseurs communs positifs de a et b
possde un plus grand lment au sens de ladivisibilit not a b. Cet
entier positif a b est un PGCD de a et b mais on lappelle en fait
le PGCD de a et b.
Unicit : Le seul autre PGCD de a et b est lentier (a b).
Explication Par exemple, les diviseurs communs positifs de 12 et
18 sont 1, 2, 3 et 6, donc : 12 18 = 6. On ditque 6 est le PGCD de
12 et 18, mais en revanche que 6 est un PGCD de 12 et 18.
Thorme (Relations de Bzout) Soient a, b Z.Il existe des entiers
u, v Z tels que a b = au+ bv. Une telle dcomposition de a b est
appele une relation de Bzout.
$ $ $ Attention ! Les entiers u et v ne sont pas du tout
uniques.Par exemple, 4 6 = 2 et on a la fois 4 (1) + 6 1 = 2 et 4 2
+ 6 (1) = 2.
Dmonstration
Unicit : Si d et d sont deux PGCD de a et b, alors ils se
co-divisent par dfinition i.e. se divisentmutuellement donc |d| =
|d|.
3
-
c Christophe Bertault - MPSI
Existence et relations de Bzout : Si a = b = 0, alors 0 est un
diviseur commun positif de a et b,ncessairement le plus grand
puisque tout entier divise 0.
Supposons dsormais a 6= 0 ou b 6= 0. Comme alors |a|+ |b|
(aZ+bZ)N, lensemble (aZ+bZ)N est unepartie non vide de N donc
possde un plus petit lment d. Cet entier naturel non nul d scrit d
= au+ bvpour certains u, v Z tiens, une relation de Bzout. Il nous
reste montrer que d est un PGCD de a et b.
Pour montrer que d est un diviseur commun de a et b, il suffit
de le prouver pour a par symtrie desrles de a et b. La division
euclidienne de a par d scrit a = dq + r pour certains q, r Z avec 0
6 r < d.Dans ces conditions, r (aZ+ bZ) N car r = a dq = a (au+
bv)q = a(1 uq) bvq. Or r < d et dest le plus petit lment de (aZ+
bZ) N donc forcment r = 0. Cest bien dire que d divise a.
Ensuite, tout diviseur commun de a et b divise d puisque d = au+
bv.
La preuve prcdente a ceci dinconfortable quelle ne nous explique
pas comment calculer le PGCD ou les coefficients dunerelation de
Bzout. Deux algorithmes y pourvoient ci-dessous : lalgorithme
dEuclide et lalgorithme de Bzout.
Thorme (Ide fondamentale de lalgorithme dEuclide) Soient a Z et
b N. On note r le reste de la divisioneuclidienne de a par b. Alors
a b = b r.
Dmonstration Notons q le quotient de la division euclidienne de
a par b. Montrer que a b = b r revient montrer que ces deux entiers
positifs se divisent lun lautre.
Pour commencer, a b divise a et b, donc aussi b et r puisque r =
a bq, donc enfin a b divise b r.
De mme, b r divise b et r, donc aussi a et b puisque a = bq + r,
donc enfin b r divise a b.
En pratique (Algorithme dEuclide)
Soient a, b Z. Lalgorithme dEuclide va nous permettre de
calculer rapidement le PGCD de a et b. Tout dabord,a b = |a| si b =
0 et a b = |b| si a = 0. Ensuite, a b = |a| |b|. Enfin, videmment,
a b = b a. Nous pouvons doncsupposer que 0 < b 6 a. On dfinit
alors les entiers naturels r0, r1, r2 . . . de la faon suivante
:
Au dpart, on pose r0 = a et r1 = b.
Ensuite, pour k N, tant que rk+1 6= 0, on note rk+2 le reste de
la division euclidienne de rk par rk+1 en particulier, rk+2 <
rk+1.
A lissue de cette construction : r0 > r1 > r2 > r3 >
. . . > 0. Comme il nexiste quun nombre fini dentiers
naturelsentre 0 et r0, on obtient forcment rN = 0 pour un certain N
N
. Alors rN1 est le dernier reste non nul de lasuite r0, r1, r2 .
. . et en vertu de lide fondamentale de lalgorithme dEuclide :
a b = r0 r1 = r1 r2 = r2 r3 = . . . = rN1 rN = rN1 0 = rN1.
Conclusion : a b est le dernier reste non nul de la suite des
restes successifs r0, r1, r2 . . .
Appliquons cela sur un exemple simple : 1542 58 = 2. Il sagit
seulement deffectuer quelques divisions euclidiennes :1542 = 26 58
+ 34, 58 = 1 34 + 24, 34 = 1 24 + 10, 24 = 2 10 + 4, 10 = 2 4 + 2
et 4 = 2 2 + 0.
Dernier restenon nul
En pratique (Algorithme de Bzout) Nous prsenterons cet
algorithme sur un exemple, celui du PGCD de525 et 3080 et dune
relation de Bzout associe. On commence par mettre en uvre
lalgorithme dEuclide :
r0 3080 = 5
r1525 +
r2455 ,
r1525 = 1
r2455 +
r370 ,
r2455 = 6
r370 +
r435 ,
r370 = 2
r435 +
r50 .
Le dernier reste non nul est 35 : 5253080 = 35. Partons alors de
lavant-dernire division sous la forme
r435 =
r2455 6
r370 .
Nous allons y liminer progressivement r3 puis r2, nous aurons
ainsi exprim r4 = 35 en fonction de r0 = 3080 et r1 = 525.
525 3080 =
r435 =
r2455 6
r370 =
r2455 6 (
r1525 1
r2455 ) (on limine r3)
= 6
r1525 +7
r2455 = 6
r1525 +7 (
r0 30805
r1525 ) (on limine r2)
= 7
r0 308041
r1525 . La voil, notre relation de Bzout.
4
-
c Christophe Bertault - MPSI
Thorme (Proprits du PGCD) Soient a, b Z.
(i) Pour tout k Z : (ak) (bk) = |k| (a b).
(ii) Pour tout diviseur commun d 6= 0 de a et b :a
d
b
d=
a b
|d|.
Dmonstration
(i) Nous pouvons supposer k 6= 0. Posons = a b et = (ak) (bk).
Pour montrer que = |k|, il noussuffit de montrer que et k se
divisent lun lautre.
Pour commencer |a et |b, donc k|ak et k|bk, donc k|.
Ensuite k|ak et k|bk, donc k|, et donc = nk pour un certain n Z.
A prsent, nk = |ak etnk = |bk, donc n|a et n|b car k 6= 0. Ceci
montre que n|, et enfin = nk|k.
(ii) Daprs (i) : a b =(a
d d
)
(b
d d
)= |d|
(a
d
b
d
), do le rsultat.
2.2 Nombres premiers entre eux
Dfinition (Nombres premiers entre eux) Soient a, b Z. On dit que
a et b sont premiers entre eux si 1 est leur seuldiviseur commun
positif, i.e. si a b = 1.
Exemple 6 et 35 sont premiers entre eux car les diviseurs
positifs de 6 sont 1, 2, 3 et 6 et ceux de 35 sont 1, 5, 7 et
35.
En pratique
La remarque suivante est utile dans de trs nombreux exercices.
Soient a, b Z de PGCD d. On peut crire a = da et
b = db pour certains a, b Z. Alors a b =a
d
b
d=
a b
|d|= 1. Bref, a et b sont premiers entre eux.
Pour montrer que deux entiers sont premiers entre eux, on peut
toujours utiliser lalgorithme de Bzout. Nous verronsplus loin une
autre technique base de nombres premiers, parfois inutilisable mais
souvent plus pratique avec les petitsentiers que nous avons
lhabitude de manipuler.
Thorme (Thorme de Bzout) Soient a, b Z. Les assertions suivantes
sont quivalentes :
(i) a b = 1. (ii) Il existe deux entiers u, v Z tels que au+ bv
= 1.
Dmonstration Limplication (i) = (ii) est une simple relation de
Bzout dj prouve. Pour la rciproque(ii) = (i), supposons lexistence
de deux entiers u, v Z tels que au + bv = 1 et fixons d un diviseur
communpositif de a et b. Alors d
(au+ bv) = 1, donc d = 1. Comme voulu, a b = 1.
Thorme (Thorme de Gauss) Soient a, b, c Z. Si a|bc et si a b =
1, alors a|c.
Dmonstration Faisons lhypothse que a|bc et que ab = 1. Alors bc
= ak pour un certain k Z et au+bv = 1pour certains u, v Z daprs le
thorme de Bzout. Multiplions par c : acu+ bcv = c puis remplaons bc
parak : a(cu+ kv) = c. Comme voulu, a|c.
Thorme (Divisibilit par un produit) Soient a, b, n Z. Si a|n, si
b|n et si a b = 1, alors ab|n.
$ $ $ Attention ! Il est impratif de supposer a et b premiers
entre eux. Par exemple, pour a = b = n = 2, a et b divisentn mais
ab ne divise pas n.
Dmonstration Comme a|n, n = ak pour un certain k Z. Mais b|n
donc b|ak. Du coup, comme a b = 1, lethorme de Gauss montre que
b|k. Finalement comme voulu ab|ak = n.
5
-
c Christophe Bertault - MPSI
Thorme (Forme irrductible dun nombre rationnel) Soit r Q. Il
existe un et un seul couple (p, q) ZN tel
que r =p
qet tel que p q = 1. Cette criture r =
p
qest appele la forme irrductible de r.
Explication Une fraction dentiers est irrductible quand plus
aucune simplification nest possible entre le numrateuret le
dnominateur, sauf par 1.
Dmonstration
Unicit : Soient (p, q), (p, q) Z N. On suppose que r =p
q=
p
q, que p q = 1 et que p q = 1.
Comme pq = pq, q|pq. Mais p q = 1, donc q|q daprs le thorme de
Gauss, puis q|q par symtrie desrles de q et q, donc enfin |q| =
|q|. Comme q > 0 et q > 0, on a mme q = q. Il nous reste
diviserlgalit pq = pq par q = q et enfin p = p.
Existence : Par dfinition de r, r =a
bpour certains a, b Z avec b 6= 0. On peut toujours supposer
que
b est positif. Notons d le PGCD de a et b. Alors a = dp et b =
dq pour certains p Z et q N dont nous
savons quils sont premiers entre eux. Cest termin : r =a
b=
dp
dq=
p
q.
2.3 PPCM
Dfinition (PPCM) Soient a, b Z. On appelle plus petit commun
multiple (ou PPCM) de a et b tout entier m Zsatisfaisant les deux
assertions :
m est un multiple commun de a et b, tout multiple commun de a et
b est divisible par m.
Explication Rappelons que lorsque a et b sont positifs, alors au
sens de la divisibilit :
Borne suprieure = Plus petit majorant = Plus petit commun
multiple = PPCM.
Existe-t-il toujours des PPCM? Combien ?
Thorme (Existence et unicit du PPCM) Soient a, b Z. Il existe un
et un seul PPCM positif de a et b,not a b et appel le PPCM de a et
b. Le seul autre PPCM de a et b est lentier (a b).
En outre : |ab| = (a b) (a b).
Dmonstration
Unicit : Comme dans le cas des PGCD.
Existence : Si a = b = 0, 0 est le seul multiple de a et b donc
a et b admettent 0 pour unique PPCM.
Supposons dsormais a 6= 0 ou b 6= 0 et posons d = a b 6= 0. Nous
allons montrer queab
dest un PPCM de a
et b. Cela prouvera dun coup dun seul et lexistence dun PPCM de
a et b, et la formule |ab| = (ab) (ab).
Partons du fait que a = da et b = db pour certains a, b Z
premiers entre eux. Ensuite :ab
d= ba = ab.
Pour commencer,ab
dest un multiple commun de a et b car : a
ab = abd
et bba = ab
d.
Montrons ensuite que tout multiple commun de a et b est
divisible parab
d. Soit m un multiple
commun de a et b. Alors m = au = bv pour certains u, v Z, donc
ua = vb aprs division par d,donc a|vb. Comme a b = 1, a|v daprs le
thorme de Gauss. Bref, v = ak pour un certain k Z.
Concluons : m = bv = bak = kab
d, donc en effet
ab
d
m.
Exemple 12 18 =12 18
12 18=
12 18
6= 36.
6
-
c Christophe Bertault - MPSI
Thorme (Proprits du PPCM) Soient a, b Z.
Pour tout k Z : (ak) (bk) = |k| (a b).
Pour tout diviseur commun d 6= 0 de a et b :a
d
b
d=
a b
|d|.
3 Nombres premiers
Dfinition (Nombre premier, nombre compos) Soit p N. On dit que p
est premier si p 6= 1 et si les seuls diviseurspositifs de p sont 1
et p. On dit que p est compos si p 6= 1 et si p nest pas
premier.
Lensemble des nombres premiers est parfois not P.
Exemple Il nest pas inutile de connatre la liste des premiers
nombres premiers : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37. .
.
Le rsultat suivant est un thorme dexistence facile dmontrer.
Nous aurons ensuite un thorme dunicit, maisnettement plus difficile
obtenir.
Thorme Tout entier naturel non nul est un produit de nombres
premiers.
Explication Dans cet nonc lapidaire, on considre 1 comme le
produit de 0 nombre premier et tout nombre premiercomme le produit
d1 nombre premier soi-mme.
Dmonstration Par rcurrence forte. Un seul outil ici : la
relation de divisibilit et ses proprits lmentaires.
Initialisation : 1 nest divisible par aucun nombre premier, cest
le produit de zro dentre eux.
Hrdit : Soit n > 2. Faisons lhypothse que tout entier naturel
non nul strictement infrieur n est unproduit de nombres premiers.
Quen est-il de n ? Deux cas possibles : soit n est premier, soit n
est compos.Si n est premier, cest termin, il est produit de nombres
premiers. Et sil est compos ? Il scrit dans ce casn = ab o a et b
sont deux diviseurs positifs de n autres que 1 et n. Par hypothse
de rcurrence, a et b sontdes produits de nombres premiers, donc n
aussi par produit.
Thorme (Infinit de lensemble des nombres premiers) Lensemble P
des nombres premiers est infini.
Dmonstration Raisonnons par labsurde en supposant P fini et
notons donc p1, p2, . . . , pr la liste compltedes nombres
premiers. Posons ensuiteN = p1p2 . . . pr+1. Cet entierN , au moins
gal 2, est un produit de nombrespremiers daprs notre thorme
prcdent, donc divisible par pk pour un certain k J1, rK. En
particulier, pkdivise N p1p2 . . . pr = 1, i.e. pk = 1
contradiction.
Thorme La dcomposition dun entier naturel non nul en produit de
nombres premiers est unique lordre prs.
Dmonstration Par rcurrence forte. Contrairement la preuve simple
de lexistence dune dcomposition, lapreuve de son unicit requiert
massivement le thorme de Gauss.
Initialisation : 1 na aucun diviseur premier, donc videmment. .
.
Hrdit : Soit n > 2. Faisons lhypothse que la dcomposition de
tout entier naturel non nul strictementinfrieur n en produit de
nombres premiers est unique lordre prs. Quen est-il de n ?
Donnons-nousdeux dcompositions n = p11 p
22 . . . p
rr et n = q
11 q
22 . . . q
ss de n en produit de nombres premiers avec
p1 < p2 < . . . < pr et q1 < q2 < . . . < qs
et 1, 2, . . . , s N.
Se peut-il quon ait p1 6= q1 ? Dans ce cas, par exemple, p1 <
q1. Premiers et distincts, p1 et q1 sont premiersentre eux, donc
daprs le thorme de Gauss, p1
q111 q22 . . . qss . Bref, q111 q22 . . . qss = p1d pour un
certaind N quon peut lui-mme dcomposer en produit de nombres
premiers. Comme q111 q
22 . . . q
ss < n,
lhypothse de rcurrence nous autorise conclure de tout ceci que
p1 est lun des entiers q1, q2, . . . , qs, cequi est impossible car
p1 < q1 < q2 < . . . < qs.
7
-
c Christophe Bertault - MPSI
Conclusion : p1 = q1. Dans ces conditions, p111 p
22 . . . p
rr = q
111 q
22 . . . q
ss . Ce sont l deux dcomposi-
tions en produit de nombres premiers dun entier naturel non nul
strictement infrieur n. Par hypothsede rcurrence, r = s et pi = qi
et i = i pour tout i J1, rK, cest termin.
La dfinition suivante repose intgralement sur lexistence et
lunicit de la dcomposition de tout entier naturel nonnul en produit
de nombres premiers.
Dfinition (Factorisation premire, valuation p-adique) Pour tout
n N, il existe une et une seule famille presquenulle
(vp(n)
)pP
dentiers naturels i.e. dont tous les lments sont nuls sauf un
nombre fini dentre eux telle que :
n =pP
pvp(n). Cette dcomposition est appele la factorisation premire
de n.
Pour tout p P, vp(n) est appel la valuation p-adique de n.
Lentier pvp(n) est la plus grande puissance de p qui divise n.
Exemple Comme 60 = 22 3 5 : v2(60) = 2, v3(60) = 1, v5(60) = 1
et vp(60) = 0 pour tout p P \{2, 3, 5
}.
Thorme (Proprits des valuations p-adiques) Soient a, b N.
(i) Pour tout p P : vp(ab) = vp(a) + vp(b).
(ii) a divise b si et seulement si pour tout p P : vp(a) 6
vp(b).
(iii) a b =pP
pmin{vp(a),vp(b)} et a b =
pP
pmax{vp(a),vp(b)}.
En pratique
Daprs (ii) et (iii), on peut savoir si un entier en divise un
autre ou connatre le PGCD/PPCM de deux entiers quandon connat leurs
deux dcompositions en produit de nombres premiers. Cest trs
pratique, mais attention : dterminerla dcomposition en produit de
nombres premiers dun entier est trs long quand cet entier est un
grand nombre.Lalgorithme de la division euclidienne et lalgorithme
de Bzout sont incomparablement plus efficaces en gnral.
Vous utilisez la formule (iii) sur le PPCM depuis fort longtemps
quand vous rduisez une somme de fractions dentiers au
mme dnominateur. Quel est le plus petit dnominateur commun
de13
12+
7
30? Ce nest pas 12 30 mais 12 30. Et
comme 12 = 22 3 et 30 = 2 3 5 : 12 30 = 22 3 5 = 60. Bref
:13
12+
7
30=
5 13 + 2 7
60=
79
60.
Dmonstration
(i) Tout simplement :pP
pvp(ab) = ab =
pP
pvp(a)
pP
pvp(b) =
pP
pvp(a)+vp(b) et on conclut grce lunicit
de la dcomposition en produit de nombres premiers.
(ii) Si a|b, disons b = ak pour un certain k N, alors pour tout
p P : vp(b)(i)= vp(a) + vp(k) > vp(a).
Rciproquement, si vp(a) 6 vp(b) pour tout p P, alors
pvp(a)|pvp(b), donc a =
pP
pvp(a)
pP
pvp(b) = b.
(iii) Pour le PGCD, posons d =pP
pmin(vp(a),vp(b)). Pour montrer que d = a b, il nous suffit de
montrer que
a
d
b
d= 1. Soit p P. Si vp(a) 6 vp(b), alors vp(d) = vp(a) donc
vp
(a
d
)(i)= vp(a) vp(d) = 0, donc p ne
divise pasa
d. Si au contraire vp(a) > vp(b), alors p ne divise pas
b
d. Dans les deux cas, p ne divise pas la
foisa
det
b
d. En rsum,
a
det
b
dnont aucun diviseur commun premier, donc sont premiers entre
eux.
Pour le PPCM, remarquons que pour tous x, y R : x + y = min{x,
y
}+max
{x, y
}. Cette relation
est dun certain point de vue quivalente la relation : ab = (a b)
(a b) comme on le voit ci-aprs :
a b =ab
a b=pP
pvp(a)+vp(b)min{vp(a),vp(b)} =
pP
pmax{vp(a),vp(b)}.
Exemple Le PGCD de 600 et 740 est 20 = 22 5 car 600 = 23 3 52 et
740 = 22 5 37.
8
