1 Raisonnementautourdu pgcd - ENS...

Feuille d’exercice no1 L3 SIF

1 Raisonnement autour du pgcd

1. Associativité : Soient a, b, c ∈ N, montrez que :

pgcd [pgcd (a, b) , c] = pgcd [a,pgcd (b, c)]

Correction :Pour chaque entier a, on peut noter D (a) l’ensemble des diviseurs de a. i.eD (a) = {x ∈ N| x|a}.À partir de cette définition, on peut caractériser le pgcd de a et b comme l’unique entierd tel que D (d) = D (a) ∩ D (b).Par conséquent pour prouver l’associativité, il suffit de montrer que pour tout a, b, c ∈ N,on a :

[D (a) ∩ D (b)] ∩ D (c) = D (a) ∩ [D (b) ∩ D (c)]

Ce qui est vrai car l’intersection finie est associative.

2. Équation diophantiennes : Résoudre à l’aide de l’identité de Bézout dans Z2 l’équation :

10x+ 15y = −365

3. Généralisation : En déduire la méthode générale pour résoudre une équation du type :

ux+ vy = a

où pgcd (u, v) = 1.Correction de deux exercices : On veut résoudre dans Z2 le système suivant :

10x+ 15y = −363 (E)

⇔ 2x+ 3y = −73 (E)

Or, on peut voir que :2 · (−1) + 3 · 1 = 1

donc, si on pose (x, y) une solution quelconque de (E) et (x0, y0) = (−1, 1). On a lesystème suivant : {

2x+ 3y = −73−73 · (2x0 + 3y0) = −73

, d’où :

2 (x+ 73x0) + 3 (y + 73y0) = 0

Comme 2 et 3 sont premiers entre eux, 2 divise (y + 73y0) et 3 divise (x+ 73x0) il existedonc α ∈ Z tel que : {

x+ 73x0 = 3α

y + 73y0 = −2α

Feuille d’exercice no1 L3 SIFLes solutions du système (E) sont donc{

(x, y) ∈ Z2|∃α ∈ Z, x = 3α− 73, y = −2α− 73}

Méthode générale : quand on a une équation (E) de la forme ux + vy = a tel quepgcd (u, v) = 1.— Extraire une solution (x0, y0) ∈ Z2 tel que u · x0 + v · y0 = 1 1

— Si on prend (x, y) une solution quelconque de (E), on a :{u (ax0) + v (ay0) = a

ux+ vy = a

d’où l’équation suivante (sans second membre !) :

u · (x− ax0) + v (y − ay0) = 0

— Comme u et v sont premier entre eux, les solutions sont les solution de la forme :{x = ax0 + αv

y = ay0 + αu, α ∈ Z

4. Diviseur de 3 ? : Soient a, b ∈ Z, montrez que :

3|pgcd (a, b)⇔ 3|a2 + b2

Correction : On montre les deux sens :

⇒ : Si 3 divise pgcd(a, b) alors 3 divise a et b, donc divise a2 et b2 et donc 3 divise biena2 + b2.

⇐ : Si 3 divise a2 + b2, alors a2 + b2 ≡ 0 mod 3.Sauf que pour un nombre entier a quelconque, a ≡ 0, 1, 2 mod 3, traitons chaquecas :— Si a ≡ 0 mod 3, alors a2 ≡ 0 mod 3— Si a ≡ 1 mod 3, alors a2 ≡ 1 mod 3— Si a ≡ 2 mod 3, alors a2 ≡ 4 mod 3 ≡ 1 mod 3C’est valable pour un nombre a quelconque, donc, comme on doit avoir a2 + b2 ≡ 0mod 3, le seul cas possible parmi tous les cas est a ≡ 0 mod 3 et b ≡ 0 mod 3 (ex :b ≡ 1 mod 3 et a ≡ 2 mod 3⇒ a2 + b2 ≡ 2 mod 3).D’où 3 divise a et b.

5. pgcd de plus de deux nombres : Donner le pgcd de l’ensemble des coefficient binomiaux :

dn :=

{(n

k

)pour i ∈ {1, · · · , n− 1}

}dans le cas où :

(a) n est premier

(b) n est une puissance d’un nombre premier.Indication pour cette partie :

1. à la main ou avec l’algorithme d’Euclide étendu

Feuille d’exercice no1 L3 SIF— Tout d’abord, utiliser la formule du Binome pour montrer que dn divise (k + 1)n−

(1 + kn) pour tout k ≥ 1, en déduire que :

∀p ≥ 1, dn|pn − p

— Montrer que soit dn = 1, soit dn a des facteurs premiers d’ordre au plus 1. (Pourdn 6= 1, regarder dn comme le produit d’un nombre premier et d’un nombre quel-conque.)

Correction :

(a) Cas où n est premier :

Comme(n

k

)=

n!

k!(n− k)!, on sait que n! =

(n

k

)k!(n− k)!.

Si n est premier, il est premier avec tous les 1 ≤ k ≤ n. Par conséquent, pour tout1 ≤ k ≤ n, n est premier avec tous les 1, · · · , k et n− 1, · · ·n− k. Donc n est premieravec k! (n− k)!

Donc n! =(n

k

)k!(n − k)! mais n est premier avec k! (n− k)!, donc nécessairement

(Par Gauss), n divise(n

k

)Donc n|dnOr, dn divise tous les binômes

(n

k

), donc en particulier il divise

(n

1

).

Doncdn = n

(b) Cas où il existe u premier et k ∈ N∗ tel que n = uk :

i. Tout d’abord, observons que pour tout r ∈ R, par la formule du binôme de New-ton :

(r + 1)n =

n∑k=0

(n

k

)rk

dn divise tous les membres sauf le premeir et le dernier, excluons les

= 1 + rn +

n−1∑i=1

(n

k

)rk

Donc, dn| − (1 + rn) + (r + 1)n, il divise donc sa somme par rapport à r ∈{0, · · · , p− 1} :

∀p ≥ 1, dn|p−1∑r=0

(r + 1)n − 1− rn

Par télescopage, on obtient donc :

∀p ≥ 1, dn|pn − p

ii. On veut montrer que si dn 6= 1, alors dn a des facteurs premiers au plus d’ordre 1.Écrivons donc dn comme le produit d’un nombre premier a quelconque, et d’unnombre entier non nul b quelconque :

db = ab, où b ∈ N∗, a est premier.

Feuille d’exercice no1 L3 SIFMontrons que a et b sont premier entre eux. Or, par l’étape précédente, on saitque dn|an − a, donc il existe s ∈ N∗ tel que an − a = sab, donc an−1 − 1 = sb, cequ’on peut réécrire ainsi, car n ≥ 2 :

an−2 · a+ (−sb) = 1

Donc par le théorème de Bezout, pgcd (a, b) = 1

iii. Comme dn|n et que n = uk avec u premier, donc a = u et b = 1 ou b est unepuissance de u. Comme b et a sont premiers entre eux, b = 1.Donc

dn ∈ {1, u}

iv. Autre correction proposée par un élève : Une fois qu’on a montré que dn|pn −p,∀u ≥ 1.On a n = uk donc comme dn|n on a dn = ui avec i ≤ k.supposons que dn 6= 1 (i.e que i 6= 0).On sait par la question précédente que un−u ≡ 0 mod dn et, comme dn = ui, onsait que un = un−iui ≡ 0 mod dn car i ≤ j ≤ n = uj avec u ≥ 1. Par conséquent :

un − u ≡ −u mod dn et un − u ≡ 0 mod dn

donc u ≡ 0 mod dn donc dn = ui|u avec i ≥ 1, donc i = 1 et :

dn = u ou 1

2 Critères de cyclicité

1. Produit de deux groupes cycliques : Soient H et K deux groupes cycliques.Montrez que H ×K est cyclique si et seulement si pgcd [ord (K) , ord (H)] = 1Correction : Notons n = ord (K) et m = ord (H).⇒ : Supposons que H ×K est cyclique. Posons (h, k) le générateur de H ×K. Comme

ce groupe est cyclique, ord (h, k) = ord (H ×K) = ord (H)× ord (K)Comme h et k sont les générateurs respectivement des groupes cycliques H et K,ord (h) = n et ord (k) = mMontrons que pgcd [n,m] = 1.On sait que si on prend un couple x, y, alors ord (x, y) = ppcm (ord (x) , ord (y)) Doncici, ord (h, k) = m× n = ppcm (m,n). Or pour deux entiers quelconques z, t ∈ Z :

ppcm (z, t) =|z| · |t|

pgcd (z, t)

d’où en appliquant à m = z et n = t, pgcd (m,n) = 1

⇐ Supposons que pgcd (n,m) = 1, montrons que H ×K est cyclique, i.e que si (h, k)est un générateur de H ×K, alors ord (h, k) = mn.Soit h et k deux générateurs respectif des groupes H et K. Donc m = ord (h) etn = ord (k).Or, ord ((h, k)) = ppcm (m,n) = m×n car ces deux nombres sont premiers entre eux.Donc ord ((h, k)) = ord (H ×K) et (h, k) ∈ H ×K, donc H ×K est cyclique.

Feuille d’exercice no1 L3 SIF2. Cyclicité d’un groupe d’ordre fini : Soit (G, ·) un groupe fini d’ordre m. Soit e l’élément

neutre de G pour la multiplication.Supposons que pour tout entier d divisantm, le cardinal de l’ensembleAd =

{x ∈ G|xd = e

}est au plus d.Montrer que le groupe G est alors cyclique.

Indication :— On veut en fait montrer que #Ad = ϕ (d) ou 0. On peut tout d’abord choisir un

générateur quelconque x de g et regarder H = 〈x〉 et compter le nombre d’élémentd’ordre d.

— Voir G comme⊔d|m

{x ∈ G|xd = e

}et utiliser que m =

∑d|m

ϕ (d) pour montrer par

l’absurde que aucun Ad n’est vide.Correction : On veut montrer que #Ad = ϕ (d) ou 0.Supposons qu’il existe un élément d’ordre d dans G, notons le x. Ainsi, Ad n’est pas vide.Posons H = 〈x〉. H est un sous-groupe de G et est d’ordre d, et il est cyclique.Comme Ad est de cardinal au plus d, Ad ⊆ H. On notera que H a ϕ (d) éléments d’ordred.Écrivons maintenant G comme

⊔d|m

{x ∈ G|xd = e

}, car tout élément de G a un ordre qui

divise m.On veut montrer que l’assertion suivante est fausse : P = ”∃d|m, tel que Ad = ∅”.Supposons (par l’abusrde) que P est vrai, alors #G <

∑d|m

ϕ (d), or m =∑d|m

ϕ (d), donc

#G < m, ce qui est absurde.Donc il n’existe aucun d|m tel que Ad soit vide.

3. En déduire que si p est premier, alors (Z/pZ)∗ est cyclique.Correction : Si p est premier, alors Z/pZ est un corps commutatif. Pour tout d ≥ 1,Xd − 1 ∈ (Z/pZ) [X] a au plus d racines dans (Z/pZ)∗, donc par l’exercice précédent, cegroupe est cyclique.

3 Théorème chinois, d’Euler et le théorème de Fermat

1. Fonction indicatrice : Calculer la fonction indicatrice ϕ (n) pour n = 425250000Correction : On a la décomposition en facteur premier de n suivante :

n = 24 × 35 × 56 × 7

Donc en utilisant les trois formules suivantes :

ϕ (mn) = ϕ (m)ϕ (n)pgcd (m,n)

ϕ (pgcd (m,n)), ∀k ≥ 1, ϕ

(nk)= nk−1ϕ (n)

Feuille d’exercice no1 L3 SIFϕ (n) = ϕ

(24)· ϕ(35)· ϕ(56)· ϕ (7)

= 23 · ϕ (2) · 34ϕ (3) · 55 · ϕ (5) · ϕ (7)

= 23 · 1 · 34 · 2 · 55 · 4 · 6= 24 · 34 · 4 · 55 · 6

2. Des modulos : Donner les deux derniers chiffres de l’écriture décimale de :

(a) 31000

(b) 21000

Correction :

(a) On cherche à calculer l’écriture décimale de 31000 pour ces deux derniers chiffres,c’est-à-dire de savoir combien vaut 31000 mod 100, donc on veut 0 < a < 99 tel que31000 ≡ a mod 100On peut dès à présent observer que 1000 = 40 · 25, or si pgcd (a, n) = 1, aϕ(n) ≡ 1mod n (Euler) et un calcul de la fonction indicatrice (Cf exo précédent) ϕ (100) = 40.Donc, par cette égalité, on a en l’appliquant à n = 100 :

340 ≡ 1 mod 100

donc 340·25 ≡ 01 mod 100, les deux derniers chiffres de 31000 en écriture décimalessont donc 01.

(b) On cherche également ici 0 < a < 99 tel que 21000 ≡ a mod 100 mais on ne peut pasutiliser la même méthode pour calculer ce modulo, car 2 et 100 ne sont pas premiersentre eux, donc on ne peut pas utiliser le critère d’Euler.On observe que 100 = 25 · 4, et par Euler, comme 2 et 25 sont premiers entre eux :

220 ≡ 1 mod 25 ≡ −24 mod 25

Par le théorème chinois, on peut donc prouver que 21000 ≡ −24 mod 100 ≡ 76mod 100, les deux derniers chiffres de 21000 en écriture décimales sont donc 76.En effet, si on regarde le théorème chinois, si on écrit n =

∏ni où chaque ni sont

premiers entre eux. Il permet une bijection entre (a mod n) et (ai mod ni) où a ≡ aimod n. Donc si on a b et c premiers entre eux, et qu’on trouve a ≡ d mod b et a ≡ dmod c alors a ≡ d mod bcQue faire si on a deux modulo différents ? (i.e si on a a ≡ a1 mod b et a ≡ a2mod c ?)Si on traduit la situation d’origine, on sait donc que il existe k1, k2 ∈ Z tel que :

a = a1 + k1 · b = a2 + k2 · c (E)

Or, on sait que b et c sont premiers entre eux, donc par Bézout, il existe u et v telsque :

bu+ cv = 1

Donc si on multiplie le premier terme de (E) par vc et le deuxième par ub, on obtient :

vac = va1c+ k1 · vbc , uab = ua2b+ k2 · ubc

Feuille d’exercice no1 L3 SIFOn peut donc simplifier :

vac+ abc = va1c+ k1 · vbc+ ua2b+ k2 · ubca (vc+ ub)︸ ︷︷ ︸

=1

= va1c+ ua2b+ bc (k1v + k2u)

a = va1c+ ua2b+ bc (k1v + k2u)

a ≡ va1c+ ua2b mod bc

Cela revient donc à trouver les coefficients de Bézout (u, v) par l’algorithme d’Euclideétendu.

3. Théorème de Schinzel : Soit k ∈ Z\ {1}, montrez qu’il existe une infinité d’entiers n telsque 22

n+ k ne soit pas premier. Indications/Remarques :

(a) On ne sait pas le démontrer pour k = 1...(b) On peut exprimer k à l’aide de choses, dont des puissance de 2 et d’autres choses.(c) On va chercher à majorer un entier a quelconque par quelque chose de la forme 22

n+k.

Correction :(a) Cas k pair : il existe a ∈ N∗ tel que k = 2 · a donc 22

n+ 2 · a est pair, donc non

premier, et ce quelque soit n ∈ N. Donc on a bien une infinité de tels nombres.(b) On se restreint donc au cas où k est impair. Il suffit en fait de montrer que

∀a ∈ N, ∃n ∈ N, 22n+ k > a et ∃p ∈ N\ {0, 1} , p|22n + k

On montre en fait que quelque soit le nombre que l’on prend a, aussi grand soit-il, onpeut encore trouver un nombre de la forme souhaité, divisible par un nombre entierp 6= 1.

(c) Traduisons l’énonce pas à pas :[k est impair] : donc il existe s ∈ N, ∃h ∈ N\ {1, 2} impair tel que :

k − 1 = 2sh

Écrivons le comme : 1 = 2sh+ k.(d) Posons t ∈ N tel que p := 22

t+ k > a tel que t > s. On peut supposer que p est

premier (en effet si ce n’était pas le cas, la démonstration s’arrête car on a trouvé unnombre non premier de la bonne forme.).Par conséquent, il existe h ∈ N\ {1, 2}, impair, tel que p = 2sh1 + 1

Par Euler :2ϕ(h1) ≡ 1 mod h1

Donc 2s+ϕ(h1) ≡ 2s mod 2sh1 ≡ 2s mod (p− 1)Comme t > s, on a donc 2t+ϕ(h1) ≡ 2t mod (p− 1)Comme p est premier, impair, alors 2 ne divise pas p donc par Fermat :

2p−1 ≡ 1 mod p

L’entier que l’on cherche est donc 22t+ϕ(h1)

+ k > p et on va montrer que p le divise.Notons cet entier q, on sait que 2t+ϕ(h1) ≡ 2t mod (p− 1), donc il existe k′ ∈ N∗ telque :

22t+ϕ(h1)

+ k = 22t+(p−1)·k′ + k

= 22t · 2(p−1)k′ + k or 2(p−1)k

′ ≡ 1 mod p

≡ 22t+ k mod p

22t+ϕ(h1)

+ k ≡ 0 mod p

Feuille d’exercice no1 L3 SIF

4 Exercices de fin

1. Soit G un groupe où chaque élément est son propre inverse (∀a ∈ G, a2 = eG).

(a) Montrer que G est abélien.Soit a, b ∈ G, alors (ab) = (ab)−1 = b−1a−1 = ba donc

ba = ab

(b) Montrer que on peut munir G d’une structure de Z/2Z−espace vectoriel.On peut voir que G est un groupe commutatif si on le muni de la loi externe [0] a = [0],[1] a = a

(c) Montrer que si en plus G est d’ordre fini, alors ord (G) est une puissance de 2.G est un espace vectoriel de dimension finie sur Z/2Z, on a donc un isomorphisme deZ/2Z-espace vectoriel entre G et (Z/2Z)n.

(d) En déduire que si un groupe H est d’ordre 4, alors H est isomorphe à Z/4Z ou àZ/2Z× Z/2ZSi H est d’ordre 4, alors pour tout a dans H, ord (a) ∈ {2, 4}— Si il y a un élément d’ordre 4, alors H est isomorphe à Z/4Z— Sinon, il n’y a que des éléments d’ordre 2, alors a2 = e et par les question précé-

dentes, on est isomorphe à (Z/2Z)2

Feuille d’exercice no2: Résidus quadratiques et symbole de Legendre L3 SIF

Calcul de symbole de Legendre

Utilisez trois méthodes différentes pour calculer les symboles de Legendre suivants :

Méthode 1 : par le critère Euler :(75

3

)Correction : Le critère d’Euler donne que pour un nombre premier impair quelconquep et pour tout entier relatif n : (

n

p

)≡ n

p−12 mod p

Donc ici comme 73 ∈ Z et que 3 est un entier premier impair, on a :(73

3

)= 73

3−12 mod 3 = 73 mod 3 = 1 mod 3 = 1

Méthode 2 : par la loi de réciprocité quadratique :(101

641

)Correction : La loi de réciprocité quadratique permet d’inverser un symbole deLegendre par la formule suivante : Si p et q sont deux entiers impairs distincts, alors :(

p

q

)= (−1)

(p−1)(q−1)4

(q

p

)De plus, si on a m,n ∈ Z et p ∈ Z :(

mn

p

)=

(m

p

)(n

p

)Lorsqu’on a un symbole de Legendre

(q

p

)avec p plus grand que q, en fait, comme(

q

p

)=

(q mod p

p

), on veut l’inverse, pour réduire le nombre au dessus modulo le

nombre en dénominateur. Ensuite, on ré-inverse et on refait une division euclidien pourréduire, jusqu’à arriver à un symbole de Legendre que l’on peut calculer. (Voir exempleci-dessous)Ici, cela donne :(

101

641

)= (−1)

(100)(640)4

(641

101

)=

(641

101

)=

(35

101

)car 641 = 6 · 101 + 35

=

(5

101

)·(

7

101

)=

(101

5

)(101

7

)en appliquant la LQR deux fois

=

(1

5

)(3

7

)=

(3

7

)= −

(7

3

)par la loi de réciprocité quadratique

= −1

Feuille d’exercice no2: Résidus quadratiques et symbole de Legendre L3 SIF

Exercice 1

1. On a vu en cours que : ∀n ∈ N,(n

2

)≡ n mod 2

Montrez ici que

∀n ∈ N,(n

3

)≡ n mod 3

Correction : Il faut en fait faire les cas de congruence (on en a que 3 en soi.)

• Si n ≡ 0 mod n, alors (n

3

)≡ 0 mod 3

• Si n ≡ 1 mod 3 alors :(n

3

)=

(1

3

)= 1 or 1 est un carré modulo 3 donc :

(n

3

)≡ 1 mod 3

• Si n ≡ 2 mod 3 ≡ −1 mod 3 alors :(n

3

)=

(2

3

)=

(−13

)≡ −1 mod 3 car 2 ≡ −1

mod 3 donc : (n

3

)≡ 2 mod 3

2. Soit p un nombre premier impair, et posons n le plus petit entier n’étant pas un résiduquadratique modulo p.Montrez que n < 1 +

√p

Indications : On veut en fait montrer que (n− 1)2 < p. On pourra poser m ∈ N le pluspetit entier tel que m · n > p et travailler sur les conditions ’le plus petit..tel que... ’Correction : On veut en fait montrer que (n− 1)2 < p, car on aura alors n − 1 <

√p

car n− 1 > 0 et p > 0.Posons pour cela m le plus petit entier tel que m · n > p donc n (m− 1) ≤ p.Or comme p est premier on ne peut pas avoir le cas d’égalité, donc :

n (m− 1) < p

Donc, on a 0 < mn−n < p. Montrons quem ≥ n, comme n est le plus petit entier n’étantpas un résidu quadratique modulo p, si on montre quem est un résidu quadratique modulop, alors m ≥ n. Regardons le résidu quadratique de m.De qui connaissons-nous les résidus quadratiques ? n n’en est pas, et mn − p est unentier, inférieur strict à n, donc comme n est le plus petit entier n’étant pas un résidu

Feuille d’exercice no2: Résidus quadratiques et symbole de Legendre L3 SIFquadratique modulo p, alors mn− p est un résidu quadratique modulo p

1 =

(mn− p

p

)=

(mn

p

)=

(m

p

)(n

p

)= −

(m

p

)

Donc, en conclusion,(m

p

)= −1, donc m ≤ n et on sait que n(m− 1) < p, or :

(n− 1)2 ≤ n (n− 1)

≤ m (n− 1)

Donc :(n− 1)2 < p

Exercice 2 : Somme de Gauss

On rappellera la construction des sommes de Gauss :Soit q un entier premier, impair, et A un anneau commutatif, d’élément neutre 1A.

Soit α ∈ A tel que :q−1∑i=0

αi = 0 dans A et αi et(i

n

)ne dépendent que de i mod q.

On posera la somme de Gauss τ comme étant :

τ :=

q−1∑i=0

(i

q

)αi

On a montré en cours que :τ2 = (−1)

q−12 · q

Maintenant on veut montrer que :1. Soit p un nombre premier impair, tel que p 6= q, supposons que p · α = 0 dans A.

Montrez que :

τp =

(p

q

)τ

Correction :

τp =

(q−1∑i=0

(i

q

)αi

)p

=

q−1∑i=0

(iq

)p (αi)p car αi · p = 0 ∀i ∈ Z/qZ\ {0}

Feuille d’exercice no2: Résidus quadratiques et symbole de Legendre L3 SIF

En effet, si on développe avec le binôme de Newton (a+ b)p où b = αp

(q

q

)et a = τ−b,

alors il ne reste que le premier et le dernier terme à la fin, car αi · p = 0.

τp =

q−1∑i=0

(i

q

)αip

(p

q

)τp =

q−1∑i=0

(ip

q

)αip

Comme p et q sont premiers entre eux, i 7→ p · i est une bijection de Z/pZ et que

α est une racine q-ème de l’unité et que(p

q

)2

= 1 on a :

τp =

(p

q

)τ

2. Montrez que :

τ =

q−1∑i=0

αi2

Correction : On sait que τ =

q−1∑i=0

(i

q

)αi, et on cherche donc un moyen d’éliminer le

symbole de Legendre, or il ne prends que 3 valeurs donc coupons la somme ne 3 (en faiten 2 car il prend les valeur 1,−1 ou 0.) :

si on prend I =

{i = 1, · · · , q − 1 |

(i

q

)= 1

}et S =

∑i∈I

αi

Donc τ = S −∑

i=1,··· ,q−1|i 6∈I

αi

Or, 1 + α+ · · ·+ αq−1 = 0 donc :

τ = 2 ·q−1∑i=0

αi + 1 = 2

q−12∑

i=1

αi + 1 =

q−1∑i=1

αi2 + 1 =

q−1∑i=0

αi2

Exercice 3

1. Montrez qu’il existe une infinité de nombres premiers congru à 7 modulo 8.Indications :— Raisonner par l’absurde en posant un ensemble P = {p1, · · · , pn} l’ensemble des tels

nombres décrits.— Poser N = (4p1 · · · pn)2 − 2 et montrer qu’il existe un diviseur de N , congru à 7

modulo 8.Correction : Supposons le contraire, posons P = {p1, · · · , pn} l’ensemble (fini) desnombres premiers congru à 7 modulo 8.Posons ensuite N = (4p1 · · · , pn)2 − 2 et notons p un diviseur premier impair de N (quiest le produit de 2 et d’un nombre impair, donc p existe). On va montrer qu’il existe un

Feuille d’exercice no2: Résidus quadratiques et symbole de Legendre L3 SIFdiviseur de N , premier, impair, congru à 7 modulo 8.tout d’abord, comme 2 = N − (4p1 · · · pn)2, on sait que 2 ≡ (4p1, · · · , pn)2 mod p doncc’est un carré modulo p.Par conséquent, p ≡ ±1 mod 8.

Comme N = 16 (p1, · · · , pn)2 − 2 on sait queN

2= 8 (p1, · · · , pn)2 − 1 donc comme N

admet un diviseur p premier, impair, congru à ±1 modulo 8, donc p ≡ 7 mod q.Par l’hypothèse de départ, p est l’un des pi, ce uqi est absurde. car p ne divise pas 2.

2. Soit n ∈ N, posons Fn = 22n+ 1 (Nombre de Fermat).

Montrez que pour tout n ≥ 2 entier, les facteurs premiers de Fn sont congru à 1 modulo2n+2.Indications :— Étudier l’ordre de 2 dans le groupe multiplicatif (Z/pZ)∗ pour montrer que p ≡ ±1

mod 8

— Utiliser le théorème d’Euler pour montrer quep− 1

2≡ 0 mod 2n+1

Correction :Soit p un facteur premier de Fn.Regardons l’ordre de 2 dans le groupe multiplicatif (Z/pZ)∗, 22

n ≡ −1 mod p et par dé-finition des nombres de Fermat, 22

n+1 ≡ (−1)2 mod p ≡ 1 mod p donc ord(Z/pZ)∗ (2) =2n+1

Par le théorème de Lagrange, on sait donc que 2n+1|p− 1.comme n ≥ 2, alors 23|p − 1 donc p ≡ 1 mod 8, donc 2 est un carré modulo p, donc(2

p

)= 1

Par le critère d’Euler,(2

p

)2

p−12 mod p donc 2

p−12 mod p ≡ 1 mod p

D’où 2n+1|p− 1

2car c’est l’ordre de 2.

D’oùp− 1

2≡ 0 mod 2n+1 donc p− 1 ≡ 0 mod 2n+2

3. Soit p un nombre premier. supposons que p soit de la forme p = 4q+1, où q est premier.Montrez que 2 est un générateur de (Z/pZ)∗.Indications : Réfléchir aux valeurs possibles de l’ordre de 2 et ensuite, tester les possibilités(faire des disjonctions de cas)Correction : On note d = ord(ZpZ)∗ (2).On sait que l’ordre de 2 divise ϕ (p) = p− 1 = 4q donc d ∈ {1, 2, 4, q, 2q, 4q}∗ Si d = 1 alors 21 ≡ 1 mod p, on devrait avoir p = 3, ce qui n’est pas possible car

p = 4q + 1 > 5

∗ Si d = 2 alors 22 ≡ 1 mod p, or 4 ≡ 1 mod p si p = 5, ce qui est absurde.

∗ Si d = 4 alors 8 ≡ 1 mod p, ce qui obligerait à q = 2, ce qui est absurde.

∗ Si d ∈ {q, 2q} alors on peut montrer que dans tous les cas 2p−12 ≡ 1 mod p.

En effet, si d = q ,alors 2q ≡ 1 mod p, donc 22q ≡ 1 mod p donc 2p−12 ≡ 1 modp

donc dans tous les cas, 2 est un carré modulo p et donc p ≡ ±1 mod 8, or p = 4q+1donc :— Si q > 2, c’est absurde car q est alors impair, donc s’écrit sous la forme 2k + 1,

donc p = 8k + 3 6≡ 1 mod 8

Feuille d’exercice no2: Résidus quadratiques et symbole de Legendre L3 SIF— Si q = 2, p = 9 ≡ 1 mod 8 mais 2 est quand même un générateur car :

2 ≡ 3 mod 5

22 ≡ −1 mod 5

23 ≡ 8 mod 5 ≡ 3 mod 5

24 ≡ 16 mod 5 ≡ 1 mod 5

Donc 2 est bien générateur.Il ne reste donc plus, dans tous les cas, que la possibilité d = 4q donc 2 est bien

générateur.4. On rappelle que ∀n ≥ 1, le nombre de Fermat s’écrit : Fn = 22

n+ 1.

On va montrer que Fn est premier si et seulement si 3Fn−1

2 ≡ −1 mod Fn par les étapessuivantes :(a) Soit k ∈ N, montrer que si 2k +1 est premier, alors k s’écrit comme une puissance de

2.

(b) Montrer que g ∈ N est un générateur de (Z/FnZ)∗ si et seulement si(g

Fn

)= −1

(c) Montrer que si Fn est premier alors 3 est un générateur de (Z/FnZ)∗, en déduire lepremier sens de la proposition.

(d) Montrer enfin que si 3Fn−1

2 ≡ −1 mod Fn alors Fn est premier.Correction :(a) Posons k = a · 2b où a ∈ N est impair et b ∈ N.

On écrit alors :

2k + 1 = 2a·2b+ 1

=(22

b)a

+ 1

Peut-on trouver des diviseurs ? Regardons pour cela le polynôme P = Xa+1. Commea est impair, −1 est une racine évidente donc X + 1 divise P .

Xa + 1 = (X + 1)(Xa−1 −X−a−2 + · · ·+ 1

)= (X + 1)

a−1∑i=0

(−1)iXi

Ainsi, on sait que :

2k + 1 =(22

b+ 1)(a−1∑

i=0

(−1)i(22

b)i)

Donc 22b+ 1 divise 2k + 1, deux cas sont alors possibles : soit 22

b+ 1 = 1, ce qui est

impossible, soit 22b+ 1 = 2k + 1 donc k = 2b est une puissance de 2

(b) ⇐ On va chercher à montrer que ord (g) = Fn − 1, ainsi on aura montre qu’il est ungénérateur.

Par hypothèse, on sait que(g

Fn

)≡ −1 mod Fn, par le critère d’Euler, on sait

que g ≡ −1 mod Fn donc gFn−1 ≡ 1 mod Fn, donc :

g22n ≡ 1 mod Fn et g2

2n−1 6≡ 1 mod Fn

donc ord (g) |Fn − 1 = 22n, or ord (g) - 22

n−1 donc ord (g) = Fn − 1

Feuille d’exercice no2: Résidus quadratiques et symbole de Legendre L3 SIF

⇒ Si g est un générateur de (Z/FnZ)∗, alors g n’est pas un carré dans(g

Fn

)= −1

(c) Comme 3 est un nombre premier impair, on peut appliquer le critère d’Euler pour

calculer le symbole de Legendre(Fn

3

):

(Fn

3

)≡ F

3−12

n mod 3

≡ Fn mod 3

≡ 22n+ 1 mod 3

Faisons une disjonction de cas :

i. Si 3 divise 22n+1 c’est absurde car ce nombre est premier et différent de 3 (n ≥ 1).

ii. Si 22n+ 1 ≡ 1 mod 3, alors 3 divise 22

nce qui est absurde.

Nécessairement, Fn ≡ 2 mod 3, donc(Fn

3

)≡ 2 mod 3 = −1

Par la loi de réciprocité quadratique, on a(

3

Fn

)≡ −1, donc 3 est générateur de

(Z/FnZ)∗ par la question précédente.Le premier sens de la proposition s’en déduit donc : 3 est générateur donc 3Fn−1 ≡ 1

mod Fn mais [par le Critère d’Euler] 3Fn−1

2 =

(3

Fn

)= −1

(d) Montrer enfin que si 3Fn−1

2 ≡ −1 mod Fn, alors Fn est premier.supposons que Fn ne soit pas premier, et notons p ∈ N un de ses diviseurs premiers,donc p|Fn et p < Fn.Comme 3

Fn−12 ≡ −1 mod Fn alors 3

Fn−12 ≡ −1 mod p et 3Fn−1 ≡ 1 mod p. Par

conséquent, ord(Z/pZ)∗ (3) |Fn − 1 = 22net 3

Fn−12 6≡ 1 mod Fn donc ord(Z/pZ)∗ (3) -

22n−1 donc ord(Z/pZ)∗ (3) = Fn − 1.

Or, par le théorème de Lagrange, ord(Z/pZ)∗ (3) | ord ((Z/pZ)∗) = ϕ (p) = p− 1 car

p est premier, donc :Fn − 1|p− 1

ce qui est absurde car Fn − 1 > p− 1, donc Fn est bien premier.

Feuille d’exercices no3 - Corrigé L3 SIF

1 Petits rappels sur les corps finis

On rappellera ici quelques notions sur les corps finis :

• Corps finis :Un corps fini k est un corps commutatif qui est fini (i.e. #k < +∞).On notera Fp le corps fini à p élément, il est unique à isomorphisme près.Un corps fini k a toujours pour cardinal q la puissance d’un nombre premier p. Cenombre premier s’appelle la caractéristique du corps fini k.

• Cas des corps finis Fp où p est premier :Si p est un nombre premier, alors on peut montrer que Fp = Z/pZ.

• Autres cas :Pour les cas où le cardinal q du corps fini n’est pas premier, q = pn où p est un nombrepremier et n ≥ 1. On peut alors représenter ce corps fini comme un quotient de Fp [X]avec un polynôme irréductible. En effet :

L’anneau Fp [X] / (P ) est un corps ssi P est un polynôme irréductible.

Si P est irréductible, le corps Fp [X] / (P ) est de cardinal pdegP .Pour finir, Fpn possède un sous-corps de cardinal pd ssi d|n. Ce corps est unique, àisomorphisme près, et est formé de l’ensemble des racines de Xpd − 1.

• Comment caractériser un corps ? quelle propriété peut-on en tirer ? On rappelleque :— Soit k un anneau, k est un corps ssi l’ensemble des inversible k× est exactement

l’ensemble des éléments non nuls k∗ de k, i.e k est un corps ssi k× = k∗.— Si (k,+, ·) est un corps commutatif, alors

(k×, ·

)est un groupe commutatif multi-

plicatif. Ce sera important pour manipuler l’ordre des éléments ! en effet la notiond’ordre est propre aux groupes. quand on prend un élément a dans un corps k etque l’on parle de son ordre, on parle de l’ordre de a dans le groupe multiplicatif k×.

• Factorisation des polynômes et polynômes irréductibles sur les corps finis :

Soit k un corps commutatif. On rappelle que k [X] =

{n∑

i=0

aiXi|ai ∈ k, ∀0 ≤ i ≤ n, n ∈ N

}représente l’ensemble des polynômes à coefficients dans k.Soit k un corps. Un polynôme P ∈ k [X] est réductible ssi il est le produit de deux poly-nômes irréductibles Q et R ∈ k [X] avec deg (R) ≥ 1 et deg (R) ≥ 1.On rappelle qu’un polynôme peut être réductible dans k [x] et n’avoir aucune racine dansle corps k. Exemple :

(X2 + 1

)2 est réductible dans R [X], pourtant ses racines sont dansC\R.En fait, un polynôme de degré 2 ou 3 sur un corps est irréductible ssi il n’admet aucuneracine.Prenons l’exemple sur un corps finis k et avec n = 4 > 3 pour montrer qu’un po-lynôme est donc irréductible sur k[X]. Soit un polynôme P ∈ k[X] de degré 4,

Feuille d’exercices no3 - Corrigé L3 SIFsupposons que P n’a aucune racine dans k. S’il était réductible dans k [X], alors il fau-drait qu’il soit le produit de deux polynômes irréductibles de degré 2.En effet s’il était le produit d’un polynôme irréductible de degré 1 et d’un polynôme dedegré 3, tous deux dans k[X], alors il aurait des racines dans k.Pour un corps k particulier, par exemple k = F3,On peut alors lister la liste des polynômesirréductibles de degré 2. Les polynômes irréductibles de degré 2 dans F3 sont :

X2 + 1, X2 −X − 1, X2 +X − 1

Ainsi, on peut vérifier que notre polynôme n’est pas le produit de deux polynômes irré-ductibles de degré 2.

2 Exercices de base

1. Soit p un nombre premier, montrer que pour tout k ∈ {1, · · · , p− 1}, p divise(p

k

).

Correction :On peut écrire k

(p

k

)= p

(p− 1

k − 1

), comme k ≤ p−1 et p est premier, k et p sont premiers

entre eux, par le lemme de Gauss, p divise donc(p

k

).

2. Montrer que Z/pZ est un corps ssi p est un nombre premier.Si p est premier, montrer que

∣∣Z/pZ×∣∣ = ϕ (p) = p− 1Correction :On peut caractériser les éléments inversibles (pour ×) de l’anneau (Z/pZ,+,×) :

(Z/pZ)× = {m ∈ Z/pZ| m est inversible dans Z/pZ pour ×}= {m ∈ Z/pZ| ∃u ∈ Z/pZ, um = 1}= {m mod p| m ∈ Z tel que ∃u ∈ Zv ∈ Z, um+ vp = 1} Or, par Bézout := {m ∈ Z/pZ| m ∧ p = 1}

Comme p est premier, les éléments de {0, · · · , p− 1} premiers avec p sont exactement{1, · · · , p− 1}. Ainsi (Z/pZ)× = (Z/pZ)∗.On obtient également que |Z/pZ|× = ϕ (p) = p− 1 car p est premier.

3. Soit p un nombre premier, soient a, b ∈ Fp, montrer que (a+ b)p = ap + bp.Correction :On développe (a+ b)p avec la formule du binôme de Newton :

(a+ b)p =

p∑k=0

(p

k

)akbp−k

(a+ b)p = ap + bp +

p−1∑k=1

(p

k

)akbp−k

or p |(p

k

)pour 1 ≤ k ≤ p− 1, comme p est premier on a Fp = Z/pZ d’où :

(a+ b)p = ap + bp.

Feuille d’exercices no3 - Corrigé L3 SIF4. Soient a ∈ N\ {0, 1}, et d, n ∈ N, montrer que ad − 1|an − 1 ssi d|n

Correction :

⇐ : Si d|n, alors il existe q ∈ Z tel que n = dq. On peut écrire :

an − 1 =(ad)q− 1

=(ad − 1

)((ad)q−1

+ · · ·+ 1

)Ainsi, ad − 1 divise bien an − 1.

⇒ : On effectue la division euclidienne de n par d :

∃q, r ∈ Z, n = qd+ r, 0 ≤ r ≤ d− 1.

Comme ad − 1 divise an − 1, on a :

an − 1 ≡ 0 mod ad − 1

abd+r − 1 ≡ 0 mod ad − 1, donc par l’implication précédente :

ar − 1 ≡ 0 mod ad − 1

comme r < d, la seule solution est que r = 0.

3 Exercice calculatoires

1. Soit F4 = F2 [X] /(X2 +X + 1

)Montrer que ∀a ∈ F×4 , a

3 = 1.Correction :Soit a ∈ F×4 , montrer que a3 = 1.Comme a2 + a+ 1 = 0, en multipliant cette équation par le polynôme a :

a3 = −a2 − a = −1 = 1 ∈ F2

2. Soit k un corps de cardinal q. Montrer que ∀x ∈ k, xq = xCorrection :Soit x ∈ k quelconque.Pour x = 0, le résultat est immédiat.Pour x 6= 0, x ∈ k× qui est un groupe multiplicatif d’ordre #k − 1, or k est un corpsdonc k× = k∗.Donc k× est un groupe multiplicatif d’ordre q − 1. Par le théorème de Lagrange, on saitdonc que l’ordre de x divise q − 1, donc xq−1 = 1, d’où :

xq = x.

Feuille d’exercices no3 - Corrigé L3 SIF3. Factoriser le polynôme P = 3X3 + 4X2 + 2X − 4 dans F5 [X] et dans F7 [X]. Est-ce la

même décomposition ? Ce polynôme a-t-il toutes ces racines dans F7?Correction :— Pour F5 : On cherche une racine évident de P modulo 5. 1 est une racine évidente car

3 · 13 + 4 · 12 + 2 · 1− 4 = 3 + 2 = 5 ≡ 0 mod 5En faisant la division euclidienne de P par X − 1 dans F5 [X] on trouve :

P = (X − 1)(3X2 + 7X − 1

)= (X − 1)

(3X2 + 2X − 1

)On trouve ensuite −1 en racine évidente car 3 · (−1)2 + 2 · (−1)− 1 = 3− 2− 1 ≡ 0mod 5, en faisant la division euclidienne de 3X2 +2X−1 par (X + 1) on trouve dansF5 [X] :

P = (X − 1) (X + 1) (3X − 1) = (X + 4) (X + 1) (3X + 9) = 3 (X + 1) (X + 3) (X + 4) .

— Pour F7, on trouve la première racine évidente −4 car P (−4) = −140 ≡ 0 mod 7.En faisant la division euclidienne de P par X − 1 dans F7 [X] on trouve :

P = (X + 4) 3(X2 + 2X + 2

).

On peut montrer que X2 + 2X + 2 est irréductible dans F7[X] (cf exo suivant).4. Montrer que X2 + 2X + 2 est irréductible dans F7[X].

Correction :Comme c’est un polynôme de degré 2, il suffit de vérifier que pour p ∈ {0, 1, 2, 3, 4, 5, 6},p2 + 2p+ 2 6≡ 0 mod 7. Cela montre qu’il n’a pas de racines dans F7.

4 Exercice un peu plus difficile

On rappelle le critère d’Euler : si k est un corps fini de cardinal q = pd où p est un nombrepremier :

a ∈ k× est un carré ssi aq−12 = 1 dans k×

1. Montrer que, pour un nombre premier p :

P = X2 + 1 ∈ Fp [X] est irréducible ssi p ≡ 3 mod 4

Correction :Vérifions le cas p = 2 pour pouvoir supposer ensuite que p est un nombre premier impair :X2 + 1 est réductible dans F2 [X] car X2 + 1 = (X + 1)2 dans F2 [X].Considérons maintenant le cas où p est un nombre premier impair. Comme P est un

Feuille d’exercices no3 - Corrigé L3 SIFpolynôme de degré 2, il est irréductible dans Fp [X] ssi il n’a pas de racines dans Fp [X] :

P est réductible dans Fp [X] ssi ∃a ∈ Fp, P (a) = 0

ssi ∃a ∈ Fp, a2 = −1

ssi − 1 est un carré dans Fp or par le critère d’Euler :

ssi (−1)p−12 ≡ 1 mod p

ssip− 1

2≡ 0 mod 2

ssi p− 1 ≡ 0 mod 4

ssi p ≡ 1 mod 4

Comme p 6≡ 0, 2 mod 4 (car p 6= 2), on a P = X2 + 1 ∈ Fp [X] est irréducible ssi p ≡ 3mod 4

5 Une application de la loi de réciprocité quadratique

On rappelle le théorème suivant :

Théorème 5.1 (Loi de réciprocité quadratique).Soient p et q deux entiers impairs, alors :

1.(−1

p

)= (−1)

p−12

2.(

2

p

)= (−1)

p2−18

3.(p

q

)(q

p

)= (−1)

p−12

q−12

1. Soit a un entier premier impair. Montrer que :(a) Si a ≡ 1 mod 4, alors a est un résidu quadratique modulo p ssi p ≡ r mod a où r

est un résidu quadratique modulo aCorrection :

Si a ≡ 1 mod 4, alors, par la loi de réciprocité quadratique,(a

p

)=

(p

a

)ce qui

montre la propriété.(b) Si a ≡ 3 mod 4, alors a est un résidu quadratique modulo p ssi p ≡ ± (b)2 mod (4a)

où b est un entier impair premier à a.Correction :

⇐ : On a p ≡ ± (b)2 mod 4a où b est un entier impair. Traitons deux sous-cas :— Si p ≡ b2 mod 4a alors, comme b2 ≡ 1 mod 4 (car c’est un carré d’un nombre

b ≡ 1 ou 3 mod 4.) on sait que p ≡ 1 mod 4 donc (−1)p−12 = 1. Ainsi par la

loi de réciprocité quadratique on sait que(p

a

)=

(a

p

).

De plus, comme p = b2 mod a, on sait que p est un résidu quadratique modulo

a, donc(p

a

)= 1 =

(a

p

).

Feuille d’exercices no3 - Corrigé L3 SIF— Si p ≡ −b2 mod 4, alors p ≡ −1 ≡ 3 mod 4, donc (−1)

p−12 ≡ −1 mod 4 et

on sait aussi p = −b2 mod a.(p

a

)=

(−b2a

)=

(−1

a

)(b2

a

)=

(−1

a

)= −1 car a ≡ 3 mod 4

Donc(a

p

)= 1

⇒ : Supposons que(a

p

)= 1, alors :

soit (−1)p−12 = −1 et

(p

a

)= −1 (1)

soit (−1)p−12 = 1 et

(p

a

)= 1 (2)

— Dans le cas (1), alors p ≡ 3 mod 4. comme a ≡ 3 mod 4,(−1

a

)= (−1)(a−1)/2 =

−1 donc(−pa

)= 1, donc p ≡ −b2 mod a.

Si b est pair, on pose b′ tel que b = b′ + a où b′ est impair. On peut doncsupposer à présent que b est impair.Ainsi, on peut vérifier que b1 ≡ 1 mod 4 (faire un tableau de congruence), etdonc −b2 ≡ −1 ≡ 3 mod 4, donc p ≡ −b2 mod 4 et p ≡ −b2 mod a donc≡ −b2 mod 4a par le théorème chinois (a est impair).

— Dans le cas (2), p ≡ b2 mod a, et p ≡ 1 mod 4.comme précédemment, on peut supposer que b est impair, comme cela nechange rien modulo a. Par conséquent, b2 ≡ 1 mod 4 et p ≡ b2 mod 4 etp ≡ b2 mod a, donc p ≡ b2 mod (4a) par le théorème chinois. Ce qui conclutla preuve.

Feuille d’exercices no3 - Corrigé L3 SIF6 Un test de primalité : Les suites de Lucas

6.1 Énoncé du théorème

On va tout d’abord définir la suite de Lucas (Vk)k∈N associées à l’entier relatif a ∈ Z :

V0 = 2, V1 = a, Vk+1 = aVk − Vk−1, ∀k ≥ 1

On va vouloir montrer le critère de primalité suivant :

Théorème 6.1. soit n ∈ N\ {0, 1} tel que n est impair. Soit b ∈ N impair, et a ∈ Z et (Vk)k∈Nsa suite de Lucas associée.supposons que :

1.(a2 − 4

)est premier avec n

2. Vn+1 ≡ 2 mod n

3. Pour tout diviseur premier q de n+ 1, Vn+1q− 2 est premier avec n.

Alors, n est un nombre premier.

6.2 Notations des exercices préliminaires

Pour ce faire, on aura tout d’abord besoin de résoudre deux premiers exercices où l’on doitdéfinir quelques objets : Soit p un nombre premier impair, et a la classe de a modulo p.On définit l’anneau polynomial A := Fp [X] /

⟨X2 − aX + 1

⟩. On notera que Fp est alors un

sous-anneau de A.Posons α la classe de X modulo

(X2 − aX + 1

). On obtient alors que α ∈ A× et que :

α2 − a · α+ 1 = 0, α+ α−1 = a

6.3 Exercices préliminaires

Une fois que ces notations sont posées, on peut donc prouver ces deux premiers exercices :(dans l’ordre que l’on veut, le deuxième étant le plus facile)

1. Premier exercice :Soit ∆ := a2 − 4, supposons que le nombre premier impair p définit plus haut (s. 6.2) nedivise pas ∆.Montrer alors qu’on a ∆

p−12 ≡ ±1 mod p, puis montrer que :

(a) — Si ∆p−12 ≡ 1 mod p, alors αp−1 = 1

— Si ∆p−12 ≡ −1 mod p, alors αp+1 = 1

Correction :Si p ne divise par ∆ et que p est premier, alors par le petit théorème de Fermat,∆p−1 ≡ 1 mod p donc ∆

p−12 ≡ ±1 mod p. Développons (2α− a)2 :

(2α− a)2 = 4α2 − 4αa+ a2

= 4α (α− a) + a2

Comme α+ α−1 = a, on a :

(2α− a)2 = 4α(α−

(α+ α−1

))+ a2

= 4α(−α−1

)+ a2

= −4 + a2 = ∆ + pZ

Feuille d’exercices no3 - Corrigé L3 SIF

Si on met l’équation précédente à la puissancep− 1

2:

(2α+ a)p−1 = ∆p−12 + pZ =: ε

(2α− a)p = (2α− a) ε

2pαp − ap = (2α− a) ε or 2p ≡ 2 mod p, ap ≡ a mod p (par le petit thm de Fermat)

(2α− a) ε = 2αp − a

— Si ε = 1 (i.e. ∆p−12 ≡ 1 mod p), alors 2α − a = 2αp − a, sauf que 2 et a sont

inversibles dans A (Par le petit théorème de Fermat), donc 2−1 · 2α − 2−1a =

αp − 2−1a. Donc α− 2−1a = αp − 2−1a, d’où αp−1 = 1 .— Si ε = −1 (i.e. ∆

p−12 ≡ −1 mod p) donc 2αp − a = a − 2α, alors (αp + α) = a.

Par conséquent, αp + α = a.Or α+ α−1 = a, donc αp + α = α+ α−1, donc αp = α−1, d’où αp+1 = 1 .

(b) ∀m ∈ Z, on a l’équivalence suivante :

αm = 1⇔ αm + α−m = 2.

Correction :On sait que (1, α) est une base de A en tant que Fp−espace vectoriel.En effet, cette famille est libre dans A : Supposons que on ait λ1, λ2 ∈ Fp tel queλ1 + αλ2 = 0 dans A, cela se traduit par : ∃k, k′ ∈ Fp tel que :

λ1[1 + k

(X2 − aX + 1

)]+ λ2

[X + k′

(X2 − aX + 1

)]= 0

On peut alors en déduire en développant les équations suivantes :

λ1k + k′λ2 = 0 (1)k (−a)λ1 − ak′λ2 + λ2 = 0 (2)

(k + 1)λ1 + k′λ2 = 0 (3)

Ce qui devient :

λ1k = −k′λ2 (1)

λ2 = 0 (2)

(k + 1)λ1 + k′λ2 = 0 (3)

Ainsi, (k + 1)λ1 = 0. Si k 6= 0, par (1), λ1 = 0, Si k = 0, alors (0 + 1)λ1 = 0 doncλ1 = 0.dans tous les cas (1, α) est une famille libre de A en tant que Fp−espace vectoriel, ordimFp A = 2, cette famille forme une base de A en tant que Fp−espace vectoriel.Montrons à présent que ∀x ∈ A, x2 = 0⇒ x = 0.Soit x ∈ A, ∃u, v ∈ Fp tels que x = u + vα, on a alors x2 = u2 + v2α2 + 2uvα, orα+ α−1 = a donc α2 = αa− 1.Ainsi, x2 =

(u− v2

)+(av2 + 2uv

)α, donc si x2, comme (1, α) est une base de A et

que u− v2 et av2 + 2uv ∈ Fp, on a :{u2 − v2 = 0

av2 + 2uv = 0

Feuille d’exercices no3 - Corrigé L3 SIFD’où : {

(u+ v) (u− v) = 0

av2 + 2uv = 0

Donc u = ±v, donc v2 (a± 2) = 0.Comme p ne divise pas a2 − 4, il ne divise pas a ± 2 donc a ± 2 6≡ 0 mod p, doncv = 0 mod p par le lemme de Gauss, donc u = 0 donc x = 0.On veut montrer dans cet exercice que αm = 1 ⇔ αm + α−m = 2 ∀m ∈ Z, on posem ∈ Z quelconque.Si αm = 1, alors αm + α−m = 2 de manière immédiate.Si αm + α−m = 2, montrons que (αm − 1)2 = 0 (et ainsi on aura αm − 1 = 0 et onaura résolu l’exercice).

(αm − 1)2 = α2m − 2αm + 1, on multiplie ensuite par α−m ∈ A :

(αm − 1)2 = αm − 2 + α−m = 0 par hypothèse.

Ainsi αm = 1.2. Deuxième exercice : Montrer la relation de récurrence suivante :

∀k ∈ N, Vk + pZ = αk + α−k.

Correction :Si k = 0, V0 = 2 = α0 + α−0, si k = 1, V1 = a = α+ α−1.Soit k ∈ N tel que k > 1. Supposons que ∀l ≤ k, Vl + pZ = αl + α−l, on a alors :

Vk+1 + pZ = (aVk − Vk−1) + pZ = a(αk + α−k

)− αk−1 − α−k+1

d’où : Vk+1 + pZ = αk+1 + α−(k+1), ce qui montre le résultat par récurrence.Indications pour le premier exercice :— Montrer que ∆p−1 ≡ 1 mod p.— Se rappeler que A est un corps de caractéristique p, cela signifie que ∀a1, a2 ∈ A,

(a1 + a2)p = ap1 + ap2. Comme a est calculé modulo p, donc ap ≡ a mod p.

— Pour la (b) : considérer la base (1, α) du Fp−espace vectoriel A et montrer que

∀x ∈ A, x2 = 0⇒ x = 0.

6.4 Démonstration du théorème

Maintenant que ces deux exercices sont prouvés/admis, on va vouloir démontrer le théorème(les notations de la section 6.2 ne sont pas utilisées, elles serviront à la preuve.) :

Théorème 6.2. soit n ∈ N\ {0, 1} tel que n est impair. Soit b ∈ N impair, et a ∈ Z et (Vk)k∈Nsa suite de Lucas associée.supposons que :

1.(a2 − 4

)est premier avec n

2. Vn+1 ≡ 2 mod n

3. Pour tout diviseur premier q de n+ 1, Vn+1q− 2 est premier avec n.

Alors, n est un nombre premier.

On peut démontrer le théorème avec les étapes suivantes :

Feuille d’exercices no3 - Corrigé L3 SIF1. Poser p un diviseur premier de n, le but sera de montrer que n = p.

2. Utiliser les exercices précédents pour montrer que αn+1 = 1 et αn+1q 6= 1 pour tout

diviseur q premier de n+ 1.

3. En déduire l’ordre de α dans le groupe multiplicatif A×.

4. Montrer ensuite que soit αp+1 = 1, soit αp−1

5. En déduire que n+ 1 divise p± 1 et conclure.

Correction :Soit p un diviseur premier de n, et notons ∆ = a2−4 et on peut ainsi définir toutes les notationsde la section 6.2 (A, a, α...) où p est le nombre premier que l’on vient de fixer ici.Par le deuxième exercice, on sait que αn+1 + αn+1 = Vn+1 mod p et α

n+1q + α

n+1q = Vn+1

q

mod p pour tout diviseur premier q de n+ 1.On va donc chercher à calculer Vn+1 et Vn+1

qmodulo p pour trouver l’ordre de α dans A×.

Pour cela, le premier exercice semble donner des résultats, comme ∆∧ n = 1, aucun diviseurde n, sauf 1, ne divise ∆ donc p ne divise pas ∆.Comme Vn+1 ≡ 2 mod n, et que pour tout diviseur q de n + 1, Vn+1

q− 2 est premier avec n,

alors p ne divise pas Vn+1q− 2, ainsi :

Vn+1 ≡ 2 mod n

Vn+1q6≡ 2 mod p pour tout diviseur premier q de n+ 1

Par conséquent :

αn+1 + α−(n+1) ≡ 2 mod n

αn+1q + α

−n+1q 6≡ 2 mod p pour tout diviseur premier q de n+ 1

Par le deuxième item du premier exercice, on a donc que αn+1 = 1 mod p et αn+1q 6≡ 1

mod p pour tout diviseur q premier de n+ 1 donc l’ordre de α dans le groupe A× est n+ 1.Par le premier exercice, comme p ne divise pas ∆, on sait que ∆

p−12 ≡ ±1 mod p, donc par

le premier item, soit αp−1 = 1, soit αp+1 = 1 dans A× (α est inversible dans A).Ainsi, comme α est d’ordre n+ 1, n+ 1 divise p+ 1 ou p− 1, comme p ≤ n, n+ 1 divise p+ 1et p+ 1 ≤ n+ 1, donc n = p.On a donc bien montré que n est premier.

Feuille d’exercices no4 L3 SIF

Ici, si on prend un anneau A, A× désignera les inversibles de A et A∗ les éléments non nulsde A. Dans le cas où A est un corps, on rappelle que A∗ = A×.

1 Un test de primalité.

1. théorème de Wilson :Soit p ∈ N\ {0, 1}, on a l’équivalence suivante :

p est un nombre premier ssi p divise (p− 1)! + 1

avec l’indication suivante : montrer que 1 + (−1)p−1 (p− 1)! ≡ 0 mod p en étudiant lesracines de Xp−1 − 1.Correction :Soit p ∈ N∗. On notera a = a mod p

• ⇒ Supposons que p soit premier. Montrons que p divise (p− 1)!− 1.On veut pour cela étudier les racines deXp−1−! dans Fp [X]. Or, par le petit théorème de Fermat,on sait que ∀a ∈ Fp, ap−1−1 ≡ 0 mod p car p est premier. Les p−1 racines distinctesde Xp−1 − 1 dans Fp [X] sont donc exactement

{0, · · · , p− 1

}dans Fp. Donc :

Xp−1 − 1 =

p−1∏a=1

(X − a)

En évaluant en 0, on a :

−1 =

(p−1∏a=1

a

)(−1)p−1

d’où 1+(−1)p−1 (p− 1)! ≡ 0 mod p. Dans le cas p = 2, 2 divise déjà (2− 1)!+1 = 2.Sinon, p− 1 est pair car p est premier. Donc p divise (p− 1)! + 1.

• ⇐ Supposons que p divise (p− 1)! + 1, montrons que p est premier.Soit k un diviseur premier de p, différent de p.Comme k est un diviseur premier de p, k|p. Comme k < p, alors k divise (p− 1)!.Donc

k| (p− 1)! et k| (p− 1)! + 1

Donc k|1 ce qui est absurde car k est premier. Donc k = p.

2 Exercices sur les corps finis.

1. Inverser des éléments sur des anneaux et des corps finis :Soit A l’anneau A = F2 [X] /

⟨X3 + 1

⟩.

Feuille d’exercices no4 L3 SIF(a) Factoriser X3 + 1 dans F2 [X].

Correction :

X3 + 1 = (X − 1)(X2 +X + 1

)Or, X2 +X + 1 est un polynôme de degré 2 sans racine dans le corps F2, donc il estirréductible dans F2 [X].

(b) Lister les éléments de A×. Hormis 1, ont-ils un lien l’un envers l’autre ?Correction : Si Q ∈ A est inversible dans A, alors il existe U, V ∈ F2 [X] tels queU ·Q+V ·X3+1 = 1 dans F2 [X], donc X3+1 et Q doivent être premiers entre eux.Il faut donc exclure les multiples de X + 1 et X2 +X + 1, or les polynômes de degré1, 2 dans F2 [X] sont :— deg 1 : X,X + 1— deg 2 : X2 +X + 1, X2 +X,X2 + 1, X2

Or, dans A, X3 = 1 donc on a pas de polynôme de degré ≥ 3, les éléments de A∗

sont{1, X,X2

}. Comme X3 = 1, on peut observer que X et X2 sont inverses l’un de

l’autre.(c) On rappelle que l’ on peut déterminer l’inversibilité et l’inverse d’un élément via

l’identité de Bézout.Déterminer l’inverse de X2 + 1 dans le corps F2 [X] /

⟨X4 +X + 1

⟩.

Correction :On admettra ici que X4 +X +1 est un polynôme irréductible de degré 4 dans F2 [X]car ce sera montré dans l’exercice suivant. On va faire l’algorithme d’Euclide étendu :

X4 +X + 1 =(X2 + 1

) (X2 + 1

)+X

X2 + 1 = X ·X + 1

X2 + 1−X ·X = 1

Pour retrouver les coefficients de Bézout, on doit à présent remplacer le reste X de ladivision euclidienne par son expression développée :

X2 + 1−[X4 +X + 1−

(X2 + 1

) (X2 + 1

)]·X = 1(

X2 + 1) [

1 +X3 +X]+[X4 +X + 1

](X) = 1

D’où :(X3 +X + 1

) (X2 + 1

)+(X4 +X + 1

)X = 1, donc U = X et V = X3+X+1

dans la relation de Bézout.L’inverse de X2 + 1 dans F2 [X] /

(X4 +X + 1

)est donc X3 +X + 1.

2. Des polynômes irréductibles dans F2 [X] :

(a) Montrer que X2 +X + 1 est l’unique polynôme irréductible de degré 2 sur F2 [X].Correction :Les autres polynômes de degré 2 sur F2 sont :X2, X2+1 etX2+X qui sont réductiblessur F2 (ils possèdent des racines).

(b) Lister tous les polynômes irréductibles de F2 [X] de degré 1, 2, 3.Correction :Pour savoir si un polynôme de degré 1, 2, 3 est irréductible, il suffit de montrer qu’iln’a pas de racine dans le corps. Dans F2 [X] :— degré 1 : X,X + 1 sont tous les deux réductibles.

Feuille d’exercices no4 L3 SIF— degré 2 : X2, X2 + 1, X2 +X sont réductibles. X2 +X + 1 est irréductible.— degré 3 : X3 +X + 1 X3 +X2 + 1 sont irréductibles.Pour lister des polynômes dans un petit corps, on peut se servir d’un arbre et raisonnerdirectement dessus pour éliminer les polynômes réductibles.

(c) Montrer que X4 +X + 1 ∈ F2 [X] est irréductible.Correction :Si X4 + X + 1 était réductible, comme il n’a pas de racines dans F2, il serait doncle produit de deux polynômes irréductibles de degré 2 sur F2. Le seul polynômesirréductible étant X2 +X + 1, le seul polynôme réductible de degré 4 dans F2 [X]

qui n’admet pas de racines dans F2 est donc(X2 +X + 1

)2= X4 + X2 + 1.

X4 +X + 1 est donc un polynôme irréductible de F2 [X]. De même on peut montrerque X64+X3+1 et X4+X3+X2+X+1 sont aussi des polynômes irréductibles deF2 [X], afin de terminer la liste des polynômes irréductibles de degré 4 dans F2 [X].Donc X4 +X + 1 est irréductible.

(d) Soit P = X4 +X + 1 et K = F2 [X] / (P ). Quel est le cardinal de K ? sa caractéris-tique ?Correction :#K = 2degP = 24 = 16, sa caractéristique vaut celle de F2, soit 2.

(e) Soit α la classe de X modulo P .Montrer que α est un générateur de K∗.Correction :Comme #K = 16 et que K est un corps, K× = K∗ et #K∗ = 15 ordK∗ (α) |15 par lethéorème de Lagrange. Donc ordK∗ (α) ∈ {1, 3, 5, 15}. On notera ord (α) = ordK∗ (α).— Si ord (α) = 1, alors α = 1 ce qui est absurde.— Si ord (α) = 3, α3 = 1, donc α4 = α, or α4 + α+ 1 = 0 donc 1 = 0 dans F2 ce qui

est absurde.— Si ord (α) = 5, α5 = 1, or α4 + α+ 1 = 0 donc :

α5 = 1&α4 + α+ 1 = 0

α5 = 1&α5 + α2 + α = 0

α5 = 1&α2 + α+ 1 = 0

Donc :

α4 + α+ 1 = 0⇔ α4 + α2 = 0

⇔ α2(α2 + 1

)= 0

⇔ α2 = 1 car α2 6= 0

Ce qui est absurde car 5 - 2.Donc, ord (α) = 15.

(f) Combien de générateurs possède K∗ ? Écrire les coordonnées de chacun de ces géné-rateurs dans la base

(1, α, α2, α3

)de K en tant que F2−espace vectoriel.

Correction :Par le corollaire 10 de la section 2.2, le groupe K∗ a ϕ (15) générateurs qui sont :{

αk|1 ≤ k ≤ 15, k ∧ 15 = 1}

soit : {α, α2, α4, α7, α8, α11, α13, α14

}

Feuille d’exercices no4 L3 SIFÉcrivons ces générateurs dans la base

{1, α, α2

}:

α = α

α2 = α2

α3 = α3

3. Construire son propre corps finis :Construire les corps F4,F8,F16 et F25. Il n’y a pas de procédé général pour trouver unpolynôme irréductible de degré n, donc pour construire un corps FpnCorrection :— F4 : on cherche un polynôme irréductible unitaire de degré 2 sur F2 : F2 [X] /

⟨X2 +X + 1

⟩— F8 : F2 [X] /

⟨X3 +X + 1

⟩, ou F2 [X] /

⟨X3 +X2 + 1

⟩— F16 : F2 [X] /

⟨X4 +X + 1

⟩— F25 : On veut un polynôme irréductible de degré 2 sur F5, par exemple X2 +X + 1.

F5 [X] /⟨X2 +X + 1

⟩.

4. Isomorphisme entre deux corps finis :On sait que tout corps finis d’ordre pn sont isomorphe.Donner un isomorphisme explicite entre F2 [X] /

⟨X4 +X + 1

⟩et F2/

⟨X4 +X3 + 1

⟩Correction :On veut expliciter l’isomorphisme de corps entreK1 := F2 [X] / (P1) etK2 := F2 [X] / (P − 2)où P1 = X4 +X + 1 et P2 = X4 +X3 + 1.Soit ϕ un isomorphisme entre K1 et K2, ϕ envoie 0 sur 0, 1 sur 1 et un générateur deK×1 sur un générateur de K×2 .Notons β la classe de X dans K2, β est d’ordre 15 dans K×2 qui comprends les généra-teurs : {

β, β2, β4, β8, β7, β11, β13, β14}

Or, β, β2, β4 et β8 sont des racines de P2 dans K2. Or β7 = β−8, β11 = β−4, β13 =β−2, β14 = β−1 Soit α une racine de P2, montrons que α−1 est racine de P1 : P1

(α−1

)=

α−4 + α−1 + 1 Or, α4 6= 0 et :

α4P1

(α−1

)= 1 + α3 + α4 = P2 (α) = 0

Donc α−1 est bien racine de P1, donc β7, β11, β13, β14 sont racines de P1.L’isomorphisme β 7→ β−1 convient donc.

5. Quelques petites factorisations :

(a) Factoriser X2 +X ∈ F2 [X] en produit de polynômes irréductibles dans F2 [X].(b) Puis X4 +X dans le même corps....(c) Puis X8 +X...(d) Enfin, X16 +X dans ce même corps.Correction :On va utiliser le théorème 17 de la section 2.5 : si K est un corps de cardinal q, et sin ∈ N∗, si on note A (d,K) l’ensemble des polynômes irréductibles unitaires de K [X] telque d0F = d alors :

Xqn −X =∏d|n

∏F∈A(d,K)

F

Feuille d’exercices no4 L3 SIF(a) X2 +X = X (X + 1)

(b) X4 +X = X4 −X = X22 −X =(X2 +X + 1

)(X + 1)X

(c) X8 +X =(X3 +X + 1

) (X3 +X2 + 1

)X (X + 1) car 1, 3|3.

(d) X16 + X = X24 − X, or 4 est divisible par 1, 2 et 4. Il existe, comme on a deuxpolynômes irréductibles de degré 1 et 1 polynôme irréductible de degré 2 seulement,en calculant les degrés, 3 polynômes irréductibles de degré 4 (cf exercice 2.2.(c)), doncon a bien :

X16+X = X (X + 1)(X2 +X + 1

) (X4 +X + 1

) (X4 +X3 + 1

) (X4 +X3 +X2 +X + 1

)

3 Trouver des inverses dans un corps avec de l’algèbre linéaire.

Soit K = Q et P = X3 + X + 1 ∈ K [X], on note A la Q−algèbre K [X] / (P ). A est dedimension 3.On note α la classe de X modulo P . On sait que

(1, α, α2

)est une Q−base de A.

1. Exprimer X5 + 1 dans cette base.Correction :

X5 + 1 =(X3 +X + 1

) (X2 − 1

)+(−X2 +X + 2

)= α2 + α+ 2

2. On admettra que A est un corps.NB :en fait, on peut montrer que P est irréductible via le lemme suivant :

Lemme 3.1. Sin−1∑i=0

aiXi ∈ Z [X] a une racine dans Q, alors cette racine est également

dans Z et divise a0.

Comme on a ici un polynôme de degré 3, il suffit de montrer qu’on a pas de racine dansQ.

3. On veut déterminer l’inverse de 1 + α dans la base(1, α, α2

)avec de l’algèbre linéaire :

(a) Poser l’endomorphisme f :

Q [X] / (P ) → Q [X] / (P )a 7→ a (α+ 1)

Montrer que cet endomorphisme est bijectif.Correction :Cet endomorphisme est injectif, de surjectif, car α+ 1 6= 0.

(b) Donner la matrice de f dans la base(1, α, α2

).

Correction :Notons M la matrice de cet endomorphisme de f dans la base

(1, α, α2

). M =1 0 −1

1 1 −10 1 1

Feuille d’exercices no4 L3 SIF(c) En déduire l’inverse de (1 + α).

Correction :

On a (1 + α)−1 = f (1)−1 or, on aM−1 =

2 −1 1−1 1 01 −1 1

donc (1 + α)−1 = 2−α+α2.

(d) Retrouver ce résultat avec l’algorithme d’Euclide.Correction :On peut retrouver :

(X + 1)(X2 −X + 2

)−(X3 +X + 1

)= 1

4 Fonction de Möbius et polynômes irréductibles sur Fq.

Dans cette partie, on va chercher à dénombrer le nombre de polynômes irréductible d’uncorps finis Fq [X]. Le premier exercice portera sur la fonction de Möbius :

1. Fonction de Möbius :On définit la fonction de Möbius µ de la manière suivante :

µ :

N∗ → {−1, 0, 1}

n 7→

1 si n = 1

0 si n a un facteur carré(−1)r si n = p1 · · · pr (premiers distincts)

(a) Montrer que µ est multiplicative, i.e ∀n,m ∈ N∗ tel que m ∧ n = 1, µ (mn) =µ (m)µ (n).Correction :— Si n ou m = 1, alors immédiatement µ (mn) = µ (m)µ (n).— Si n ou m a un facteur carré, de même immédiatement : µ (mn) = µ (m)µ (n) = 0.— Si n = p1 · · · pr et si m = p′1 · · · p′l où p1, · · · , pr sont des premiers tous distincts

et p′1, · · · , p′l sont des premiers tous distincts. Comme m et n sont premiers entreeux, p1, · · · , pr, p′1, · · · , p′l sont tous distincts. Ainsi :

µ (mn) =∏pi,p′i

(−1)pip′i = µ (m)µ (n)

(b) Montrer que∑d|n

µ (d) =

{1 si n = 1

0 sinon.

Correction :

Feuille d’exercices no4 L3 SIF

Si n ∈ N∗\ {1}, tel que n =r∏i=1

pαii , avec pi est premiers tous distincts, alors :

∑d|n

µ (d) = µ (1) +r∑i=1

µ (pi) +∑i<j

µ (pipj) + · · ·+ µ (p1 · · · pr)

= 1 +

r∑i=1

(−1)1 +∑i<j

(−1)2 + · · ·+ (−1)r

=r∑

k=0

(r

k

)(−1)k = (1− 1)k = 0

Le cas n = 1 étant immédiat.

(c) Montrer la formule d’inversion de Möbius : si g (n) =∑d|n

f (d) alors :

f (n) =∑d|n

g (d)µ(nd

)=∑d|n

g(nd

)µ (d)

Correction :Si g (n) =

∑d|n

f (d), alors :

∑d|n

g(nd

)µ (d) =

∑d|n

∑d′|n

d

f(d′)µ (d)

=∑dd′|n

f(d′)µ (d)

=∑d′|n

f(d′)∑d| n

d′

µ (d)]

= f (n)

L’autre partie de l’équation s’obtient en effectuant le changement de variable d ↔n/d :

f (n) =∑d|n

g (n/d)µ (d) =∑d|n

g (d)µ (n/d)

2. Application no1 :Fonction d’Euler et de Möbius :Montrer que pour n ∈ N∗ :

ϕ (n)

n=∑d|n

µ (d)

d

Correction :On rappelle que n =

∑d|n

ϕ (d), donc en posant g = id et f = ϕ, on obtient :

ϕ (n) =∑d|n

µ (d)n

d

Feuille d’exercices no4 L3 SIF3. Application no2 :Dénombrer les polynômes irréductibles de Fq :

On va donc chercher à montrer le théorème suivant :Théorème 4.1. Soit n ∈ N∗.Notons A (n, q) l’ensemble des polynômes irréductibles unitaire de degré n de Fq [X]. Onnote I (n, q) = #A (n, q). On rappelle que :

Xqn −X =∏d|n

∏P∈A(d,q)

P

Alors :• Si µ est la fonction de Möbius, I (n, q) =

1

n

∑d|n

µ(nd

)qd

Correction :On sait queXqn−X =

∏d|n

∏P∈A(d,q)

P , donc en regardant les degrés : qn =∑d|n

∑P∈Q(d,q)

degP .

D’où :qn =

∑d|n

d · I (d, q)

En posant g (n) = qn et f (d) = d·I (d, q), on obtient par la formule d’inversion de Möbius :

n · I (n, q) =∑d|n

qdµ(nd

)=∑d|n

qnd µ (d)

I (n, q) =1

n

∑d|n

µ (n/d) qd

• On a l’équivalent suivant :

I (n, q) ∼n→+∞

qn

n

Correction :

I (q, n) =1

n

qn +∑

d|n,d<n

qdµ(nd

)︸ ︷︷ ︸

=:rn

On veut montrer que rn est négligeable devant qn pour prouver notre équivalent, i.e

on veut montrer que|rn|qn

tend vers 0 quand n tend vers +∞.

|rn| ≤[n2 ]∑d=1

qd

≤ q − q[n2−1]+1

1− q

≤ q[n2 ]+1

q − 1

Donc|rn|qn

tend vers 0 quand n tend vers +∞. D’où l’équivalent.

Feuille d’exercices no4 L3 SIF• En déduire la probabilité de choisir un polynôme unitaire irréductible lorsque l’on

choisit un polynôme au hasard, de degré n, dans Fq [x] quand n est grand.Correction :Immédiat par l’équivalent.

5 Point technique : Remonté de l’algorithme d’Euclide étendu,chercher des inversibles

Comment relier ’chercher un inversible’ et relation de Bézout

On a pu voir différent exemples où on cherchait à trouver des inversibles dans un anneauquotient K [X] / (P ). Voici un généralisation.Soit A un anneau, et I un idéal de A. On forme ainsi l’anneau quotient Q = A/ (I). Chercherl’inverse de x ∈ A/ (I) revient à chercher un élément y ∈ A tel que xy = 1 dans A/ (I).Prenons maintenant le cas particulier où on s’intéresse à l’anneau quotient K [X] / (P ), où Kest un corps, et P un polynôme unitaire irréductible de K [X], de degré n.Soit Q un polynôme de l’anneau quotient K [X] / (P ). Si Q est inversible, d’inverse U mod Poù U ∈ K [X], alors il existe V ∈ K [X] tel que

U ·Q+ V · P = 1 dans K [X]

C’est donc bien la relation de Bézout que l’on connait, on va voir ensuite comment retrouver lescoefficient de cette relation via la remonté de l’algorithme d’Euclide.

Algorithme d’Euclide étendu : Exemple sans calcul concret.

Soit K un corps, soient A,B ∈ K [X] tel que degA > degB, on cherche à faire l’algorithmed’Euclide pour obtenir le pgcd de A et B :Cet algorithme se base sur le fait suivant, sachant A,B ∈ K [X] :

pgcd (A,B) = pgcd (A mod B,B)

Donc pour regarder le pgcd entre deux polynômes A et B, on peut simplifier et regarder cepolynôme modulo celui de plus petit degré. Dans le cas où degA > degB, cela revient à regarderle pgcd entre B et le reste de la division euclidienne de A et B.Un excellent schéma de l’algorithme d’Euclide sur Wikipédia pour deux entiers a et b :

Feuille d’exercices no4 L3 SIFOn commence par faire la division euclidienne de A par B :

A = Q1 ·B +R1 On effectue ensuite la division ecudlienne du diviseur avec le reste :B = Q2 ·R1 +R2

R1 = Q3 ·R2 +R3

Jusqu’à ce que l’on arrive à un reste égal à 1 (alors les deux polynômes sont donc premiers entreeux vu que leur pgcd vaut 1.) ou alors 0 (alors les deux polynômes ont un facteur commun quicorrespond au dernier reste non nul).en effet, par exemple si on avait :

A = Q1 ·B +R1, degR1 < degB

B = Q2 ·R1 +R2

R1 = Q3 ·R2 + 0

Alorspgcd (A,B) = pgcd (R1, B) = pgcd (R1, R2) = pgcd (R2, Q3R2) = R2

Dans le cas où on obtiendrait par exemple :

A = Q1 ·B +R1

B = Q2 ·R1 +R2

R1 = Q3 ·R2 + 1

On a bien que A et B soient premiers entre eux. supposons que B soit irréductible unitaire, onaimerait alors par exemple trouver l’inverse de A dans K [X] / (B), on sait qu’il est inversible carils sont premiers entre eux, mais on aimerait calculer son inverse. Donc retrouver U, V ∈ K [X]tel que AU + V B = 1 dans K [X].On va effectuer une remonté de l’algorithme, c’est-à-dire qu’on aimerait avoir à partir de

R1 −Q3 ·R2 = 1

une expression avec un 1 à droite, mais des polynôme multiplié par A et B à gauche et non parR1 et R2. On regarde notre dernier reste avant, R2 = Q1 −Q2 ·R1, qui lui sera exprimé ensuiteen fonction de A et B, donc on injecte cette expression là :

R1 −Q3 (B −Q2 ·R1) = 1

On refait pareil en regardant ce que vaut R1 lors de la premier étape de l’algorithme :(A−Q1 ·B)−Q3 (B −Q2 · (A−Q1 ·B)) = 1

Ensuite on développe tout et on regarde quels sont les expression multipliée par A et B :

A−Q1B −Q3B −Q2Q3A−Q1Q2Q3B = 1

soit :A · (1−Q2Q3) +B (−Q1 −Q3 −Q1Q2Q3) = 1

La correction des divers TD donnent des exemples d’algorithme d’Euclide et de remonté.