[PDF] [PDF] Arithmétique

[PDF] Cours darithmétique

Cette section, comme son nom l'indique, présente le concept de base de l' arithmétique, `a savoir la divisibilité On introduit ensuite les nombres premiers ce qui 

[PDF] Cours darithmétique

L'arithmétique est l'étude des propriétés des nombres entiers, appelés aussi entiers Théorème 1 20 Théorème fondamental de l'arithmétique Tout entier a > 1 

[PDF] ARITHMETIQUE

Lise Jean-Claude - Cours d'arithmétique -Terminale S 1/16 ARITHMETIQUE Partie des mathématiques étudiant les propriétés élémentaires des nombres 

[PDF] Résumé du cours darithmétique

Résumé du cours d'arithmétique Les ensembles N et Z N = {0, 1, 2, 3, } est l' ensemble des entiers naturels (entiers positifs) Z = { , −2, −1, 0, 1, 2, 3,

[PDF] Cours darithmétique

L'arithmétique est l'étude des propriétés des nombres entiers, appelés aussi entiers Théorème 1 20 Théorème fondamental de l'arithmétique Tout entier a > 1 

[PDF] Arithmétique dans Z - Maths-francefr

(théorème fondamental de l'arithmétique) Tout entier naturel supérieur ou égal à 2 se décompose de manière unique, à l'ordre près des facteurs, en produit de

[PDF] Arithmétique - Maths-francefr

Arithmétique (enseignement de spécialité) I Divisibilité dans Z 1) Définition de la divisibilité dans Z Définition 1 Soient a et b deux entiers relatifs tels que a 

[PDF] Arithmétique - Licence de mathématiques Lyon 1

Maths en L˙1gne Arithmétique UJF Grenoble 1 Cours 1 1 Nombres premiers On appelle entier (ou entier relatif, c'est-à-dire positif ou négatif) tout élément de

[PDF] ARITHMETIQUE Exercice 1 - Licence de mathématiques Lyon 1

Arithmétique Pascal Lainé ARITHMETIQUE Exercice 1 : Étant donnés cinq nombres entiers Arithmétique Pascal Lainé 7 Si un entier divise deux entiers,  

[PDF] Arithmétique

13 fév 2013 · On a donc bien pour tout n ⩾ 1 : n divise a et 0 si et seulement si n divise sa + t × 0 6 Page 8 Maths en Ligne Arithmétique UJF Grenoble Soit 

[PDF] CHAPITRE 1 ATMOSPHÈRE, HYDROSPHÈRE, CLIMATS : DU

[PDF] Energie et cellule vivante - Blogpeda

[PDF] Chapitre III LA SPECTROSCOPIE INFRAROUGE

[PDF] Chapitre III-Spectroscopie d 'absorption dans l 'UV-visible

[PDF] Cours SQL - SQLsh

[PDF] Requêtes SQL - LACL

[PDF] Cours SQL - SQLsh

[PDF] COURS COMPLET STATIQUE

[PDF] Statistique : Résumé de cours et méthodes 1 - Xm1 Math

[PDF] Première ES - Statistiques descriptives - Variance et écart - Parfenoff

[PDF] Cours de statistiques - 1 ère S - B Sicard

[PDF] I Etude d 'une série statistique : le vocabulaire II - college-therouanne

[PDF] Statistique et calcul de probabilité

[PDF] Cours de Statistiques inférentielles

[PDF] Probabilités et Statistiques, polycopié de L3 - Département de

Université Joseph Fourier, Grenoble Maths en Ligne

Arithmétique

Didier Piau et Bernard Ycart

Guère d"introduction tonitruante à faire, sinon pour souligner que ce chapitre a le charme de n"utiliser comme notions admises que les notations de la théorie des ensembles naïve et les connaissances évidentes sur les entiers, et qu"il présente donc l"agrément de donner une image de démonstrations (que l"on espère) totalement cré- dibles.

Table des matières

1 Cours 2

1.1 Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2 Division euclidienne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 PGCD et PPCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.4 Lemme de Gauss et décomposition en facteurs premiers . . . . . . . . . 8

1.5 Sous-groupes deZ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.6 Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.7Z/nZ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2 Entraînement 23

2.1 Vrai ou Faux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.2 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.3 QCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.4 Devoir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.5 Corrigé du devoir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3 Compléments 39

3.1 Abacistes contre algoristes . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.2 Des grains de sable dans l"univers . . . . . . . . . . . . . . . . . . . . . 41

3.3 Les comptes binaires de l"Empereur de Chine . . . . . . . . . . . . . . . 43

3.4 Chasles contre Libri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.5 Ils sont amicaux, parfaits... voire excessifs . . . . . . . . . . . . . . . 48

3.6 Le Théorème des Restes Chinois . . . . . . . . . . . . . . . . . . . . . . 49

3.7 Le Théorème de Ibn al-Haytham . . . . . . . . . . . . . . . . . . . . . 50

3.8 Diophante et Hypathie, tous deux d"Alexandrie . . . . . . . . . . . . . 52

3.9 Le Dernier Théorème de Fermat . . . . . . . . . . . . . . . . . . . . . . 53

3.10 Quatre siècles avant Fermat . . . . . . . . . . . . . . . . . . . . . . . . 57

3.11 Le grand plan de Sophie Germain . . . . . . . . . . . . . . . . . . . . . 58

3.12 Le Théorème de Fermat-Wiles . . . . . . . . . . . . . . . . . . . . . . . 61

13 février 2013

Maths en LigneArithmétiqueUJF Grenoble3.13 Le code RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

3.14 La course aux nombres premiers . . . . . . . . . . . . . . . . . . . . . . 63

3.15 La répartition des nombres premiers . . . . . . . . . . . . . . . . . . . . 65

1

Maths en LigneArithmétiqueUJF Grenoble1 Cours

1.1 Nombres premiers

On appelle entier (ou entier relatif, c"est-à-dire positif ou négatif) tout élément de

Z=?...,-3,-2,-1,0,1,2,3,...?

Définition 1.On dit qu"un entieraest unmultipled"un entierb, ou quebest un diviseurdealorsqu"il existe un entierktel quea=kb. Définition 2.On dit qu"un entierp≥2est premier lorsqu"il possède pour seuls diviseurs positifs1et lui-même. On notera au passage qu"au hasard des définitions, on parlera parfois d"entiers relatifs (les éléments deZ) et parfois d"entiers naturels (les éléments deN). Ce n"est qu"exceptionnellement très significatif; la principale fonction est d"être cohérent avec le reste du monde. Ainsi, comme partout ailleurs, dans ce cours, le nombre3est un nombre premier alors que-3n"en est pas un. En revanche, les nombres négatifs étant autorisés dans la définition de " diviseurs », l"entier3possède en tout et pour tout quatre diviseurs (à savoir-3,-1,1et3). Et tout de suite un joli théorème, qui remonte auxÉlémentsd"Euclide, écrits au IIIème siècle avant notre ère (c"est la proposition 20 du livre IX). Théorème 1.Il existe une infinité de nombres premiers. Vous connaissez probablement déjà une démonstration, il en existe plusieurs qui sont toutes bonnes à connaître, en voici une qui est très proche de celle du traité d"Euclide lui-même. Démonstration: SoitAl"ensemble des nombres premiers.Aest une partie deN, et est non vide car2est premier. On va supposerAfinie et aboutir à une absurdité. Supposons doncAfinie. Dès lors queAest une partie finie deN, évidemment non vide car2est premier,Apossède un plus grand élément. NotonsPce plus grand élément, le mystérieux " plus grand nombre premier ». Considérons alors l"entierN=P!+1(la factorielle deP, plus1). Pour tout entier Tout diviseur deN, et en particulier tout diviseur premier deN, est donc strictement supérieur àP. Or tout entier, et par exempleN, possède au moins un diviseur premier (pourquoi? exercice...). Mais alors, chacun de ces diviseurs premiers contredit la maximalité de

P. Absurdité!

2 Maths en LigneArithmétiqueUJF Grenoble1.2 Division euclidienne Il s"agit de formaliser avec précision la bonne vieille division euclidienne, celle que vous connaissez depuis l"école primaire. Théorème 2.Soitaun entier (relatif) etb>1un entier strictement positif. Alors il existe un couple(q,r)unique (d"entiers) vérifiant la double condition : a=bq+ret 06r < b. Démonstration: On va prouver successivement l"existence et l"unicité de(q,r). Existence de(q,r): la démonstration se prête bien à discuter selon le signe dea. Le cas oùa>0est le cas contenant l"essentiel de la démonstration; lorsquea <0, on ne peut utiliser mot à mot la même preuve, mais on se ramène alors sans mal au cas intéressant déjà traité. •Premier cas (le cas significatif) : sia>0. L"idée de la démonstration est de dire que le quotient deaparbest le plus grand entierqtel quebqsoit encore plus petit quea. Introduisons donc l"ensembleA={c?N, bc6a}. L"ensembleAest un ensemble d"entiers naturels; il est non vide, car il contient0. Il est fini : en effet soitdun entier tel qued>a+ 1; on a alorsbd>b(a+ 1)>a+ 1> a, doncd??Aet ainsiAne contient que des entiers inférieurs ou égaux àa. L"ensembleApossède donc un plus grand élémentq. Posonsr=a-bq. La première condition sur(q,r)est alors évidemment vérifiée, c"est la seconde qui nécessite une vérification. Commeq?A, par définition deA, on abq6a. Doncr=a-bq>0. Commeqest maximal parmi les éléments deA,q+1??A. Doncb(q+1)> a, donc r=a-bq < b.

L"existence est démontrée dans ce cas.

•Second cas (preuve sans imagination) : sia <0. Posonsa?=a(1-b). Commea <0et1-b60, on obtienta?>0. On peut donc, en appliquant le premier cas, faire la division euclidienne dea?par b; notons(q?,r)le couple ainsi obtenu : on a alorsa?=bq?+r, avec en outre06r < b. En réinjectant la définition dea?, on écrit alorsa-ba=bq?+r, donca=b(q?+a)+r. Si on poseq=q?+a, on constate qu"on a réussi la division euclidienne deaparb. Unicité de(q,r): soit(q1,r1)et(q2,r2)des couples vérifiant les deux conditions exigées dans l"énoncé du théorème. On déduit dea=bq1+r1=bq2+r2queb(q1-q2) =r1-r2. Ainsi,r1-r2est un multiple deb. Des conditions06r1etr2< b, on déduit que-b < r1-r2. 3 Maths en LigneArithmétiqueUJF GrenobleDes conditionsr1< bet06r2, on déduit quer1-r2< b. Ainsir1-r2est un multiple debcompris strictement entre-betb. La seule possibilité est quer1-r2soit nul. On en déduitr1=r2, puis, en allant reprendre l"égalitéb(q1-q2) =r1-r2, queq1=q2.

1.3 PGCD et PPCM

Les deux théorèmes qui se suivent sont agréablement parallèles; il est donc amusant de constater que leurs preuves sont plus différentes qu"on ne pourrait s"y attendre. Il est possible de les déduire l"un de l"autre, mais il est instructif de les prouver très séparément. Vous verrez donc plusieurs preuves de l"un comme de l"autre. Théorème 3.Soita>1etb>1deux entiers. Alors il existe un unique entierm>1 tel que pour tout entierc>1, cest un multiple deaet debsi et seulement sicest un multiple dem. Théorème 4.Soita>1etb>1deux entiers. Alors il existe un unique entierd>1 tel que pour tout entierc>1, cdiviseaetbsi et seulement sicdivised. Ces théorèmes sont vendus avec deux compléments, le premier occasionnellement utile, le second totalement fondamental.

Complément 1Pour tousaetb,md=ab.

Complément 2 (Identité de Bézout)

Pour tousaetb, il existe deux entiers (relatifs)setttels qued=sa+tb. Et tant qu"on y est avant de passer aux démonstrations : Définition 3.Leplus petit multiple communde deux entiersaetbest l"entierm apparaissant dans l"énoncé du théorème 3. Notation 1.Le plus petit multiple commun deaetbsera notéppcm(a,b). Définition 4.Leplus grand commun diviseurde deux entiersaetbest l"entierd apparaissant dans l"énoncé du théorème 4. Notation 2.Le plus grand commun diviseur deaetbsera notépgcd(a,b).

Première démonstration du théorème 3

Cette démonstration est la plus élémentaire; elle consiste à choisir pourmle mul- 4

Maths en LigneArithmétiqueUJF Grenoblevérifier qu"il marche. La preuve est en deux parties : d"abord l"existence dem(partie

significative) puis son unicité (partie très facile).

Existence dem

Introduisons l"ensembleAformé des entiers strictement positifs simultanément mul- tiples deaet deb. L"ensembleAn"est pas vide, puisqu"il contient l"entierab. Il admet donc un plus petit élémentm. On va vérifier que cet entiermconvient. Pour faire cette vérification, soit un entiern>1; nous avons désormais à montrer une équivalence, distinguons méthodiquement les deux sens. •Preuve de l"implication directe : Supposons donc quenest un multiple commun deaetb, et montrons quenest un multiple dem. Pour ce faire, effectuons la division euclidienne denparm, soitn=mq+r, avec06r < m. Commenetmsont des multiples dea,r=n-mqaussi; de même avecb. Ainsirest un multiple commun deaetb. Sirétait un entier strictement positif, vu l"inégalitér < mil contredirait la minimalité dem. C"est donc quer= 0et donc quenest un multiple dem. •Preuve de l"implication réciproque : Supposons ici quenest un multiple dem. Commemest lui-même multiple dea,nest à son tour multiple dea; de même avec b. C"est réglé.

Unicité dem

Soitmetm?vérifiant les hypothèses du théorème. Commemest un multiple dem (eh oui!), c"est un multiple commun deaetb, donc un multiple dem?. De même,m? est un multiple dem. Cela implique quemetm?sont forcément égaux au signe près. Comme ils sont tous deux strictement positifs, ils sont égaux. Fin de la démonstration. Voici maintenant une première démonstration de l"existence (et l"unicité) du pgcd, qui l"obtient à partir du ppcm. Cette démonstration a le confort d"être dépourvue d"idée subtile et l"avantage de prouver le Complément 1. Elle a l"inconvénient de ne pas prouver le Complément 2 et de ne pas fournir une méthode rapide de calcul du pgcd.

Première démonstration du théorème 4

Existence ded

On notemle ppcm deaetbet on posed=ab/m. Remarquons que ce nombred est bien un entier : en effet,abétant un multiple commun évident deaetb, c"est un multiple de leur ppcm. Reste à prouver qu"il convient. Pour faire cette vérification, soitn>1un entier; nous avons désormais à montrer une équivalence, distinguons méthodiquement les deux sens. •Preuve de l"implication directe : supposons quenest un diviseur commun dea etb. On peut donc introduire deux entiersket?tels quea=knetb=?n. Pour travailler sur ce sur quoi nous avons des informations, à savoir les multiples deaetb, introduisons le nombren?=ab/n. Ce nombren?vaut aussi(a/n)b=kbet(b/n)a=?a. C"est donc un entier, et même un multiple commun deaetb. C"est donc un multiple 5

Maths en LigneArithmétiqueUJF Grenobledem. Il existe donc un entierctel quen?=cm, soitab/n=cab/d, doncd=cn. On

a bien prouvé quendivised. •Preuve de l"implication réciproque : puisquea=d(m/b)oùm/best un entier,d divisea; symétriquement puisqueb=d(m/a),ddiviseb. Supposons maintenant que ndivised. On voit alors aussitôt quendiviseaetb.

Unicité ded

C"est exactement le même principe que pour le ppcm, on laisse donc cette partie de la démonstration en exercice (très) facile. Preuve du Complément 1 : Il tombe immédiatement au vu de la formule qui donne dà partir dem. Fin de la démonstration. Comme promis, voici maintenant une deuxième démonstration du théorème 4, très différente dans son esprit, et qui permet pour guère plus cher de montrer simultanément le Complément 2.

Deuxième démonstration du théorème 4

La démonstration est une récurrence surb; techniquement, on gagne sérieusement

en confort si on autorisebà être nul, ce que l"on n"a pas fait, volontairement, en énonçant

le théorème dans l"espoir qu"il soit plus clair. On montrera donc légèrement mieux que

l"énoncé de la page précédente, puisqu"on prouvera le résultat sous l"hypothèse "a>1

etb>0». Avant de se lancer dans la récurrence proprement dite, on va donner un " résumé de la preuve » sous forme de programme informatique récursif.

Début du programme

*pgcd(a,0) =a. * Soitrle reste de la division euclidienne deaparb. Les diviseurs communs deaetbsont les diviseurs communs debetr.

D"où :pgcd(a,b) = pgcd(b,r).

Fin du programme

Ce résumé de démonstration convaincra peut-être les esprits les plus agiles, mais à notre niveau d"entraînement, il est plus prudent de faire ce qui est derrière les formu- lations récursives : une bonne vieille récurrence. On va démontrer par " récurrence forte » surb>0l"hypothèse(Hb)suivante : (Hb)Pour tout entiera>1, il existe deux entiers (relatifs)setttels que, pour toutn>1,ndiviseaetbsi et seulement sindivisesa+tb.

Vérifions(H0).

Soitaun entier aveca>1; tout entiern>1qui diviseadivise aussib= 0puisque

0n= 0. Pour toutn>1, on a donc :ndiviseaet0si et seulement sindivisea.

Prenons alorss= 1ett= 0. On a donc bien pour toutn>1:ndiviseaet0si et seulement sindivisesa+t×0. 6

Maths en LigneArithmétiqueUJF GrenobleSoitbun entier fixé, avecb>1. Supposons la propriété(Hc)vraie pour toutcavec

06c < bet montrons(Hb).

Soitaun entier aveca>1. Notonsa=bq+rla division euclidienne deaparb (qu"on peut réaliser puisqueb>1). Vérifions l"affirmation intermédiaire suivante : pour toutn>1,nest un diviseur commun deaetbsi et seulement sinest un diviseur commun debetr. C"est-à-dire, avec des mots peut-être plus lisibles : " les diviseurs communs deaetbsont les mêmes que ceux debetr. » Soitnun diviseur commun deaetb, alorsndivise aussir=a-bq; réciproquement soitnun diviseur commun debetr, alorsndivise aussia=bq+r. L"affirmation intermédiaire est donc démontrée. On peut alors appliquer l"hypothèse de récurrence(Hr)(puisque précisément06 r < b) sur l"entierb>1. On en déduit qu"il existe deux entiers relatifss?ett?tels que pour toutn>1,n divisebetrsi et seulement sindivises?b+t?r. Remarquons enfin ques?b+t?r=s?b+t?(a-bq) =t?a+(s?-q)b, et qu"ainsi, si on poses=t?ett=s?-q, on a bien prouvé que, pour toutn>1,ndiviseaetbsi et seulement sindivisesa+tb. (Hb)est donc démontrée. On a donc bien prouvé(Hb)pour toutb>0, donc a fortiori pour toutb>1, ce qui prouve le théorème 4 et son Complément 2. En fait, il reste à prouver l"unicité ded, pour laquelle on renvoie à la démonstration précédente (où on écrivait qu"on la laissait en exercice).

Fin de la démonstration.

À présent, donnons un petit exemple sur des vrais nombres concrets, pour nous soulager l"esprit après tant de lettres.

Calcul du pgcd de137et24

On fait des divisions euclidiennes successives et on écrit dans la colonne de droite les conséquences de ces divisions. (1) 137 = 5×24 + 17pgcd(137,24) = pgcd(24,17) (2) 24 = 1×17 + 7pgcd(24,17) = pgcd(17,7) (3) 17 = 2×7 + 3pgcd(17,7) = pgcd(7,3) (4) 7 = 2×3 + 1pgcd(7,3) = pgcd(3,1) (5) 3 = 3×1 + 0pgcd(3,1) = pgcd(1,0) = 1

Doncpgcd(137,24) = 1.

Ces calculs permettent ensuite sans mal de reconstituer une identité de Bézout. - La dernière division avec un reste non nul est (4) qui donne1 = 7-2×3. 7

Maths en LigneArithmétiqueUJF Grenoble- On va repêcher une expression de3comme un reste dans la relation précédente,

soit (3), ce qui donne3 = 17-2×7. - On reporte cette expression de3donc1 = 7-2×(17-2×7). - On regroupe les termes en17et7donc1 =-2×17 + 5×7. - On va repêcher une expression de7comme un reste dans la relation précédente, soit (2), ce qui donne7 = 24-1×17. - On reporte cette expression de7donc1 =-2×17 + 5×(24-1×17). - On regroupe les termes en24et17donc1 = 5×24-7×17. - On va repêcher une expression de17comme un reste dans la relation précédente, soit (1), ce qui donne17 = 137-5×24. - On reporte cette expression de17donc1 = 5×24-7×(137-5×24). - On regroupe les termes en137et24donc

1 =-7×137 + 40×24.

- Et voilà!

Voici un autre exemple.

Calcul du pgcd de141et24

Voici les divisions euclidiennes successives et leurs conséquences en termes de pgcd. (1) 141 = 5×24 + 21pgcd(141,24) = pgcd(24,21) (2) 24 = 1×21 + 3pgcd(24,21) = pgcd(21,3) (3) 21 = 7×3 + 0pgcd(21,3) = pgcd(3,0) = 3 Doncpgcd(141,24) = 3et on vérifiera que ces calculs permettent de reconstituer l"identité de Bézout -141 + 6×24 = 3. Donnons une dernière définition avant de quitter les pgcd. Définition 5.On dit que deux entiersa>1etb>1sontpremiers entre euxlorsque leur seul diviseur commun positif est1. On veillera à ne pas confondre cette notion avec celle de nombre premier. (Par exemple, les calculs ci-dessus montrent que137et24sont premiers entre eux mais24 n"est pas premier.)

1.4 Lemme de Gauss et décomposition en facteurs premiers

Le lemme de Gauss permet de démontrer l"unicité de la décomposition en facteurs premiers. Ce dernier résultat semble plus facile d"usage pour un utilisateur peu expéri- menté, donc on énonce le lemme de Gauss sans commentaire, ou plus exactement sans autre commentaire que ce commentaire négatif. 8

Maths en LigneArithmétiqueUJF GrenobleLemme 1.Soita,betctrois entiers strictement positifs. Siadivise le produitbcet

siaest premier avecc, alorsadiviseb. Démonstration: Puisqueaest premier avecc, le pgcd deaetcest1, donc il existe des entiers relatifssetttels quesa+tc= 1. Multiplions cette identité parb: on obtient b=asb+tbc. Mais dans cette écriture,asbest évidemment multiple deatandis que tbcl"est parce quebcest multiple dea. On en déduit queb, somme des deux multiples deaque sontasbettbc, est lui-même un multiple dea. Théorème (énoncé approximatif)Tout entiern>2peut être écrit de façon unique comme produit de facteurs premiers. L"énoncé est approximatif car il n"est pas si clair de savoir ce que signifie "unique» : on peut écrire6 = 2×3 = 3×2mais il faut évidemment considérer que c"est la même chose. Pour pouvoir comprendre voire utiliser le théorème, cet énoncé suffira bien; mais pour le démontrer, il faut être plus précis. Théorème 5(énoncé précis).Tout entiern>2peut être écrit comme produit de facteurs premiers. De plus, si on dispose de deux écritures dans lesquellesk>1,i>1, les entiersp1< p2< ... < pketq1< q2< ... < qisont

tous premiers et rangés en ordre croissant, les exposantsα1,α2, ...,αketβ1,β2, ...,

isont tous des entiers strictement positifs, alors ces deux écritures sont les mêmes au sens précis suivant :k=iet pour toutjavec16j6k=i,pj=qjetαj=βj. Démonstration: À énoncé indigeste, démonstration indigeste. L"existence provient d"une récurrence élémentaire. Pour tout entiern≥2, considé- rons l"hypothèse de récurrence (forte) suivante : (En)Tout entier26k6npeut s"écrire comme un produit de facteurs premiers comme dans l"énoncé du théorème.

Alors(E2)est évidente car2est premier.

Soitn≥2un entier fixé, supposons(En)vraie et montrons(En+1).

Sin+ 1est premier,(En+1)est évidente.

Sin+ 1n"est pas premier, il existe un entier26k6nqui divisen+ 1. Notons? l"entier?= (n+ 1)/k. Alors26?6ndonc on peut appliquer l"hypothèse(En)aux deux entiersket?. Il existe donc des entiers premierspietqjet des exposantsaietbj strictement positifs tels que k=pa11pa22···pauu, ?=qb11qb22···qbvv, avecp1< p2< ... < puetq1< q2< ... < qv. Par conséquent, n+ 1 =k×?=pa11pa22···pauu×qb11qb22···qbvv. 9

Maths en LigneArithmétiqueUJF GrenobleL"ensemble{p1,p2,...,pu} ? {q1,q2,...,qv}comportew6u+véléments. Notons et

ordonnons ces éléments commer1< r2<···< rw. En regroupant les entiers qui apparaissent dans les deux factorisations, on obtient n+ 1 =rc11rc22···rcww, où les exposantscksont définis comme suit : -ck=aisirk=pietrk?=qjpour toutj, -ck=bjsirk=qjetrk?=pipour touti, - et enfinck=ai+bjsirk=pi=qj.

Donc(En+1)est vraie.

Ceci conclut la preuve de l"existence.

Passons à l"unicité. On va donc montrer par récurrence (forte) surnle résultat d"unicité(Hn)écrit dans l"énoncé du théorème. Démonstration de(H2), et en fait même de(Hp)pour tout nombre premierp Supposonsn=ppremier écrit sous forme de produitp=pα11pα22···pαkk. Chaque p iest un diviseur positif depnon égal à1, donc chaquepiest égal àp. Ceci entraîne aussitôt quek= 1et queα1= 1(sans cela le produit serait supérieur ou égal àp2 donc distinct dep). L"écriturep=pest donc la seule possible pourp, ce qui démontre (Hp)quandpest premier. Soit maintenantnun entier fixé, non premier, avecn >2, et supposons l"hypothèse d"unicité(Hm)prouvée pour tout entiermavec26m < n. Première étapeMontrons quepk=qi(toujours dans les notations de l"énoncé du théorème). Supposons tout d"abord quepk> qiet montrons que l"on aboutit à une absurdité. Puisque lesqjsont supposés rangés dans l"ordre croissant,pkest alors forcément distinct de tous lesqj;pket chaqueqjétant premiers, on en conclut que leur seul diviseur commun positif est1:pketqjsont donc premiers entre eux. Fixons unjentre1etiet montrons par récurrence surb>0l"énoncé fort intuitif suivant :(H?b):pkest premier avecqbj. (H?0)est évident puisqueq0j= 1. Soitb>0un entier fixé, supposons(H?b)vrai et montrons(H?b+1). Si(H?b+1)était faux, le pgcd depketqb+1jne serait pas1; comme c"est un diviseur positif depk, ce seraitpkqui diviserait doncqb+1j. On peut alors appliquer le lemme de Gauss : commepkdiviseqb+1j=qbjqjet quepkest premier avecqj,pkdiviseqbj. Mais ceci contredit l"hypothèse(H?b). L"hypothèse(H?b+1)est donc vraie. On a donc bien montré que pour toutb>0,pkest premier avecqbj. En particulier, p kest premier avecqβj j. Comme on a prouvé cette affirmation pour unjquelconque, on a prouvé que pour toutjentre1eti,pkest premier avecqβj j. Ce qu"on a fait avec 10

Maths en LigneArithmétiqueUJF Grenobleles puissances de chaqueqj, on va maintenant le recommencer avec le produit de ces

puissances. Précisément, on va montrer par récurrence sur l"entierjque pour toutj avec16j6l, on a l"énoncé(H??j):pkest premier avecqβ11qβ22···qβj j. Les lecteurs encore éveillés (s"il en reste) comprendront que la preuve est à peu près la même que celle des(H?b), pour les autres, la voilà : Pourj= 1, on doit prouver quepkest premier avecqβ11. C"est déjà fait. Fixons un entierjavec16j < iet supposons l"hypothèse(H??j)vraie. Si(H??j+1)était fausse, le pgcd depketqβ11qβ22···qβj jqβj+1 j+1ne serait pas1; comme c"est un diviseur positif depk, ce seraitpkqui diviserait doncqβ11qβ22···qβj jqβj+1 j+1. On peut alors appliquer le lemme de Gauss : commepkdivise le nombre q

β11qβ22···qβj

jqβj+1 j+1=?qβ11qβ22···qβj j?qβj+1 j+1 et commepkest premier avecqβj+1 j. Mais ceci contredit l"hypo- thèse(H??j). L"hypothèse(H??j+1)est donc vraie. On a donc montré(H??j)pour toutjentre1eti; en particulier on a montré(H??i),

à savoir quepkest premier avecqβ11qβ22···qβii=n. Mais pourtantpkfigure dans l"autre

décomposition en facteurs premiers den(ce n"est pas une illusion d"optique, puisqu"on a pris soin de supposerαk>1), doncpkdivisen. D"où contradiction. Ouf! On ne peut donc avoirpk> qi. En échangeant les rôles des coefficientspetq, on voit qu"on ne peut pas non plus avoirqi> pk. On en déduit donc queqi=pk.

Fin de la première étape

Deuxième étapeOn va profiter de ce tout petit morceau d"égalité pour arriver à

utiliser l"hypothèse de récurrence et faire tomber toutes les autres égalités requises en

cascade.

NotonsN=n/pk=n/qi, on a ainsi :

N=pα11pα22···pαk-1

ketN=qβ11qβ22···qβi-1 i. De plusNest strictement inférieur àn, etNest strictement plus grand que1car on a fort opportunément supposénnon premier. On va donc appliquer l"hypothèse de récurrence(HN)à ces deux écritures deNen facteurs premiers. Si on n"est pas méticuleux, on oubliera de s"assurer que tous les exposants sont strictements positifs, et on aura fini tout de suite; ce sera faux, mais de peu. Hélas, un enseignant scrupuleux ne peut se le permettre et doit donc veiller à ce petit détail, qui nous force à distinguer deux sous-cas. Premier sous-cas :αk= 1. Dans ce cas, la première écriture demse lit en réalité, après effacement dup0kqui l"encombre :

N=pα11pα22···pαk-1k-1.

11

Maths en LigneArithmétiqueUJF GrenobleAinsiNpossède une décomposition en facteurs premiers dans laquellepkne figure

pas. Comme sa décomposition est unique,pkne peut non plus figurer dans l"autre décomposition, et commeqi=pk, la seule possibilité est que l"exposantβi-1soit nul; ainsiβi=αk=1, et les deux représentations sont deux décompositions deNen facteurs premiers. On en déduit quek-1 =i-1, donck=i, puis l"égalité de tous les facteurs premiers et exposants encore en attente d"élucidation. Second sous-cas :αk>1. C"est la même chanson. On remarque tout d"abord qu"on a aussiβi>1(sans cela, en échangeant les rôles des coefficientspetqet en utilisant le premier cas, on montrerait queαk= 1); donc les deux décompositions

N=pα11pα22···pαk-1

ketN=qβ11qβ22···qβi-1 i vérifient bien les hypothèses du théorème. Elles sont égales, donck=iet chaque coefficientpest égal au coefficientqcorrespondant, avec le même exposant.

Fin de la deuxième étape

(Hn)est donc prouvée. La récurrence est donc terminée, et avec elle la démonstration. La décomposition en facteurs premiers permet d"énumérer facilement les diviseurs d"un entier.

Proposition 1.Soitnun entier et

n=pα11pα22···pαkk sa décomposition en facteurs premiers. L"ensemble des diviseurs positifs denest : D=? N=pβ11pβ22···pβkk,?i= 1,...,k06βi6αi? Par exemple l"ensemble des diviseurs positifs de60 = 223151est : D=? 2 2 soit, D=?

1,2,3,4,5,6,10,12,15,20,30,60?

Démonstration: Soit

quotesdbs_dbs7.pdfusesText_13