[PDF] Arithmétique

Généralités et Arithmétique dans Z Table des matières Z, l'ensemble des entiers relatifs, Z = {, −2, −1, 0, 1, 2,} (voir cours d'Analyse) Ce n'est pas le

[PDF] Cours darithmétique

1 La division euclidienne dans l'anneau Z et ses conséquences 21 11 La division 22 Généralités sur les groupes finis L'arithmétique est l'étude des propriétés des nombres entiers, appelés aussi entiers naturels L'ensemble N des

[PDF] Cours darithmétique

Ce document est la premi`ere partie d'un cours d'arithmétique écrit pour les él` eves pré Z ensemble des entiers relatifs Q ensemble des nombres rationnels R Une récurrence directe permettra ensuite de l'avoir dans toute sa généralité

[PDF] algèbre et arithmétique 1 - Université de Rennes 1

définitions qui seront données au fil de ce cours) et des propriétés qui découlent de ces concepts, L'arithmétique est l'étude des propriétés des nombres entiers naturels ou relatifs Notre but On peut donc identifier N à une partie de Z On prolonge alors de l'addition, qui sera démontrée ci dessous en toute généralité

[PDF] Cours darithmétique

[PDF] Chapitre 4 :Arithmétique dans Z

Mais, afin de conserver la généralité des énoncés, nous n'allons pas, pour le cours, nous limiter aux entiers positifs A) PGCD et algorithme d'Euclide Etant

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

Maths discr`etes, 2012 2013 Université Paris Sud Résumé du cours d' arithmétique Les ensembles N et Z N = {0, 1, 2, 3,} est l'ensemble des entiers naturels

[PDF] Cours arithmétique et groupes Licence première année, premier

Cours arithmétique et groupes z = x ou z = y ; on le notera x−1 (on montrera en exercice qu'un prédécesseur On peut supposer sans perte de généralité

[PDF] Arithmétique

Feb 13, 2013 · relatifs (les éléments de Z) et parfois d'entiers naturels (les éléments de N) Ce n' est Ainsi, comme partout ailleurs, dans ce cours, le nombre 3 est un pu se méprendre sur l'exactitude ou la généralité de sa solution

[PDF] Arithmétique - Math France

Nous donnerons au cours de de paragraphe quelques généralités sur cette équation, mais nous décrirons sa résolution à travers des exemples qui serviront de

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

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.quotesdbs_dbs14.pdfusesText_20

[PDF] [PDF] Arithmétique

Arithmétique

Didier Piau et Bernard Ycart

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

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

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

Maths en LigneArithmétiqueUJF Grenoble1 Cours

1.1 Nombres premiers

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

P. Absurdité!

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

1.3 PGCD et PPCM

Complément 1Pour tousaetb,md=ab.

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

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

Existence dem

Unicité dem

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

Existence ded

Unicité ded

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

Début du programme

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

Fin du programme