CALCUL FORMEL POUR L’AGRÉGATION

CALCUL FORMEL POUR L’AGRÉGATION

Cours à l’Université de Rennes 1 (2008–2009)

Antoine Chambert-Loir

Antoine Chambert-Loir

IRMAR, Université de Rennes 1, Campus de Beaulieu, 35042 Rennes Cedex.

E-mail :[email protected]

Url :http://perso.univ-rennes1.fr/antoine.chambert-loir

Version du 24 mars 2009

La version la plus à jour est disponible sur le Web à l’adresse http://perso.univ-rennes.fr/

antoine.chambert-loir/2008-09/cf/

SOMMAIRE

Introduction . . . . 1 Bibliographie . . . . 3 1. Nombres entiers . . . . 5

Représentation des entiers, 5 ; Les quatre opérations, 7.

2. Algorithme d’Euclide . . . 11 L’algorithme d’Euclide étendu, 11 ; Complexité de l’algorithme d’Euclide

pour les entiers, 13 ; Complexité dans le cas des polynômes, 15.

3. Nombres premiers, factorisation . . . 17 Nombres premiers, 17 ; Factorisation, 25.

4. Corps finis . . . 29 Rappels sur les corps finis, 29 ; Polynômes à coeficients dans un corps

fini, 31 ; Extraction de racines m-ièmes, 37.

INTRODUCTION

Programme spécifique de l’option C.

a) Représentation et manipulation des entiers longs, flottants multiprécision, nombres complexes, polynômes, éléments de Z/nZ et des corps finis. Addition, multiplication, division, extrac- tion de racine carrée.

b) Algorithmes algébriques élémentaires. Exponentiation (n 7→

aⁿ, pour n ∈ N), algorithme d’Euclide étendu. Test de primalité de Fermat.

c) Matrices à coefficients dans un corps. Méthode du pivot de Gauss, décomposition LU. Calcul du rang, du déterminant.

Exemples de codes correcteurs linéaires : codes de répétition, codes de Hamming binaires.

d) Matrices à coefficients entiers. Opérations élémentaires sur les lignes et les colonnes. Application aux systèmes linéaires sur Z et aux groupes abéliens de type fini.

e) Polynômes à une indéterminée. Évaluation (schéma de Hor- ner), interpolation (Lagrange, différences finies). Localisation des racines dans R ou C : majoration en fonction des coefficients.

f ) Polynômes à plusieurs indéterminées. Résultants, élimina- tion ; intersection ensembliste de courbes et de surfaces algé- briques usuelles.

g) Estimation de la complexité des algorithmes précités dans le cas le pire. Aucune formalisation d’un modèle de calcul n’est exi- gée.

BIBLIOGRAPHIE

[1] E. BACH& J. SHALLIT– Algorithmic number theory. Vol. 1, Foundations of Compu- ting Series, MIT Press, Cambridge, MA, 1996, Efficient algorithms.

[2] J.VON ZUR GATHEN& J. GERHARD– Modern computer algebra, second éd., Cam- bridge University Press, Cambridge, 2003.

[3] C. K. YAP– Fundamental problems of algorithmic algebra, Oxford University Press, New York, 2000.

CHAPITRE 1

NOMBRES ENTIERS

§1.1. Représentation des entiers A. Numération

THÉORÈME1.1.1. — Soit b un nombre entier tel que b > 1. Pour tout entier n>^{0, il} existe une unique suite (a_r, . . . , a₀) d’entiers vérifiant 06^ai < b pour tout i ∈ {0, . . . , r }, a_r6= 0 et n = arb^r+ a_{r −1}b^{r −1}+ · · · + a1b + a0.

Cette suite s’appelle le développement en base b de l’entier n. Lorsque b = 10, cela correspond à l’écriture usuelle, par exemple 25 = 2·10+5. On écrira ainsi n = [ar. . . a₀]_b pour signifier que (a_r, . . . , a₀) est le développement en base b de l’entier n.

L’entier 0 correspond à la suite vide () ; pour cette raison, et pour se conforter à l’ha- bitude de noter le zéro, on autorise parfois ar = 0 lorsque r = 0. Sauf dans ce cas, on a r>0 et le nombre de chiffres du développement de n est égal à r + 1.

La présence ou l’absence de zéros en tête du développement en base b n’est de toutes façons qu’une convention de notation. Si le choix du mathématicien de ne pas les inclure permet d’énoncer un théorème élégant comme celui ci-dessus ( :-)), le choix contraire peut être utile en pratique.

Les bases les plus couramment utilisées sont b = 10 (système décimal) b = 2 (numé- ration binaire), b = 16 (notation hexadécimale⁽¹⁾), b = 2⁸(du temps où l’unité de base d’un ordinateur était l’octet), b = 2⁶⁴(maintenant que les ordinateurs ont 64 bits) Mais si l’on ne peut utiliser qu’une calculatrice « 8 chiffres » pour effectuer de gros calculs, la base 10⁴s’avérera très pratique.

On peut représenter un entier relatif par sa valeur absolue et son signe.

B. Conversion d’une base à une autre

De manière générale, on calcule dans une base privilégiée (pour nous, la base 10) et il s’agit de convertir un entiers depuis, ou vers, une base b auxiliaire.

1. « The word “hexadecimal,” which has crept into our language even more recently, is a mixture of Greek and Latin stems ; more proper terms would be “senidenary” or “sedecimal” or even “sexadecimal,”

but the latter is perhaps too risqué for computer programmers. » ([?])

6 CHAPITRE 1. NOMBRES ENTIERS

Un certain nombre de conversions sont très faciles à faire en pratique, il s’agit de passer d’une base b à une base qui en est une puissance, disons b^k. En effet, on re- groupe juste les termes k par k. Dans l’autre sens, chaque « chiffre » en base b^k doit être remplacé par son développement en base b, éventuellement complété avec des zéros en tête pour occupper exactement k chiffres en base b.

Pour convertir depuis une autre base b, il s’agit essentiellement d’évaluer le poly- nôme à coefficients entiers P = arX^r+ · · · + a0en b. Le schéma de Hörner représente cette expression comme

P = (((arX + ar −1) X + ar −2) + ··· + a1) X + a0

qu’on évalue de l’intérieur vers l’extérieur.

PROPOSITION1.1.2 (Schéma de Hörner). — On définit une suite (u_r, . . . , u₀) par récur- rence descendante en posant

ur = ar, ui= u_{i +1}b + aipour 06i < r . Alors, u₀= [ar. . . a₀]_b.

Dans l’autre sens, on procède par divisions euclidiennes successives par b :

PROPOSITION1.1.3. — Soit n un entier naturel strictement positif. On définit des suites (u_i) et (a_i) par récurrence en posant u₀= n puis, si u0, . . . , u_i sont définis et u_i > 0, on pose a_i le reste de la division euclidienne de u_i par b et u_{i +1}son quotient. Si r est le plus grand entier tel que u_r soit défini, on a alors n = [ar. . . a₀]_b.

C. Taille des données

Discutons rapidement de la taille mémoire requise pour stocker un entier lorsqu’on l’écrit en base b. Si n = [ar. . . a₀]_b, on doit connaître les r + 1 entiers a0, . . . , a_r. Dans l’hypothèse où la structure de l’ordinateur lui permet de manipuler naturellement un entier entre 0 et b − 1, la représentation de n occupe donc r + 1 mots. Puisque n vérifie l’encadrement

b^r6ⁿ6(b − 1)b^r+ · · · + (b − 1)b + (b − 1) = b^{r +1}− 1, on a

r log b6log n < (r + 1)logb,

soit encore r = blogbnc, où l’on note log_ble logarithme en base b.

Il faut retenir de cela que la taille mémoire requise par le stockage d’un entier n est de l’ordre de log n. C’est aussi le temps requis pour le lire, ou pour l’écrire.

Il faut réfléchir cinq minutes à l’efficacité de la notation mathématique qui peut re- présenter avec un mot de longueur` des objets d’une taille exponentiellement plus grande. On estime à 10⁸⁰le nombre d’atomes dans l’univers, mais il suffirait d’une ligne pour l’écrire en base 10.

§1.2. LES QUATRE OPÉRATIONS 7

§1.2. Les quatre opérations A. Addition et soustraction

Ces opérations sont faciles à effectuer, la méthode que l’on apprend à l’école élé- mentaire étant essentiellement optimale. Il faut partir de la fin et additionner les chiffres un à un, en reportant la retenue éventuelle.

Pour additionner/soustraire deux entiers de r + 1 chiffres en base b, il faut ainsi ef- fectuer autant d’additions d’entiers compris entre 0 et b −1. Si ces dernières opérations sont jugées élémentaires, le nombre d’opérations à effectuer est donc (r + 1), ce qui se fait en un temps proportionnel à la lecture des données et à l’écriture du résultat.

On parle ainsi de complexité linéaire.

B. Multiplication

Soit à multiplier deux entiers, l’un de r +1 chiffres, l’autre de s +1 chiffres. Le résultat aura r + s + 1 ou r + s + 2 chiffres.

Algorithme naïf reposant sur l’expression [ar. . . a₀]_b[bs. . . b₀]_b=

r

X

i =0

ai[bs. . . b₀]_bbⁱ.

Chaque terme de la somme se calcule à l’aide de (s + 1) multiplications d’entiers de {0, . . . , b − 1}, à partir de la droite, et en tenant compte des retenues. La multi- plication finale par b^r ne coûte rien puisqu’elle consiste juste en un décalage des chiffres vers la gauche, en complétant par des zéros. Au final, il faut donc effectuer (r + 1)(s + 1) multiplications d’éléments de {0,...,b − 1}. S’y ajoutent r additions de nombres ayant s + 1 chiffres. La complexité obtenue, O((r + 1)(s + 1)) multiplications élémentaires, et autant d’additions, est quadratique en la taille des données.

C. Division euclidienne

On veut effectuer la division euclidienne (quotient et reste) de deux entiers N et M écrits en base b. Si le dividende N possède n chiffres et le diviseur M en a m, le quo- tient Q aura n − m chiffres, et le reste R en aura moins de m. La méthode de l’école élémentaire s’applique encore : on calcule un par un les chiffres de Q en partant de la gauche, et en soustrayant de N ce qui doit l’être. Chaque étape requiert donc m mul- tiplications et additions, soit, au total O(m(n − m)) opérations élémentaires, auquel il faut ajouter le coût de la détermination des chiffres du quotient où, comme à l’école élémentaire, se loge la difficulté essentielle. Cela se fait en ne considérant que les m (ou m+1) premiers chiffres du diviseur ; autrement dit : comment déterminer le quotient q de [N_m+1. . . N₀]_bpar [M_m. . . M₀] lorsque ce quotient est compris entre 0 et b ?

Lorsque b est petit, il est possible d’essayer les quotients successifs, un par un, voire de procéder par dichotomie. Mais l’école élémentaire nous apprend à deviner les chiffres du quotients en ne regardant que les premiers chiffres du diviseur et du dividende et cette méthode se généralise. Soit

q = minˆ µ

bN_m+1b + Nm

M_m c, b − 1

¶

8 CHAPITRE 1. NOMBRES ENTIERS

le quotient estimé à l’aide des deux premiers chiffres du diviseur et du premier chiffre du dividende, ramené à b − 1 s’il était plus grand que b. (Comme il se doit, on suppose M_m> 0, mais on pourrait avoir N_m+1= 0 si, après un quotient nul, on avait dû abaisser un chiffre de plus.)

PROPOSITION1.2.1. — On a q6q. Si de plus M^ˆ m>bb/2c, on a aussi ˆq − 26^q.

Démonstration. — Démontrons la première inégalité. Si ˆq = b(N_m+1b + Nm)/M_mc, on a

qˆ6^{Nm+1b + Nm}

M_m < ˆq + 1, d’où

q Mˆ _m> (N_m+1b + Nm) − Mm

et donc

q Mˆ _m>^(Nm+1b + Nm) − (Mm− 1).

Par conséquent,

N − ˆq M6N − ˆq M_mb^m

6^¡Nm+1b^m+1+ Nmb^m+ · · · + N1b + N0¢ − (N_m+1b + Nm) b^m+ (Mm− 1)b^m 6^¡Nm−1b^m−1+ · · · + N1b + N0¢ + (Mm− 1)b^m

6^¡bm− 1¢ + (Mm− 1)b^m6^Mmb^m− 1 < M.

Comme 06N − qM < M, on a donc ˆq>^q.

Pour démontrer la seconde inégalité, commençons par observer que qˆ6^{Nm+1b + Nm}

M_m =N_m+1b^m+1+ Nmb^m

M_mb^m 6 ^N

M_mb^m 6 ^N M − b^m+ 1 puisque

M_mb^m= M −¡M_m−1b^m−1+ · · · + M0

¢ >M − (b − 1)b^m−1− · · · − (b − 1) = M − b^m+ 1.

Dans le cas où M = b^m, on a évidemment ˆq = Nm+1b + Nm= q. Supposons donc que l’on a M > b^m; il vient alors ˆq < N /(M − b^m). Comme 06N − qM6M − 1 < M, on en déduit

( ˆq − q)M < (−N + M) + N M

M − b^m 6M + N b^m M − b^m, d’où

q − q < 1 +ˆ N M

b^m M − b^m. Supposons par l’absurde que ˆq − q>3 ; il vient alors

N

M > 2M − b^m

b^m >^2(Mm− 1).

Par suite,

2(M_m− 1)6

¹N M

º

= q6q − 3^ˆ 6b − 4,

d’où l’on tire l’inégalité M_m6¹₂b−1, contrairement à l’hypothèse que Mm>^bb/2c.

§1.2. LES QUATRE OPÉRATIONS 9

Pour faire usage de ce résultat, il suffit, avant d’effectuer une division, de multiplier le diviseur et le dividende par un même entier d de sorte à ce que la condition de la proposition soit vérifiée. On peut prendre d = bb/Mmc mais choisir une puissance de 2 est préférable dans un ordinateur. On calcule alors Q⁰et R⁰tels que N d = Q⁰Md + R⁰ et 06^R0< Md par la méthode indiquée. Pour terminer le calcul, il reste à effectuer la division euclidienne de M⁰par d , disons M⁰= q⁰d + r⁰, d’où N = Q⁰M + q⁰et r⁰= 0. On pose donc Q = Q⁰et R = q⁰.a En fait, [?] propose même une amélioration de ce résultat qui tient compte du chiffre suivant dans le développement de M et N .

D. Exponentiation

Il s’agit d’une méthode efficace pour calculer des puissances dans un groupe (ou, plus généralement, dans un monoïde).

Si n est un entier et a un élément d’un monoïde G, le calcul naïf de aⁿpar la formule aⁿ= a(aⁿ⁻¹) et itération requiert n − 1 multiplications dans G.

En utilisant le développement en base 2 de n, on peut grandement accélérer le pro- cessus. Cela repose sur les formules

aⁿ=

((a²)^n/2 si n est pair ; a(a²)^(n−1)/2 si n est impair.

Notons n = [nr. . . n₀]₂le développement binaire de n. Pour calculer aⁿ, on effectue r élévations au carré (calculs successifs de a², . . . , a^2r) et des multiplications dans G dont le nombre est égal à la somme des chiffres binaires de n (moins 1), soitP ni. Le nombre M (n) d’opérations dans G pour calculer aⁿest donc majoré par 2r , d’où une complexité linéaire.

CHAPITRE 2

ALGORITHME D’EUCLIDE

§2.1. L’algorithme d’Euclide étendu A. Anneaux euclidiens

Soit A un anneau (commutatif unitaire) intègre et soit w : A\{0} → N une application de A dans l’ensemble des entiers naturels. On dit que w est une jauge euclidienne si les deux propriétés suivantes sont satisfaites :

a) pour tout a ∈ A et tout b ∈ A \ {0}, il existe un couple (q,r ) d’éléments de A tels que a = bq + r avec ou bien w(r ) < w(b), ou bien r = 0 ;

b) pour tous a et b ∈ A \ {0}, w(ab)>^{w (a).}

On dit que A est un anneau euclidien s’il possède une jauge euclidienne.

On remarquera qu’on n’impose pas l’unicité d’un tel couple (q, r ) dans la définition d’une jauge. De plus, la jauge est à valeurs entières, mais tout ensemble bien ordonné ferait l’affaire. Enfin, certain auteurs omettent le second axiome de la définition d’un anneau euclidien. Ce n’est pas tellement gênant ; en effet, on peut démontrer que l’en- semble des fonctions satisfont le premier axiome admet un plus petit élément (dé- fini point par point en prenant le minimum) et que cette fonction est une jauge eucli- dienne.

Exemple 2.1.1. — L’anneau Z des entiers relatifs est euclidien, l’application w : (Z \ {0}) → N donnée par n 7→ |n| est une jauge euclidienne.

Le premier axiome est vérifié en prenant pour (q, r ) le quotient et le reste de la divi- sion euclidienne de a par b. Par définition, on a 06r < |b|.

Le second est évident car |n|>1 pour tout n ∈ Z \ {0}.

Exemple 2.1.2. — Soit K un corps. L’anneau K [X ] des polynômes en une variable à coefficients dans K est euclidien, l’application degré (K [X ] \ {0}) → N étant une jauge euclidienne.

Exemple 2.1.3. — Les anneaux Z[i ] et Z[ j ] (avec i²= −1 et j²+ j + 1 = 0) sont des an- neaux euclidiens ; dans ces deux cas, l’application z 7→ z ¯z est une jauge.

PROPOSITION2.1.4. — Un anneau euclidien est un anneau principal : il est intègre et tous ses idéaux sont principaux.

12 CHAPITRE 2. ALGORITHME D’EUCLIDE

Démonstration. — Soit A un anneau euclidien, soit w une jauge euclidienne et soit I un idéal de A. L’idéal nul étant principal, supposons I 6= (0). L’ensemble des w(a), pour a ∈ I \ {0}, est un ensemble non vide d’entiers naturels ; il possède donc un plus petit élément m. Soit b ∈ I \ {0} tel que w(b) = m et démontrons que I = (b). Pour a ∈ A, on a ab ∈ I car b ∈ I et I est un idéal. Inversement, soit a ∈ A et soit (q,r ) un couple d’éléments de A tel que a = bq + r et r = 0 ou w(r ) < w(b). Comme r = a − bq et que a, b ∈ I , on a r ∈ I . Si l’on avait r 6= 0, on en déduirait que w(r )>m = w(b), ce qui est absurde ; donc r = 0 et a ∈ (b).

B. L’algorithme d’Euclide étendu

Il s’agit de l’algorithme suivant. Soit A un anneau euclidien pour une jauge w . Soit (a, b) un couple d’éléments de A. On pose

a₀= a u₀= 1 v₀= 0

a₁= b u₁= 0 v₁= 1.

Puis, si (an, un, vn) sont définis et an6= 0, on se donne qnet rntels que a_n−1= anq_n+rn

et w (rn) < w(an) ou rn= 0 et l’on pose

a_n+1= a_n−1− qna_n u_n+1= u_n−1− qnu_n v_n+1= v_n−1− qnv_n. Par récurrence, on a a_n= aun+ bvnpour tout n tel que a_n, u_n, v_nsoient définis.

L’algorithme s’arrête lorsque a_n+1= 0.

THÉORÈME2.1.5. — L’algorithme s’arrête toujours.

Démonstration. — En effet, la suite w (a_n) est strictement décroissante tant qu’elle est définie. Comme elle prend des entiers positifs, elle est finie.

Posons d = an, u = un, v = un. La relation d = au + bv est appelée relation de Bézout pour a et b. L’élément d construit est un plus grand dénominateur commun de a et b ; cela signifie les choses suivantes :

a) L’élément andivise a et b. Démontrons par récurrence descendante sur m6n+1 que andivise am. C’est vrai si m = n + 1 (car andivise a_n+1= 0) et si m = n (puisque an

se divise lui-même). Supposons que an divise am, a_m+1, etc. ; par définition de a_m+1, on a une relation de la forme a_m+1= a_m−1− qam, avec q ∈ A, ce qui entraîne que an

divise a_m+1 et am, il divise a_m−1 = a_m+1+ qam. Par récurrence, an divise a1= b et a₀= a.

b) Si un élement x de A divise a et b, il divise an. Cela est évident sur la relation an= aun+ bvn.

Observons aussi que d est un générateur de l’idéal (a, b).

§2.2. COMPLEXITÉ DE L’ALGORITHME D’EUCLIDE POUR LES ENTIERS 13

C. Groupe spécial linéaire

On peut récrire les relations de récurrence de l’algorithme d’Euclide étendu sous la forme

µ a_n u_n v_n a_n+1 u_n+1 v_n+1

¶

=µ0 1 1 −qn

¶ µa_n−1 u_n−1 v_n−1 a_n u_n v_n

¶ ,

où qn est un élément de A tel que a_n−1− qan= 0 ou w(a_n−1− qan) < w(an). On en déduit

µd u v

0 u^∗ v^∗

¶

=µ0 1 1 −qn

¶ µ0 1 1 −qn−1

¶

. . .µ0 1 1 −q1

¶ µa 1 0 b 0 1

¶

Le produit des n matrices 2 × 2 du membre de droite appartient à GL2(A), est de déter- minant (−1)ⁿ, et applique le vecteur (a, b) sur le vecteur (d , 0). Son inverse applique le vecteur (1, 0) sur le vecteur (a/d , b/d ).

Soit M une matrice de SL2(A) et soit (a, b) sa première colonne. Le pgcd de a et b est une unité. On construit alors une matrice U ∈ SL2(A), produit de matrices de la forme¡_{0 1}

1 −q¢, telle que U M applique le vecteur (1,0) sur lui-même. Autrement dit, U M est de la forme¡_{1 z}

0 1¢.

CORRIGER : Comme µ1 z

0 1

¶

=µ 0 1

−1 −1

¶ µ 0 1

−1 −1

¶ µ 0 1

−1 −z

¶ ,

on en conclut au passage que le groupe SL₂(A) est engendré par les matrices de la forme¡ _{0 1}

−1 q¢.

Dans l’autre sens, la formule µ 0 1

−1 z

¶

=µ1 1 0 1

¶ µ 1 0

−1 1

¶ µ1 1 − z

0 1

¶

entraîne que le groupe SL₂(A) est engendré par les matrices de la forme¡_{1 q}

0 1¢ et ¡_{q 1}^{1 0}¢.

D. Application au calcul modulaire

Soit A un anneau et a un élément de A qui n’est ni nul ni inversible. Lorsque A est euclidien, l’algorithme d’Euclide étendu permet de calculer des inverses dans l’anneau quotient A/(a).

Soit b ∈ A. Supposons sa classe inversible dans A/(a) ; il existe alors v ∈ A tel que bv ≡ 1 (mod a), donc u ∈ A tel que bv = 1 − au. La relation au + bv = 1 entraîne que a et b sont premiers entre eux.

Inversement, si a et b sont premiers entre eux, l’algorithme d’Euclide étendu produit une relation au + bv = d, où d est inversible dans A. Alors, a(u/d) + b(v/d) = 1, et la classe de v/d est l’inverse de celle de b dans A/(a).

§2.2. Complexité de l’algorithme d’Euclide pour les entiers

Commençons par analyser le nombre d’opérations requises par le calcul du pgcd de deux entiers strictement positifs a et b. L’argument qu’on a utilisé pour assurer

14 CHAPITRE 2. ALGORITHME D’EUCLIDE

que l’algorithme se termine est la décroissance de la suite (an). Si l’algorithme s’ar- rête à l’étape N (a, b) (c’est-à-dire a_{1+N (a,b)} = 0), on a donc N (a, b)6b. Nous allons voir qu’une bien meilleure inégalité est satisfaite.

La suite de Fibonacci (F_n) est définie par F₀= 0, F1= 1 et F_n+1= Fn+ F_n−1pour tout entier n>1. Les racines du polynôme x²− x − 1 sont (1 ±p

5)/2 ; par conséquent, il existe des nombres réels u et v tels que

F_n= u¡ 1+p 5 2

¢n

+ v¡ 1−p 5 2

¢n

, pour tout n. En particulier, 0 = u + v et 1 = u¹⁺

p5 2 + v¹⁻

p5

2 , d’où l’on tire u = −v = 1/p 5.

PROPOSITION2.2.1. — Si a > b et n = N (a,b), alors a>^Fn+2et b>^Fn+1.

Démonstration. — Démontrons ceci par récurrence sur n. Si n = 1, il suffit de démon- trer a>^F3et b>^F2, inégalités toutes deux vraies puisque F2= 1 et F3= 2 (et a > b > 0, donc a>^2).

Supposons le résultat vrai si N (a, b) < n. Par construction, n = N (a,b) = N (a0, a1) = 1+N (a1, a₂). De plus, a₁> a2(car a₂est le reste de la division euclidienne de a₀par a₁).

On a donc a₁>^Fn+1 et a₂>^Fn. Puisque a₀= q0a₁+ a2et q₀>1, on en déduit a₀>

a₁+ a2>^Fn+1+ Fn= F_n+2.

On a F₂= 1 et pour n>^{2, F}n+1= Fn+ F_n−1> Fn. Par conséquent, si n>2, le reste de la division euclidienne de F_n+1par F_nest égal à F_n−1. Si l’on pose ainsi a = F_n+2et b = F_n+1, on a a_k= F_n+2−k pour tout k tel que n + 2 − k > 1, donc en particulier an= F2= 1.

Alors, a_n+1= 0. Cela montre que les inégalités de la proposition sont optimales.

COROLLAIRE2.2.2. — Si a > b > 0, on a N (a,b) < O(logb).

Démonstration. — En effet, si n = N (a,b), on a b>^Fn+1= 1

p5

¡ 1+p 5 2

¢_n+1

− 1 p5

¡ 1−p 5 2

¢_n+1

>p¹ 5

¡ 1+p 5 2

¢_n+1

− 1, d’où l’inégalité

n6^{log¡ 2} p5 1 +p

5(b + 1)¢/log¡1 +p 5

2 ¢ = O(logb).

Ces inégalités majorent le nombre de pas effectués par l’algorithme mais pas tout à fait la complexité de l’algorithme lui-même. En effet, la complexité des divisions eucli- diennes dépend de leurs arguments. Une majoration simple consiste à observer que les a_i sont majorés par a, si bien que chaque division requiert O(log a)²opérations ; la complexité totale est ainsi majorée par O(log a)³.

On peut être plus précis en utilisant le fait que les a_i diminuent. En effet, la division euclidienne de a_k−1par a_krequiert O(log(q_k) log(a_k)) opérations par la méthode naïve.

§2.3. COMPLEXITÉ DANS LE CAS DES POLYNÔMES 15

Par suite, le nombre d’opérations que l’algorithme d’Euclide effectue est majoré par un multiple de

n

X

k=1

log(qk) log(ak)6^log(b)X

k

= 1ⁿlog(qk).

Les relations a_k−1= qka_k+ a_k+1entraînent a_k−1>^qka_k, d’où q₁. . . q_n6^a0/a_n6^a0. COROLLAIRE2.2.3. — On peut calculer le pgcd de deux entiers positifs a > b et une relation de Bézout en O(log(a) log(b)) opérations.

Démonstration. — L’assertion concernant le pgcd est déjà vue. Pour la relation de Bé- zout, le raisonnement est analogue.

§2.3. Complexité dans le cas des polynômes A. Une première majoration

Soit K un corps et a, b des polynômes de K [X ], supposés non nuls. Le calcul de leur pgcd requiert au plus 1 + deg(b) étapes : la suite des degrés des an étant strictement décroissante tant qu’elle est définie, on a deg(an)6^deg(a1) +1−n = deg(b)+1−n. Par conséquent, si la suite (a_k) est définie pour n = deg(b) + 1, on trouve deg(an)6^{0 donc} a_n+1= 0.

PROPOSITION2.3.1. — Pour calculer le pgcd de a et b, ainsi qu’une relation de Bézout, on doit effectuer au plus

O((1 + deg(a))(1 + deg(b)))

additions et multiplications, et (1 + deg(b)) inversions dans le corps K B. Explosion des coefficients et normalisations

L’analyse précédente suppose que les opérations dans le corps K ont une complexité indépendante des données ; c’est bien ce qui se passe si K est un corps fini. En re- vanche, lorsque K = Q, le corps des nombres rationnels, il faut en outre se préoccuper de la taille des nombres qui apparaissent.

Or, l’algorithme, tel qu’il a été énoncé plus haut, fait apparaître une explosion des coefficients qui, au moins en apparence, ruine la borne de complexité que nous avons calculée.

Un remède (partiel) consiste à normaliser les restes de la division euclidienne, de sorte que la suite (an) est constituée de polynômes unitaires.

C. Une majoration du résultat

CHAPITRE 3

NOMBRES PREMIERS, FACTORISATION

Rappelons qu’on dit qu’un nombre entier p > 1 est un nombre premier s’il n’est di- visible par aucun autre nombre entier positif que 1 et lui-même.

Au delà de l’intérêt théorique qu’ils suscitent, les nombres premiers sont devenus un outil important pour certaines applications des mathématiques à la vie courante, notamment la cryptographie ou la signature électronique (Internet...) et les codes cor- recteurs d’erreurs utilisés en télécommunication numérique.

La production de nombres premiers « aléatoires » de grande taille est ainsi deve- nue une activité courante, rendant nécessaire le développement de méthodes efficaces permettant d’affirmer qu’un nombre entier donné n est, ou n’est pas, un nombre pre- mier.

On noteraP l’ensemble des nombres premiers.

§3.1. Nombres premiers

A. Définition, crible d’Ératosthène

Il convient de remarquer que tout nombre entier strictement supérieur à 1 est mul- tiple d’un nombre premier : c’est clair s’il est lui-même premier et dans le cas contraire, c’est un multiple de deux nombres entiers strictement plus petits qui sont par récur- rence multiples d’un nombre premier. On peut encore raffiner cette remarque : tout nombre entier n strictement supérieur à 1 qui n’est pas premier est divisible par un nombre premier au plus égal àp

n.

Cette remarque faite, on peut alors commencer à énumérer les éléments de P ^à l’aide du crible d’Eratosthène qui consiste à écrire les nombres entiers 2, . . . , jusqu’à un certain point, disons 20 :

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

puis à raisonner de la façon suivante. L’entier 2 est premier, donc ses multiples 4, 6, . . . ne le sont pas ; on les raye :

2, 3,
4, 5,
6, 7,8, 9,
_10, 11, _12, 13, _14, 15, _16, 17, _18, 19, _20.

18 CHAPITRE 3. NOMBRES PREMIERS, FACTORISATION

Après 2, le premier entier non rayé, en l’occurence 3, est forcément un nombre pre- mier : dans le cas contraire, il aurait été multiple d’un nombre premier déjà détecté ; on le sélectionne et on raye ses multiples 6, 9, . . . :

2, 3,4, 5,

6, 7,
8,9,
_10, 11, _12, 13, _14,_15,_16, 17, _18, 19, _20. De même, 5 est premier, on raye ses multiples :

2, 3,
4, 5,6, 7,

8,
9,_10, 11, _12,_13,_14,_15,_16, 17, _18, 19, _20.

On constate cependant qu’on n’a rien rayé de nouveau. En effet, 5² > 20 donc les nombres entiers inférieurs à 25 sont ou bien premiers, ou bien sont divisibles par un nombre premier au plus égal à 5. Par le même argument, tous ceux qui restent sont des nombres premiers, d’où le début de l’énumération :

P∩ [1, 20] = {2, 3, 5, 7, 11, 13, 17, 19}.

B. Test de divisibilité

Si l’on veut déterminer la primalité d’un entier n, on peut s’appuyer sur la définition, c’est-à-dire effectuer les divisions par tous les entiers inférieurs à n ou plutôt, comme on l’a vu, inférieurs àp

n. Cette méthode est rapidement impraticable si n a plus de quelques chiffres. Le bon paramètre est en effet le nombre de chiffres de n, c’est-à- dire, à un factor près, le logarithme de n.

C. Témoins de primalité ou de non-primalité ; algorithmes probabilistes

Les algorithmes dont nous allons parler ici résultent le plus souvent de théorèmes qui prennent l’une des formes suivantes :

– si n est premier, tout entier a tel que 16^a6n vérifie une certaine propriété P (a).

Dans ce cas, il suffit d’exhiber un entier a tel que la propriété ne soit pas satis- faite pour en déduire que n n’est pas premier ; un tel a sera appelé témoin de non-primalité. En revanche, savoir que tout entier a vérifie P (a) n’impliquera pas toujours que n soit un nombre premier.

– si n est premier, il existe un entier b, dans [1, n] vérifiant une propriété Q(b). On dira que b est un témoin de primalité. car exhiber un entier b vérifiant Q(b) prouve que b est un nombre premier.

Dans l’un et l’autre cas, il n’est cependant pas toujours raisonnable de tester tous les entiers successivement, à moins de savoir qu’il existe un entier a vérifiant P (a), ou un entier b vérifiant Q(b), qui soit de taille modérée.

Si l’on sait qu’une proportion importante des est constituée de témoins de primalité , on peut tester la propriété Q(b) sur des entiers b pris au hasard : si n est premier, la probabilité qu’aucun des entiers choisis ne soit un témoin de primalité, est égale à (1 − π)^−k siπ est la densité des témoins de primalité et k le nombre d’essais, donc décroît très rapidement avec k. Le test obtenu est ainsi appelé probabiliste.

§3.1. NOMBRES PREMIERS 19

D. Critère de Fermat

Ce test repose sur le « petit théorème de Fermat » :

PROPOSITION3.1.1. — Soit p un nombre premier ; pour tout entier a qui n’est pas mul- tiple de p, on a a^p−1≡ 1 (mod p).

Démonstration. — L’ensemble des éléments non nuls du corps Z/pZ est un groupe pour la multiplication ; son cardinal est p − 1. Par conséquent, pour tout α ∈ (Z/pZ)^×, α^p−1= 1. Traduit en termes de nombres entiers, on obtient a^p−1≡ 1 (mod p) si a est un entier qui n’est pas multiple de p.

Cette proposition fournit un test de non-primalité : si n est un nombre entier, il suf- fit d’exhiber un nombre entier a dans l’intervalle [1, n − 1] tel que a^{r −1}6≡ 1 (mod n) pour en déduire que n n’est pas un nombre premier. On l’appelle le test de Fermat. On observera que la donnée d’un tel a prouve que n n’est pas premier sans pour autant l’écrire comme produit de deux entiers inférieurs à n.

Toutefois, il existe des nombres entiers n, appelés nombres de Carmichael, vérifiant la propriété suivante : tout entier a tel que 16a < n qui est premier à n vérifie aⁿ⁻¹≡ 1 (mod n). Pour ces nombres entiers-là, les seuls témoins de non-primalité sont les en- tiers a qui ne sont pas premiers à n et fournissent ainsi automatiquement une factori- sation partielle de n. Le plus petit d’entre eux, découvert justement par Robert Carmi- chael en 1910, est 561. Un théorème démontré par les mathématiciens Alford, Granville et Pomerance en 1994 affirme qu’il existe une infinité de nombres de Carmichael.

Malgré ce défaut, le test de Fermat est utilisé par l’algorithme de cryptagePGPpour décider qu’un nombre entier donné est premier ; la probabilité qu’il échoue étant considérée comme négligeable.

PROPOSITION3.1.2. — Soit n un nombre entier > 1 qui n’est ni un nombre premier, ni un nombre de Carmichael, Alors, au moins la moitié des nombres entiers a de [1, n] qui sont premiers à n sont des témoins de non-primalité pour le test de Fermat.

Démonstration. — Soit G le groupe (Z/nZ)^∗et soit F l’ensemble des éléments de G qui ne sont pas des témoins de non-primalité pour le test de Fermat. Autrement dit, F est l’ensemble des a ∈ G tels que aⁿ⁻¹≡ 1 (mod n). C’est un sous-groupe de G. Comme n n’est ni premier ni un nombre de Carmichael, c’est un sous-groupe strict donc son indice (G : F ) est au moins égal à 2, d’où la proposition.

Remarque 3.1.3. — Soit n un nombre de Carmichael et soit n =Q_u

i =1pⁿ_iⁱ sa décompo- sition en facteurs premiers.

Comme −1 est d’ordre 2 dans (Z/nZ)^∗, l’hypothèse que n est de Carmichael entraîne (−1)ⁿ⁻¹≡ 1, donc n est impair.

Soit a ∈ (Z/nZ)^∗ et soitωi l’ordre de a modulo p_iⁿⁱ. Par hypothèse, ωi divise n − 1, mais il divise aussi le cardinal de (Z/pⁿ_iⁱZ)^∗ c’est-à-dire p_iⁿⁱ⁻¹(p_i− 1). Comme n − 1 est premier à pⁿ_iⁱ⁻¹,ωidivise pgcd(p_i− 1, n − 1). La classe de a dans le groupe cyclique (Z/pⁿ_iⁱZ)^∗appartient en particulier à un sous-groupe d’ordre p_i−1, d’où card(Z/nZ)^∗6 Q_u

i =1(p_i− 1) par le lemme chinois. Cela entraîne que ni= 1 pour tout i .

20 CHAPITRE 3. NOMBRES PREMIERS, FACTORISATION

D’autre part, si l’on avait u = 2, on aurait

pgcd(p₁− 1, n − 1) = pgcd(p1− 1, (p1− 1)p2+ (p2− 1) = pgcd(p1− 1, p2− 1).

Notons d ce pgcd. La classe de a dans chacun des groupes cycliques (Z/p₁Z) et (Z/p2Z) appartient à un sous-groupe d’ordre d ; on a donc

(p₁− 1)(p2− 1) = card(Z/nZ)^∗6^d2, ce qui est absurde : si p1< p2, alors d6^p1− 1 et d²6^(p1− 1)². E. Critère de Lucas

Il repose sur les propriétés des groupes abéliens finis.

LEMME3.1.4. — Soit G un groupe abélien fini, noté multiplicativement. Soit g et h des éléments de G d’ordres m et n. Si m et n sont premiers entre eux, alors g h est d’ordre mn.

Démonstration. — Observons que les sous-groupes 〈g 〉 et 〈h〉 n’ont pas d’autre élé- ment commun que 1. En effet, l’ordre d’un élément commun doit diviser m et n, donc est égal à 1. Par suite, si (g h)^N = 1, qu’on peut récrire g^N = h^−N puisque G est commu- tatif. D’après la remarque faite, g^N= h^−N= 1 ; ainsi, N est multiple de m et de n, donc de mn. Inversement, (g h)^mn= g^mnh^mn= 1.

PROPOSITION3.1.5. — Soit G un groupe abélien fini, noté multiplicativement. Pour toute partie S de G, il existe un élément de G dont l’ordre est le plus petit multiple com- mun des ordres des éléments de S. En particulier, il existe dans G un élément dont l’ordre est multiple de l’ordre de chaque élément de G.

Démonstration. — Par récurrence, il suffit de démontrer si G possède deux élé- ments g et h d’ordres m et n, il possède un élément d’ordre ppcm(m, n). Comme ordp(ppcm(m, n)) = max(ordp(m), ordp(n)), on peut écrire m = m⁰m⁰⁰et n = n⁰n⁰⁰, où les facteurs premiers de m⁰et n⁰ sont ceux tels que ordp(m)>^ordp(n), ceux de m⁰⁰ et n⁰⁰ étant ceux tels que ordp(n) > ordp(m). Alors, g^m00 est d’ordre m⁰, tandis que hⁿ⁰ est d’ordre n⁰⁰. Les entiers m⁰ et n⁰⁰ sont premiers entre eux, leur produit est égal au plus petit multiple comun de m et n ; d’après le lemme, l’ordre de g^m00hⁿ⁰ est égal à ppcm(m, n).

Nous pouvons maintenant énoncer le théorème qui donne lieu au critère de prima- lité de Lucas-Lehmer.

THÉORÈME3.1.6. — Soit n un entier > 1. Supposons que pour tout facteur premier p de n − 1, il existe un entier a tel que aⁿ⁻¹≡ 1 (mod n) et a^(n−1)/p6≡ 1 (mod n). Alors, n est un nombre premier.

Démonstration. — Si a est un entier tel que aⁿ⁻¹≡ 1 (mod n), observons que a et n sont premiers entre eux. L’hypothèse signifie donc qu’il existe, pour tout facteur pre- mier p de n − 1, un élément ap du groupe (Z/nZ)^× dont l’ordre divse n − 1 mais ne divise pas (n − 1)/p. Le plus petit multiple commun des ordres de ces éléments ap di- vise n − 1 mais n’est pas un diviseur strict de n − 1 ; il est donc égal à n − 1. D’après la

§3.1. NOMBRES PREMIERS 21

proposition 3.1.5, le groupe (Z/nZ)^× possède un élément d’ordre n − 1. Cela impose que (Z/nZ)^×soit d’ordre au moins n − 1, donc que n soit un nombre premier.

Considérons par exemple l’entier n = 571 ; puisque l’on a n − 1 = 570 = 2 × 3 × 5 × 19,

il suffit de trouver dans le groupe (Z/571Z)^∗ quatre éléments d’ordres ne divisant pas 570/p pour p = 2,3,5,19, autrement dit quatre entiers xptels que 571 divise x⁵⁷⁰_p −1, tandis que x_p^570/pet 571 soient premiers entre eux.

Lorsque p = 2, 570/p = 285 et x2= −1 convient. Voyons si x = 2 convient : on a 570/3 = 190, 570/5 = 114 et 570/19 = 30. On a respectivement

2⁵⁷⁰≡ 1, 2¹⁹⁰≡ 461, 2¹¹⁴≡ 1, 2³⁰≡ 306 (mod 571).

En particulier, l’ordre de 2 dans (Z/571Z)^∗ divise 570 mais ne divise pas 570/p si p = 3 ou 19. Il reste à trouver un entier x convenant pour p = 5 ; comme 3¹¹⁴ ≡ 481 (mod 571), il convient et cela conclut la démonstration que 571 est un nombre premier.

Le défaut de ce critère est de nécessiter la factorisation de n − 1, mais des variantes permettent de se contenter d’une factorisation partielle, cf. l’exercice 3.1.10. Son inté- rêt est qu’il produit un certificat de primalité : la simple donnée des entiers x₂= −1, x₃= 2, x5 = 3 et x19 = 2 permet à n’importe qui de vérifier rapidement que 571 est effectivement un nombre premier.

Il est néanmoins utile lorsque n est un nombre de Fermat, c’est-à-dire de la forme 2^2r+ 1 ; on obtient alors le critères de Pépin et de Proth :

COROLLAIRE3.1.7 (Critères de Pépin–Proth). — Soit r un nombre entier tel que r>^2.

Pour que le nombre de Fermat F_r = 2^2r+ 1. soit un nombre premier, il faut et il suffit que l’on ait l’une des congruences suivantes :

a) 3^(Fr−1)/2≡ −1 (mod Fr) ; b) 5^(Fr−1)/2≡ −1 (mod Fr).

Démonstration. — Comme F_r− 1 = 2^2r, la suffisance de ces conditions résulte du cri- tère de Lucas. Supposons inversement que F_r soit un nombre premier et vérifions ces deux congruences. Elles signifient en fait que 3 et 5 ne sont pas des carrés modulo F_r et résultent immédiatement de la loi de réciprocité quadratique de Gauß compte tenu des congruences F_r≡ 1+(−1)^2r≡ 2 (mod 3) et Fr ≡ 1+4^{2r −1}≡ 1+(−1)^{2r −1}≡ 2 (mod 5).

Voir l’exercice 3.1.11 pour une démonstration des cas de la loi de réciprocité quadra- tique qui ont été utilisés dans la démonstration précédente.

Sous les hypothèses du critère de Lucas, le groupe multiplicatif (Z/nZ)^×est cyclique.

Il est important de savoir que cette propriété est vérifiée pour tout nombre premier puisque cela montre que les hypothèses de ce critère sont aussi nécessaires. Plus gé- néralement :

THÉORÈME3.1.8. — Soit F un corps commutatif et soit G un sous-groupe fini de F^×. Alors G est cyclique.

22 CHAPITRE 3. NOMBRES PREMIERS, FACTORISATION

Démonstration. — Soit g un élément de G dont l’ordre, disons n, est multiple de l’ordre de tout élément de G. Tout élément x de G vérifie xⁿ= 1. Comme F est un corps commutatif, l’équation polynomiale xⁿ = 1 dans F a au plus n solutions. Comme les n éléments 1, g , g², . . . , gⁿ⁻¹du sous-groupe de G engendré par g sont solutions, on a nécessairement G = 〈g 〉.

Seconde démonstration. — Soit n l’ordre de G. D’après le lemme et une récurrence évidente, il suffit de produire, pour tout facteur premier p de G, un élément g_p de G dont l’ordre est p^ordp(n). En effet, le produit des g_p sera un élément de G d’ordre n.

Comme F est un corps commutatif, l’équation polynomiale x^n/p= 1 a au plus n/p solutions ; comme G est d’ordre n > n/p, il existe donc un élément x de G tel que x^n/p6=

1. Posons alors y = x^n/pr. On a y^pr = 1 mais y^{pr −1} = x^n/p6= 1. Par suite, l’ordre de y est un diviseur de p^r qui ne divise pas p^{r −1}; c’est donc p^r et on peut poser gp= y.

L’intérêt de la seconde démonstration est qu’elle se prête au calcul effectif d’un gé- nérateur. Montrons-le sur un exemple, disons le calcul d’un générateur du groupe mul- tiplicatif (Z/71Z)^×. On a 71 − 1 = 70 = 2 × 5 × 7 ; d’après la démonstration, nous devons trouver des éléments d’ordres 2, 5 et 7.

Il est clair que g2= −1 est d’ordre 2. Cherchons un élément d’ordre 5 ; il suffit de trouver un élément x tel que x¹⁴6≡ 1 (mod 71). Essayons x = 2 :

2¹⁴≡ 4⁷≡ 4 · (16)³≡ 4 · (16) · (256) ≡ 64 · 43 ≡ −7 · 43 ≡ −301 ≡ −17 (mod 71).

Par suite, g₅= −17 est d’ordre 5. De même, cherchons un élément x tel que x¹⁰6≡ 1 (mod 71) et essayons encore x = 2 :

2¹⁰≡ 16 · 64 ≡ 16 · (−7) ≡ −112 ≡ 30 (mod 71) si bien que g₇= 30 est d’ordre 7. Leur produit

g₂g₅g₇≡ (−1) × (−17) × (30) ≡ 510 ≡ 13 (mod 71) est ainsi un générateur du groupe multiplicatif (Z/71Z)^×.

Remarque 3.1.9. — On peut raisonner à l’envers et se demander, un entier a étant donné, pour quels nombres premiers p est-ce que a est un générateur du groupe mul- tiplicatif (Z/pZ)^∗. Pour qu’un tel nombre premier impair existe, une condition néces- saire évidente est que a ne soit pas un carré : si p est impair, les carrés de (Z/pZ)^∗ forment un sous-groupe strict. De même, a = −1 n’est un générateur de (Z/p^Z)^∗que si p = 2 ou p = 3. Une conjecture du mathématicien Emil Artin est que ces deux condi- tions nécessaires sont suffisantes pour qu’il existe une infinité de tels nombres pre- miers ! Cette conjecture est toujours ouverte : on ne connaît à ce jour aucun nombre entier a pour lequel on sache qu’elle est vérifiée. Cependant, C. Hooley a démon- tré en 1967 qu’elle est vérifiée si l’hypothèse de Riemann généralisée l’est, tandis que R. Heath-Brown (1985), généralisant des travaux de R. Gupta et M. Ram Murty (1984), a montré qu’elle est vérifiée pour tout nombre premier a sauf au plus 2. Par exemple, des entiers 3, 5 et 7, au moins l’un est un générateur de (Z/pZ)^∗pour une infinité de nombre premiers p.

§3.1. NOMBRES PREMIERS 23

Exercice 3.1.10. — a) Soit N un entier tel que N >2. Soit p un nombre premier qui divise N − 1 et soit e le plus grand entier>1 tel que p^e divise N − 1. Soit a un entier tel que a^{N −1}≡ 1 (mod N ) et tel que a^{(N −1)/p}et N soient premiers entre eux. Soit` un nombre premier qui divise N .

Montrer que (la classe de) a est inversible dans (Z/`Z). Si t désigne son ordre, mon- trer les divisibilités p<sup>e</sup>|t et t |` − 1. En déduire que ` ≡ 1 (mod p^e) (critère de Pockling- ton).

b) Soit N un entier >2. On écrit N = 1 + uv et on suppose que pour tout nombre premier p qui divise u, il existe un entier a comme dans la question précédente. Mon- trer que tout facteur premier` de N est congru à 1 modulo u. Si de plus v6u + 1, en déduire que N est un nombre premier (critère de primalité de Pocklington-Lehmer).

Exercice 3.1.11. — Cet exercice propose la démonstration directe de quelques cas de la loi de réciprocité quadratique, à partir de la remarque que pour certaines valeurs de n, 2 cos(2π/n) vérifie une équation du second degré dont le discriminant est ±n.

a) Soit x une racine primitive huitième de l’unité. Montrer que x + 1/x est solution d’une équation du second degré à coefficients dans F_p dont le discriminant est 2. En déduire que 2 est un carré modulo p si p ≡ ±1 (mod 8). Inversement, si 2 est un carré modulo p, montrer que x et 1/x sont solutions d’une équation du second degré de discriminant −2. En déduire que p ≡ ±1 (mod 8).

b) Écrire l’équation du second degré dont les solutions sont les racines primitives cubiques de l’unité. En déduire que −3 est un carré modulo un nombre premier p > 4 si et seulement si p ≡ 1 (mod 3).

c) Soit p un nombre premier tel que p > 5. Soit x une racine primitive cinquième de l’unité dans une extension de Fp. Montrer que u = x + 1/x est solution d’une équation du second degré de discriminant 5. Si p²≡ 1 (mod 5), en déduire que 5 est un carré modulo p.

d) (suite) Supposons inversement que 5 soit un carré modulo p. Montrer que x et 1/x sont les solutions de l’équation t²−t u +1 = 0. Montrer que x^pest aussi une solution de cette équation et en déduire que l’on a x^p= x ou x^p= 1/x, puis que p ≡ ±1 (mod 5).

Exercice 3.1.12. — a) Soit n et m des nombres entiers. Montrer que le groupe (Z/nZ) × (Z/mZ) est cyclique si et seulement si n et m sont premiers entre eux.

b) Si n est une puissance de 2, montrer que (1 + 4x)ⁿ≡ 1 + 4nx modulo 8n.

c) Soit a un entier>2 et n = 2^a. Montrer que l’ordre de (la classe de) 5 dans (Z/nZ)^∗ est égal à 2^a−2. Le groupe (Z/nZ)^∗est-il cyclique ?

d) Soit p un nombre premier impair, a un entier >2 et n = p^a. Si x est un entier, montrer que x^p ≡ x (mod p). Montrer par récurrence sur a >2 que les conditions x ≡ 1 (mod p^a−1) et x^p≡ 1 (mod p^a) sont équivalentes.

e) Soit x un entier dont la classe modulo p engendre (Z/pZ)^∗. Montrer que (la classe de) x engendre (Z/nZ)^∗si et seulement si x^p−16≡ 1 (mod p²).

f ) Si x^p−1 ≡ 1 (mod p²), montrer que (x + p)^p−1 6≡ 1 (mod p²). En déduire qu’au moins l’un des deux, x ou x + p, est générateur de (Z/nZ)^∗.