Upload
others
View
2
Download
0
Embed Size (px)
Citation preview
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é.