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

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

Previous PDF

Next PDF

Université Joseph Fourier, Grenoble I

Mathématiques, Informatique et Mathématiques Appliquées Licence Sciences et Technologies1eannéeArithmé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 22

2.1 Vrai ou Faux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

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

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

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

2.5 Corrigé du devoir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3 Compléments 38

3.1 Le code RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.2 La course aux nombres premiers . . . . . . . . . . . . . . . . . . . . . . 38

3.3 La répartition des nombres premiers . . . . . . . . . . . . . . . . . . . . 38

Maths en L

1gneArithmé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 L

1gneArithmé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 : 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. 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. 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. On peut donc, en appliquant le premier cas, faire la division euclidienne dea?par 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. 3

Maths en L

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 L

1gneArithmé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 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 L

1gneArithmé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 L

1gneArithmétiqueUJF GrenobleSoitbun entier fixé, avecb≥1. Supposons la propriété(Hc)vraie pour toutcavec

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. 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 droitequotesdbs_dbs22.pdfusesText_28

[PDF] Note et rapport - Méthode et exercices - Catégorie A et B - L

[PDF] Vitamin B12 in Vegetarian Diets - Vegetarian Nutrition

[PDF] C1 C2 B2 B1 A2 A1 A1 - Cambridge English

[PDF] C1 C2 B2 B1 A2 A1 A1 - Cambridge English

[PDF] The Association Between TOEFL iBT Test Scores and the Common

[PDF] B2i collège - mediaeduscoleducationfr

[PDF] Feuille de position B2i École

[PDF] Le B2I collège quot Brevet Informatique et Internet quot - Collège ADAUDET

[PDF] Référentiel du B2I lycée (pdf) - mediaeduscoleducationfr

[PDF] Programmes 2016 Cycles 2 3

[PDF] Performance of B3LYP Density Functional - ACS Publications

[PDF] Bit #8212 Wikipédia

[PDF] BAA - HEC Montréal

[PDF] pengaturan tentang hak asasi manusia berdasarkan undang

[PDF] Règlement simplifié du Badminton