Université Denis Diderot Paris 7, Semestre Février-juin 2005 Cours ...

Description

Université Denis Diderot Paris 7, Semestre Février-juin 2005 Cours ...

Sujets

• cours

Informations

• Publié par: ojurarop
• Nombre de lectures: 92
• Langue: Français

Extrait

Universit´ Denis Diderot Paris 7, Semestre F´vrier-juin 2005
Cours d’arithm´tique (M1)
(Marc Hindry :[e-mail] )

Premi`re partie :structures finies
∗
Rappels surZ/mZ, (Z/mZ) etFq.
∗
La structure des groupes (Z/mZ) etFq.
Symboles de Legendre et Jacobi).
Sommes de Gauss.
Applications au nombre de solutions d’´quations.

PLAN

Applications I : algorithmes, primalit´ et factorisation.
Algorithmes de base.
Cryptographie, RSA.
Test de Primalit´ (I).
Test de Primalit´ (II).
Factorisation.

Applications II : Codes correcteurs.
G´n´ralit´s sur les codes correcteurs.
Codes lin´aires cycliques.

Deuxi`me partie :Alg`bre et ´quations diophantiennes.
Sommes de carr´s.
Equation de Fermat (n= 3 et 4).
2 2
Equation de Pell-Fermatx−dy= 1.
Anneaux d’entiers alg´briques.

Troisi`me partie :th´orie analytique des nombres
Enonc´s et estimations “´l´mentaires”.
Fonctions holomorphes (r´sum´/rappels).
S´ries de Dirichlet, fonctionζ(s).
Caract`res et th´or`me de Dirichlet.
Le th´or`me des nombres premiers.

1

page 3
page 3
page 5
page 7
page 9
page 12

page 16
page 16
page 17
page 19
page 22
page 25

page 28
page 28
page 31

page 36
page 36
page 41
page 43
page 49

page 55
page 55
page 58
page 61
page 63
page 68

BIBLIOGRAPHIE(comment´e subjectivement)
D. Perrin,Cours d’alg`bre(, Ellipses.excellent livre particuli`rement recommand´ pour la pr´paration `
l’agr´gation)
M. Demazure,Cours d’alg`bre(, Cassini, Paris, 1997.surtout pour la partie “structures finies” et algorithmes)
K. Ireland, M. Rosen,A classical introduction to modern number theory, Graduate texts in math.84,
Springer, 1982.(comme le titre l’indique. . .)
P. Samuel,th´orie alg´brique des nombres(, Hermann.traite les anneaux de Dedekind ` un niveau un peu
plus ´lev´ que ce cours – deuxi`me partie – mais si bien ´crit.Un classique)

A. Baker,Transcendental Number Theory(, Cambridge University Press, 1975.les toutes premi`res pages
d´montrent la transcendance deeetπ, le reste du livre est plus sp´cialis´)
. . .et mes livres pr´f´r´s :
G. H. Hardy and E. M.Wright,An introduction to the theory of numbers, Oxford University Press, 4th
ed.,1960. (pr´sentation de la plupart des sujets de th´orie des nombres ` un niveau ´l´mentaire, tr`s
attrayant!)
J.-P. Serre,Cours d’arithm´tique, Presses Universitaires de France, 1970.(Un classique insurpassable.
J’utiliserai le d´but sur les corps finis, la loi de r´ciprocit´ et la partie th´orie analytique pour les s´ries
et th´or`me de Dirichlet)
Borevich, Shafarevich,Th´orie des nombres((traduit du russe), Gauthier-Villars.Un tr`s joli livre qui,
mˆme s’il d´marre ` un niveau ´l´mentaire, est d’un niveau plus ´lev´ que ce cours)

2

Universit´ Denis Diderot Paris 7, Semestre F´vrier-juin 2004
Cours de maıtrise :arithm´tique
∗ ∗
Premi`re partie :
Structures finies Z/nZ,(Z/nZ), Fq, Fq.

∗ ∗
A. Rappels surZ/nZ, (Z/nZ) ,Fq,F.
q
∗ ∗
B. La structure des groupes (Z/nZ) etF.
q
C. Symboles de Legendre et Jacobi.
D. Sommes de Gauss.
E. Applications au nombre de solutions d’´quations.

∗ ∗
A. Rappels sur Z/nZ,(Z/nZ), Fq, F .
q
La th´orie des congruences am`ne, pour chaque entiersn≥2, ` consid´rer l’anneauZ/nZainsi que le
∗
groupe de ses ´l´ments inversibles (pour la multiplication)(Z/nZ). Pourchaque puissance d’un nombre
f
premierq=p, il existe un corps fini de cardinalq, unique ` isomorphisme pr`s, not´Fq. Nousrappelons
la construction de ces objets et pr´cisons leurs principales propri´t´s.
Le groupeZest l’unique groupe (` isomorphisme pr`s) qui est cyclique (engendr´ par un ´l´ment) et infini.
Tous ses sous-groupes sont du typemZpourm≥0. L’ensembleZest ´galement muni d’une multiplication
qui en fait un anneau commutatif.Dans cet anneau on a la notion de divisibilit´ et de PGCD et PPCM.
Dans le cas deZla notion d’id´alcoıncide avec celle de sous-groupe.On peut en d´duire facilement le
th´or`me suivant
Th´or`me.(B´zout)Soitm, n∈Zet soitdleur PGCD, alors il existeu, v∈Ztels que

d=um+vn.

Preuve. L’ensembleH:=mZ+nZ={um+vn|u, v∈Z}est clairement un sous-groupe; il est donc de la
′ ′′
formedZet il existeu, vtels qued=um+vn. Commeddivisemetn, on voit queddiviseum+vn=d
′ ′′
maism, nappartiennent `Hdoncddivisemetndoncddivise ´galementdet on conclut quedZ=dZ
′
(on aura mˆmed=dsi l’on a pris soin de les prendre tous les deux positifs).

Le groupeZ/nZest l’unique groupe cyclique `nengendr´ par un´l´ments (` isomorphisme pr`s) i.e.
´l´ment d’ordren. Onpeut d´j` ´tudier ses g´n´rateurs
Proposition.Soitm∈Zetm¯sa classe dansZ/nZ, les trois propri´t´s suivantes sont ´quivalentes
(i) L’´l´ment¯mest un g´n´rateur deZ/nZ.
(ii) Les´l´mentsmetnsont premiers entre eux.
′ ′
(iii) L’´l´mentm¯est inversible modulon, c’est-`-dire qu’il existem∈Ztel quemm≡1 modnou encore
′
m¯m¯ =1∈Z/nZ.
′ ′′
Preuve. Supposonsque ¯mengendreZ/nZalors il existem∈Ztel quem m¯ =1∈Z/nZ; ainsimm≡
′ ′
1 modnce qui signifie quemest inversible modulon. Simm≡1 modnalorsmm+= 1anet doncm
est premier avecn. Simest premier avecnalors, d’apr`s le th´or`me de B´zout, il existea, btels que
am+bn= 1 doncam1¯ =∈Z/nZet doncm¯ engendreZ/nZ.

Exercice. Montrerque si, dans un groupe commutatif, l’ordre dex1estd1, l’ordre dex2estd2avecd1et
d2premiers entre eux, alors l’ordre dex1x2estd1d2. Montrer´galement que si, dans un groupe cyclique,
l’ordre dex1estd1, l’ordre dex2estd2, alors l’ordre du sous-groupe engendr´ parx1etx2est ´gal au
PPCM ded1etd2.
Le groupe des ´l´ments inversibles de l’anneauZ/nZest ´gal `

∗
(Z/nZ) ={m¯∈Z/nZ|mest premier avecn}={g´n´rateurs deZ/nZ}.

∗
D´finition.On noteφ(n) := card(Z/nZ) l’indicatrice d’Euler.

3

r rr−1r−1
On en d´duit facilement que, sipest premier,φ(p) =p−p= (p−1)pcalcul en g´n´ral de. Leφ(n)
se fait grˆce au lemme classique suivant.
Proposition.(Lemme chinois)Soitm, n∈Z, supposonsmetnpremiers entre eux, alors les groupes
Z/mnZetZ/mZ×Z/nZsont naturellement isomorphes.De plus cet isomorphisme est aussi un isomorphisme
∗ ∗∗
d’anneaux et, par cons´quent induit un isomorphisme entre(Z/mnZ)et(Z/mZ)×(Z/nZ)particulier. En
φ(mn) =φ(m)φ(n).
Preuve. Consid´ronsl’applicationf:Z→Z/mZ×Z/nZdonn´e parx7→(xmodm, xmodnun). C’est
homomorphisme de groupe de noyau ppcm(m, n)Z, d’o` une injection

ˆ
f:Z/ppcm(m, n)Z֒→Z/mZ×Z/nZ.

Commemetnsont suppos´s premiers entre eux, on a ppcm(m, n) =mnet, pour des raisons de cardinalit´,
ˆ
l’homomorphismefDe mani`re g´n´rale, sidoit ˆtre un isomorphisme.AetBsont des anneaux, on a
∗ ∗ ∗
(A×B) =A×Bd’o` la deuxi`me assertion.

Rappelons que, d’apr`s le th´or`me de Lagrange l’ordre d’un sous-groupe divise toujours l’ordre du groupe.
La description des sous-groupes deZ/nZest assez simple.
Proposition.Pour chaque entierd≥1divisantn, il existe un unique sous-groupe deZ/nZd’ordred, c’est
le sous-groupe cyclique engendr´ par la classe den/ddansZ/nZ.
¯
′ ′
Preuve. Supposonsn=ddalors l’´l´mentx=d∈Z/nZest d’ordredcar clairementdx= 0 et, si
′
cx= 0 alorsndivisecddoncddivisecmaintenant. SoitHun sous-groupe deZ/nZd’ordred. Notons
−1
s:Z→Z/nZOn sait quela surjection canonique.s(H) =mZest engendr´ parmdoncHest engendr´
′
parm¯∈Z/nZ. Onad¯m= 0 doncndivisedmdoncddivisemdonc le sous-groupeHest contenu dans le
¯
′
sous-groupe engendr´ pardet donc ´gal ` ce sous-groupe.

Comme application, on peut en tirer la formule (que nous utiliserons plus bas)
X
n=φ(d).
d|n

En effet on ´critZ/nZcomme union (disjointe) des ensembles d’´l´ments d’ordredpourddivisantn. Le
nombre de ces ´l´ments est le nombre de g´n´rateurs de l’unique sous-gro