[PDF] Cours darithmétique 5 Corrigé des exercices. 75.

View - Download Cours darithmétique

Previous PDF

Next PDF

Cours d"arithm´etique

Premi`ere partie

PierreBornsztein

XavierCaruso

PierreNolin

MehdiTibouchi

D´ecembre 2004

Ce document est la premi`ere partie d"un cours d"arithm´etique ´ecrit pour les ´el`eves pr´e-

parant les olympiades internationales de math´ematiques. Le plan complet de ce cours est :

1. Premiers concepts

2. Division euclidienne et cons´equences

3. Congruences

4.´Equations diophantiennes

5. Structure deZ/nZ

6. Sommes de carr´es

7. Polynˆomes `a coefficients entiers

8. Fractions continues

Cette premi`ere partie traite les quatre premiers chapitres. Les quatre derniers chapitres forment quant `a eux la deuxi`eme partie de ce cours. Contrairement `a la seconde partie, cette premi`ere partie se veut le plus ´el´ementaire

possible. Les notions abstraites, souvent plus difficiles `a assimiler, mais qui clarifient les id´ees

lorsqu"elles sont comprises, ne sont ´evoqu´ees que dans la seconde partie. Nous conseillons au lecteur de bien maˆıtriser ce premier tome avant de passer `a la lecture du second.

Les notions et les th´eor`emes introduits ici sont g´en´eralement tout `a fait suffisants pour

traiter les exercices propos´ees aux olympiades internationales de math´ematiques.

Vous trouverez `a la fin de chaque chapitre une s´erie d"exercices de difficult´e variable mais

indiqu´ee par des ´etoiles

1. Toutes les solutions sont rassembl´ees `a la fin du document.

Nous vous souhaitons bon apprentissage et bonne lecture. 1 Plus nous avons jug´e l"exercice difficile, plus le nombre d"´etoiles est important. 1

Liste des abbr´evations :

AMM American Mathematical Monthly

APMO The Asian Pacific Mathematics Olympiad

CG Concours g´en´eral

OIM Olympiades Internationales de Math´ematiques

SL Short List

TDV Tournoi Des Villes

Liste des notations :

?ensemble vide

Nensemble des entiers naturels (positifs ou nuls)

N ?ensemble des entiers naturels strictement positifs

Zensemble des entiers relatifs

Qensemble des nombres rationnels

Rensemble des nombres r´eelsPsymbˆole de sommation2Qsymbˆole de produit3 a|b adiviseb [x]partie enti`ere dex {x}partie d´ecimale dex pgcdplus grand commun diviseur a?bpgcd(a,b) ppcmplus petit commun multiple a?bppcm(a,b) a≡b(modN)aest congru `abmoduloN pun nombre premier v p(n)valuationp-adique den d(n)nombre de diviseurs positifs den

σ(n)somme des diviseurs positifs den

?fonction indicatrice d"Euler s b(n)somme des chiffres denen baseb π(n)nombre de nombres premiers inf´erieurs ou ´egaux `an a n...a0b´ecriture en baseb n!factorielle den:n! = 1×2× ··· ×n C k ncoefficient binomial : Ck n=n! k!(n-k)! u n≂vnles suites(un)et(vn)sont ´equivalentes 2 Une somme index´ee par l"ensemble vide est ´egale `a0.

3Un produit index´e par l"ensemble vide est ´egale `a1.

2

Table des mati`eres

1 Premiers concepts 4

1.1 Divisibilit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2 Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.3 Valuationp-adique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.4 Quelques fonctions arithm´etiques . . . . . . . . . . . . . . . . . . . . . . . . 14

1.5 Nombres rationnels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2 Division euclidienne et cons´equences 24

2.1 Division euclidienne et d´ecomposition en baseb. . . . . . . . . . . . . . . . 24

2.2 Algorithme d"Euclide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.3 Algorithme d"Euclide ´etendu et th´eor`eme de B´ezout . . . . . . . . . . . . . . 28

2.4 Lemme de Gauss et cons´equences . . . . . . . . . . . . . . . . . . . . . . . . 29

2.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3 Congruences 37

3.1 D´efinition, premi`eres propri´et´es . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.2 Crit`eres de divisibilit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.3 Ordre d"un ´el´ement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.4 Th´eor`eme chinois . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.5 Congruences modulop. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.6 Congruences modulopn. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.7 Coefficients binomiaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

3.8 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

4

´Equations diophantiennes 56

4.1 Quelques r´eflexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

4.2 Utilisation des congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

4.3 Descente infinie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

4.4´Equations de degr´e2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

4.5´Equations de degr´e3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

4.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

5 Corrig´e des exercices 75

5.1 Exercices de"Premiers concepts». . . . . . . . . . . . . . . . . . . . . . . 75

5.2 Exercices de"Division euclidienne et cons´equences». . . . . . . . . . . . . 103

5.3 Exercices de"Congruences». . . . . . . . . . . . . . . . . . . . . . . . . . 118

5.4 Exercices de"´Equations diophantiennes». . . . . . . . . . . . . . . . . . . 143

3

1 Premiers concepts

Cette section, comme son nom l"indique, pr´esente le concept de base de l"arithm´etique,

`a savoir la divisibilit´e. On introduit ensuite les nombres premiers ce qui permet d"´enoncer le

th´eor`eme fondamental de l"arithm´etique (c"est-`a-dire la d´ecomposition en facteurs premiers)

dans lequel les nombres premiers jouent le rˆole de briques ´el´ementaires pour la fabrication

des nombres.

1.1 Divisibilit´e

D´efinition 1.1.1Siaetbsont deux entiers, on dit queadiviseb, ou quebestdivisible para, s"il existe un entierqtel queb=aq. On dit encore queaest undiviseurdeb, ou que best unmultipledea. On le notea|b.

Propri´et´es

+Siaetbsont deux entiers avecb?= 0,bdiviseasi et seulement si la fractiona b est un entier. +Tous les entiers divisent0, et sont divisibles par1. +Un entiernest toujours divisible par1,-1,net-n. +Sia|b, etb|c, alorsa|c. +Sia|b1,b2,...,bn, alorsa|b1c1+b2c2+...+bncn, quels que soient les entiersc1,c2,...,cn. +Siadivisebetb?= 0, alors|a|6|b|. +Siadivisebetbdivisea, alorsa=±b. +Siaetbsont deux entiers tels quean|bnpour un entiern>1, alorsa|b.

Toutes les propri´et´es list´ees pr´ec´edemment sont imm´ediates, `a l"exception de la derni`ere dont

la d´emonstration n"est pas triviale sans bagage arithm´etique. Une preuve possible consiste

`a utiliser la caract´erisation de la divisibilit´e par les valuationsp-adiques (voir paragraphe

1.3). Voyons imm´ediatement deux exercices qui montrent comment on peut manipuler la no- tion de divisibilit´e :

Exercice

: Soientxetydes entiers. Montrer que2x+ 3yest divisible par7si et seulement si5x+ 4yl"est.

Solution

: Supposons que7divise2x+3y, alors il divise6(2x+ 3y)-7(x+ 2y) = 5x+4y. R´eciproquement si7divise5x+ 4y, il divise6(5x+ 4y)-7(4x+ 3y) = 2x+ 3y.⎷

Exercice

: Pour quels entiersnstrictement positifs, le nombren2+ 1divise-t-iln+ 1?

Solution

: Sin2+1divisen+1, comme tout est positif, on doit avoirn2+16n+1, ce qui n"est v´erifi´e que pourn= 1. On v´erifie ensuite quen= 1est bien solution.⎷ 4

Parties enti`eres

D´efinition 1.1.2Sixest un r´eel, on appellepartie enti`eredex, et on note[x], le plus grand entier inf´erieur ou ´egal `ax. Ainsi, on a[x]6x <[x] + 1. Remarque.On d´efinit aussi lapartie d´ecimaledex, comme la diff´erencex-[x]. La partie

d´ecimale dexest souvent not´ee{x}. Cette notion est moins utilis´ee que la notion de partie

enti`ere et les conventions de notations sont moins usuelles `a ce propos : lors d"un exercice,

ou d"un expos´e, il est toujours de bon goˆut de commencer par pr´eciser les notations qui vont

ˆetre employ´ees par la suite.

Notons qu"il fautˆetre prudent avec les nombres n´egatifs : autant pour les nombres positifs, la partie enti`ere correspond au nombre auquel on retire ses chiffres apr`es la virgule, autant

ce n"est pas le cas pour les nombres n´egatifs. En effet, si on suit la d´efinition, on voit par

exemple que[-3,5] =-4.

Les parties enti`eres et parties d´ecimales ob´eissent `a quelques propri´et´es ´el´ementaires que

nous listons ci-dessous :

Propri´et´es ´el´ementaires

+On a toujoursx= [x] +{x}. +Pour tout r´eelx, on ax-1<[x]6x +Sixest entier,[x] =xet{x}= 0. Et r´eciproquement si l"une des deux ´egalit´es est v´erifi´ee, alorsxest entier. +[-x] =-[x]-1sauf sixest entier, auquel cas[-x] =-[x]. +Sixetysont deux r´eels,[x] + [y]6[x+y]6[x] + [y] + 1. +Sim >0est un entier, alors il y a exactement[x m ]multiples demcompris entre1et x.

La d´emonstration des propri´et´es consiste en de simples manipulations de la d´efinition et

principalement de l"in´egalit´e[x]6x <[x] + 1. Elle est laiss´ee au lecteur. On remarquera que tr`es souvent les questions faisant intervenir des parties enti`eres se r´esument `a de la manipulation d"in´egalit´es comme le montre par exemple l"exercice suivant :

Exercice

: On suppose que4n+ 2n"est pas le carr´e d"un nombre entier. Montrer que pour n>0, on a :h⎷ n+⎷ n+ 1i =h⎷

4n+ 2i

Solution

: Remarquons tout d"abord que l"on a toujours l"in´egalit´e : n+⎷ n+ 1<⎷ 4n+ 2 En effet, en ´elevant au carr´e, on a `a comparer2n+ 1 + 2⎷ n

2+net4n+ 2, soit2⎷

n 2+n

et2n+ 1et l"in´egalit´e devient ´evidente apr`es une nouvelle ´el´evation au carr´e.

Il reste `a prouver qu"il n"existe aucun entierktel que : n+⎷ n+ 1< k6⎷ 4n+ 2 5 soit, encore en ´elevant au carr´e qu"il n"existe aucun entierktel que :

2n+ 1 + 2⎷

n

2+n < k264n+ 2

Mais il est clair que4n+ 1<2n+ 1 + 2⎷

n

2+net un tel entierkv´erifiraita fortiori

4n+ 1< k264n+ 2. Commekest entier, il vient forc´ementk2= 4n+ 2, mais cela n"est

pas possible puisque l"on a suppos´e que4n+ 2n"´etait pas le carr´e d"un entier.⎷ Remarque.En fait,4n+ 2n"est jamais le carr´e d"un entier. En effet, le nombre4n+ 2est

pair, et s"il ´etait le carr´e d"un entier, il serait le carr´e d"un entier pair. Mais alors4n+ 2

devrait ˆetre un multiple de4, ce qui n"est, `a l"´evidence, pas le cas. L"´egalit´e pr´ec´edente de

parties enti`eres est donc valable pour tout entiern>1, sans hypoth`ese suppl´ementaire. Une propri´et´e amusante des parties enti`eres qui montre ´egalement que parfois (souvent)

les manipulations d"in´egalit´es ne sont pas faciles est le th´eor`eme de Beatty que voici :

Th´eor`eme 1.1.3 (Beatty)Soientαetβdeux r´eels strictements positifs. On noteSα

(resp.Sβ) l"ensemble des entiers strictement positifs qui s"´ecrivent sous la forme[nα](resp.

[nβ]) pour un certain entiern. Les ensemblesSαetSβforment une partition deN?si, et seulement siαetβsont irrationnels et v´erifient 1 +1 = 1. D´emonstration.Commen¸cons par supposer queαetβsont des irrationnels v´erifiant1 1 = 1. Soitkun entier strictement positif. Il est dans l"ensembleSαsi et seulement s"il existe un entierntel que : nα-1< k < nα

l"in´egalit´e de droite ´etant stricte carαest suppos´e irrationnel. L"´equation se transforme et

donne :k ff

¡ n ¡k

ff +1 ff ,k ff +1

£contient un entier. De mˆeme

k?Sβsi et seulement si l"intervallei k fi ,k fi +1 h contient un entier. ff ,k ff + 1£est de longueur1et ses bornes sont irrationnelles, donc il contient un et un seul entiern. Sin ¡ k+ 1-n fi +1

et donck?Sβ. Sik´etait `a la fois ´el´ement deSαet deSβ, il y aurait un entier dans

ff ,k ff +1

£et un dans l"intervallei

k fi ,k fi +1 h et donc par le mˆeme raisonnement ff ,k ff + 1£, ce qui n"est pas possible. 6 R´eciproquement, supposons queSαetSβforment une partition deN?. Consid´erons un entierkstrictement positif. Il y a£k ff y ah k fi i entiers dans{1,...,k}qui sont dansSβ. Du fait de la partition, il vient : ·k ff +·k fi =k pour toutk. En faisant tendrekvers l"infini, il vient : 1 +1 = 1 ce qui d´emontre la deuxi`eme condition. Supposons maintenant par l"absurde queαsoit rationnel. Alors il en est de mˆeme deβ d"apr`es la relation pr´ec´edente.´Ecrivonsα=a b etβ=c d . L"entieracest ´el´ement deSα(en prenantn=bc) et ´egalement ´el´ement deSβ(en prenantn=ad), ce qui est contradictoire.

PgcdetPpcm

Ce paragraphe introduit les d´efinitions depgcdetppcmqui sont deux notions fonda-

mentales de l"arithm´etique et en donne leurs principales propri´et´es. Les d´emonstrations qui

ne sont pas ´evidentes sont report´ees au chapitre 2 et seront vues comme cons´equence de la

division euclidienne. D´efinition 1.1.4Soientaetbdeux entiers non tous deux nuls. L"ensemble des diviseurs communs deaet debest fini et non vide, il poss`ede donc un plus grand ´el´ement appel´eplus grand commun diviseur(pgcd) deaetbet not´epgcd(a,b). Lorsquepgcd(a,b) = 1, on dit queaetbsontpremiers entre eux. De mˆemeaetbposs`edent un plus petit multiple commun positif, on l"appelle leplus petit commun multiple(ppcm) deaet debet on le noteppcm(a,b).

Propri´et´es

+Sid=pgcd(a,b), alorsndiviseaetbsi et seulement sindivised. +Sim=ppcm(a,b), alorsnest un multipleaet debsi et seulement sinest un multiple dem. +Sia,betnsont des entiers non nuls etn >0, alorspgcd(na,nb) =npgcd(a,b). Si de plusndiviseaetb, alorspgcd¡a n ,b n

¢=1

n pgcd(a,b). +Sid=pgcd(a,b), on peut ´ecrirea=da?etb=db?poura?etb?des nombres premiers entre eux. +Siaetbsont des entiers, l"´egalit´epgcd(a,b) =pgcd(a,a+b)est toujours v´erifi´ee lorsqu"elle a un sens. En particulier, lepgcdde deux nombres cons´ecutifs est1, et plus g´en´eralement, lepgcddeaet dea+nest un diviseur positif den. +Plus g´en´eralement, six,y,a,b,a?etb?sont des entiers alors : En particulier si|ab?-ba?|= 1, alorspgcd(x,y) =pgcd(ax+by,a?x+b?y). 7

Ces propri´et´es sont ´el´ementaires. Souvent, pour prouver l"´egalit´e de deuxpgcd, on

montre que chacun despgcddivise l"autre. C"est la m´ethode que l"on utilise majoritai- rement ici. Expliquons comment on proc`ede pour montrer qu"unpgcden divise un autre en donnant un preuve de la derni`ere propri´et´e qui est la plus difficile : notonsd=pgcd(x,y). Alorsddivisexetyet donc il diviseax+byeta?x+b?ypuis leurpgcd. De mˆeme, soit d ?=pgcd(ax+by,a?x+b?y), alorsd?diviseb?(ax+by)-b(a?x+b?y) = (ab?-ba?)xet a ?(ax+by)-a(a?x+b?y) = (a?b-b?a)y. Ainsid?divisepgcd((ab?-ba?)x,(a?b-b?a)y) = |ab?-ba?|pgcd(x,y), ce qui conclut. Citons ´egalement des r´esultats classiques et souvent assez utiles :

Propri´et´es

+Siaetbsont des entiers non nuls alorspgcd(an,bn) =pgcd(a,b)npour tout entier n>0. +Sia,betcsont des entiers non nuls, on a : pgcd(a,ppcm(b,c)) =ppcm(pgcd(a,b),pgcd(a,c)) ppcm(a,pgcd(b,c)) =pgcd(ppcm(a,b),ppcm(a,c)) +Th´eor`eme de B´ezout.Siaetbsont des entiers premiers entre eux, alors il existe des entiersuetvtels queau+bv= 1. +Lemme de Gauss.Si des entiersa,betcsont tels queadivisebcetapremier avecb, alorsadivisec. +Si deux entiers premiers entre euxaetbdivisentn, alors le produitabdivise ´egalement n.

Ces propri´et´es sont plus difficiles. Les deux premi`eres r´esultent par exemple directement de

l"expression depgcd(a,b)en fonction de la d´ecomposition en facteurs premiers deaet de b(voir la partie surle th´eor`eme fondamental de l"arithm´etiquedans le paragraphe 1.2). Les

autres r´esultent des propri´et´es de la division euclidienne que nous ´etudions au chapitre 2.

Leur d´emonstration est donc report´ee aux paragraphes 2.3 et 2.4. Donnons `a pr´esent deux exercices qui montrent comment l"on peut manipuler les faits pr´ec´edents :

Exercice

: On d´efinit len-i`emenombre de Fermatpar la formuleFn= 22n+1. Montrer que lesFnsont deux `a deux premiers entre eux.

Solution

: On remarque que : F n+1-2 = 22n+1-1 =¡22n-1¢¡22n+ 1¢ 2

2n-1-1´³

2

2n-1+ 1´¡22n+ 1¢=FnFn-1···F0

Soitdun diviseur commun deFnetFm. Supposons par exemplen < m. D"apr`es la formule pr´ec´edente, commeddiviseFn, il diviseFm-2et donc2. LesFnsont clairement impairs, la seule solution est d"avoir|d|= 1. Ceci prouve queFnetFmsont premiers entre eux.⎷ 8 Exercice: Soientaetbdes nombres premiers entre eux. Montrer queabeta+bsont aussi premiers entre eux.

Solution

: Soitdun diviseur commun deabet dea+b. Alorsddivisea(a+b)-ab=a2. De

mˆemeddiviseb2. D"apr`es une des propri´et´es pr´ec´edentes, les entiersa2etb2sont premiers

entre eux. Ainsid=±1, ce qui conclut.⎷

1.2 Nombres premiers

D´efinition et exemples

Comme nous l"avons dit dans l"introduction de cette partie, les nombres premiers sont

les briques ´el´ementaires pour fabriquer les nombres. De fa¸con plus pr´ecise et moins imag´ee,

on a la d´efinition suivante : D´efinition 1.2.1Un entiern >0est ditpremiers"il est diff´erent de1et s"il n"admet aucun diviseur positif diff´erent de1etn. Un tel diviseur est appel´ediviseur strict. Un nombre qui n"est pas premier est appel´enombre compos´e. Par d´efinition, donc,1n"est pas premier. C"est une simple convention mais elle s"av`ere utile

pour l"´enonc´e des th´eor`emes comme vous allez (peut-ˆetre) vous en rendre compte. Les entiers

2,3,5,7,11,13sont les premiers nombres premiers. Le nombre6, n"est par contre pas premier

car on peut ´ecrire6 = 2×3(et donc2(ou3) est un diviseur strict de6). Proposition 1.2.2Soitn >1un entier. Son plus petit diviseurd >1est un nombre premier. Si de plusnest compos´e, alorsd6⎷ n. D´emonstration.Supposons quedne soit pas premier. Alors par d´efinition, il existe un diviseur strictd?ded. Mais alorsd?divisen,d?>1etd?< d, ce qui contredit la minimalit´e ded. Commeddivisen, on peut ´ecriren=dd?. On ad >1et commenn"est pas premier, d < n. Ainsid?est un diviseur denstrictement sup´erieur `a1. Par minimalit´e ded, on obtientd?>det doncn>d2puis finalementd6⎷

Remarque.On d´eduit de la propri´et´e pr´ec´edente que pour tester si un entiern >1est

premier, il suffit de regarder s"il est divisible ou non par un des entiers compris entre2et⎷ n. Par exemple, pour v´erifier que37est premier, il suffit de voir qu"il n"est divisible ni par

2, ni par3, ni par4, ni par5, ni par6. On aurait ´egalement pu ´eviter les divisions par4et

6si on savait par avance que ces nombres ´etaient compos´es.

La remarque pr´ec´edente nous am`ene `a la m´ethode suivante, appel´eecrible d"´Eratosth`ene

pour lister tous les nombres premiers entre1etn: on ´ecrit `a la suite les uns des autres tous les entiers compris entre2etn. On entoure le premier2et on barre tous ses multiples (i.e. tous les nombres pairs). On entoure ensuite le prochain nombre non barr´e (en l"occurrence3) et on barre tous ses multiples. Ainsi de suite jusqu"`a⎷ n. On entoure finalement les nombres non barr´es. Les nombres entour´es sont alors exactement les nombres premiers compris entre 1etn. 9 Le th´eor`eme fondamental de l"arithm´etique On en arrive `a pr´esent au th´eor`eme fondamental de l"arithm´etique. Nous aurons besoin pour la d´emonstration du lemme suivant (qui sera d´emontr´e dans le paragraphe 2.4) : Lemme 1.2.3Si un nombre premierpdivise le produita1···an, alors il divise l"un desai. Th´eor`eme 1.2.4 (D´ecomposition en facteurs premiers)Tout entiern>1se d´ecom- pose d"une et d"une seule mani`ere en un produit de nombres premiers. Autrement dit, pour tout entiern>1, il existe des nombres premiers deux `a deux distinctsp1,...,pket des

entiers strictement positifsα1,...,αk, uniquement d´etermin´es `a l"ordre pr`es, tels que :

n=pα11pα22···pαkk Remarque.Le th´eor`eme reste bien vrai pourn= 1: il faut choisirk= 0, le produit d"aucun entier ´etant par convention ´egal `a1. D´emonstration.Commen¸cons par l"existence de la d´ecomposition. On raisonne par r´ecur- rence surn. Commen¸cons (pour ne pas perturber le lecteur) `an= 2qui s"´ecrit comme un produit de nombres premiers, ´etant lui-mˆeme premier. Soitn>3un entier. Supposons que tous les entiers strictement inf´erieurs `ans"´ecrivent comme le stipule le th´eor`eme et montrons que la conclusion subsiste pour l"entiern. Il y a deux cas : soitnest premier, soit il ne l"est pas. Le premier cas est vite r´egl´e :npremier s"´ecrit bien comme un produit de nombres premiers. Supposons donc quensoit compos´e. Ainsi, il s"´ecritn=dd?avec26d < net26d?< n. Les entiersdetd?rel`event de l"hypoth`ese de r´ecurrence et on peut ´ecrire : d=p1p2···pk d ?=p?1p?2···p?k? pour des nombres premierspietp?i. Il ne reste plus qu"`a effectuer le produit pour conclure. Passons d´esormais `a l"unicit´e. Supposons que : p

1p2···pk=p?1p?2···p?k?

pour certains nombres premierspietp?i. On veut montrer quek=k?et que lespisont ´egaux auxp?i`a l"ordre pr`es. Raisonnons par l"absurde. Parmi les contre-exemples dont on vient de supposer l"existence, il en est au moins un pour lequelmin(k,k?)est minimal. Consid´erons un de ceux-ci.

Le nombre premierp1divise le produitp?1p?2···p?k?donc d"apr`es le lemme 1.2.3, il divisep?ipour un certain entieri. Or, les diviseurs dep?i(qui est premier) ne sont que1etp?i. Comme

p

1?= 1, il ne reste plus que la possibilit´ep1=p?i=p. On peut alors simplifier l"´egalit´e :

p

1p2···pk=p?1p?2···p?k?

en divisant parp, obtenant ainsi un contre-exemple plus petit. C"est une contradiction et

Le th´eor`eme pr´ec´edent permet de d´ecrire explicitement les diviseurs d"un entierndont

on connaˆıt la d´ecomposition en facteurs premiers. 10 Proposition 1.2.5Si la d´ecomposition en facteurs premiers de l"entiern>1estn= p

α11pα22···pαkk, alors les diviseurs positifs densont les entiers de la formepβ11pβ22...pβkk, avec

06βi6αipour tout16i6k.

Comme cons´equence, on obtient une expression dupgcdet duppcmde deux entiers lorsqu"on connaˆıt leur d´ecomposition en facteurs premiers. Pr´ecis´ement, si : a=pα11pα22···pαkk b=pβ11pβ22···pβkk o`u lespisont deux `a deux distincts, mais lesαietβisont ´eventuellement nuls, on a : pgcd(a,b) =pmin(α1,β1)

1pmin(α2,β2)

2···pmin(αk,βk)

k ppcm(a,b) =pmax(α1,β1)quotesdbs_dbs7.pdfusesText_13

[PDF] arithmétique dans z exo7

[PDF] exercice arithmétique mpsi corrigé

[PDF] algebre 2 structures polynômes et fractions rationnelles

[PDF] cours arithmétique

[PDF] arithmétique dans z cours mpsi

[PDF] suite arithmétique

[PDF] exercice code barre terminale s

[PDF] exercices d arithmétique corrigés

[PDF] arithmétique exercices corrigés pdf

[PDF] exo7 arithmétique

[PDF] rencontre arles 2017

[PDF] programme arles 2017

[PDF] luma arles

[PDF] forum d'arles

[PDF] arles monuments romains