Démonstration du théorème de Pépin

stfj

Bonjour

Je rappelle son énoncé : 

$$\forall n\in \mathbb N^*, \,F_n \text{ premier }\iff 3^{\frac{F_n-1}{2}}\equiv -1\mod F_n$$

________________________________________

J'aimerais démontrer ce théorème dont l'énoncé est simple à comprendre mais dont la démonstration nécessitera que je rafraîchisse quelques connaissances arithmétiques, je crois, si j'en juge une lecture en diagonale de l'article wikipédia.

J'espère bénéficier de votre aide. 

Cordialement.

depasse

Bonjour
@stfj J'espère pouvoir t'aider. Pourrais-tu nous dire déjà le premier point que tu ne comprends pas dans la preuve donnée sur Wiki?
Cordialement
Paul

Calembour

Je crois que toutes les démonstrations de ce théorème contiennent un pépin

depasse

le roi du calembour ou du calembour la reine?

Paul Broussous

stfj a dit :

... la démonstration nécessitera que je rafraîchisse quelques connaissances arithmétiques ...

  Après lecture de la page Wikipédia, il y a, outre des connaissances de base sur les congruences et les anneaux $\Z /nZ$, deux prérequis :

1) Le "critère d'Euler" qui affirme que $a$ est un carré modulo $p$ premier (resp. n'est pas un carré) si, et seulement si, $a^{(p-1)/2}\equiv 1$ mod $p$ (resp. $a^{(p-1)/2}\equiv -1$ mod $p$). C'est élémentaire (niveau L1/L2).

2) Loi de réciprocité quadratique qui relie, pour deux nombres premiers $p$, $q$, les assertions "$p$ est un carré modulo $q$" et "$q$ est un carré modulo $p$". C'est moins élémentaire (disons niveau M1 2024).

 Dans un premier temps tu peux admettre la loi de réciprocité.

stfj

Dans $\Z/p\Z$, supposons qu' $\, \exists b: a=b^2$. Alors comme $b^{p-1}=1$, on a $a^{\frac{p-1}{2}}=1$.

JLapin

Oui

stfj

Toujours dans $\Z/p\Z$, supposons que $a^{\frac{p-1}{2}}=1$. Pourquoi  $a$ est-il un carré ?

Par ailleurs, il faut précédemment exclure le cas où $a=b=0$

gai requin

Il y a $\frac{p-1}2$ carrés non nuls (pourquoi ?) qui sont donc les racines de $X^{\frac{p-1}2}-1$.

stfj

Soit $a\neq 0$. Alors $a^{p-1}=1$. Donc $(a^{\frac{p-1}{2}}-1)(a^{\frac{p-1}{2}}+1)=0$. Donc $\begin {cases} a^{\frac{p-1}{2}}=1 \\ou \\ a^{\frac{p-1}{2}}=-1\end{cases}$

stfj

$X^{\frac{p-1}2}-1$ est un polynome de degré $\frac{p-1}{2}$ donc a au plus $\frac{p-1}{2}$ racines.

stfj

Voyons sur un exemple $p=13$. $\Z/13\Z=\{-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6\}$$$1²=1;2²=4;3²=-4;4²=3; 5²=-1;6²=-3$$ $$1^6=1;2^6=4^3=64=65-1=-1; 3^6=1;4^6=3^3=1; 5^6=-1;6^6=-1$$Les racines de $X^6-1$ sont $1=1^2,3=4^2,4=2^2,-4=3^2,-1=5^2 $ et $-3=6^2$. On constate en effet que les racines de $X^6-1$ sont les carrés de $\Z/13\Z$

___________________________

Si $a=b^2$ et $c=d^2$ et si $a=c$, alors $b^2-d^2=(b-d)(b+d)=0$ donc $b=d$ ou $b=-d$. Donc il y a au moins $\frac{p-1}{2}$ carrés distincts. Et on a vu que ces carrés sont racines de $X^{\frac{p-1}2}-1$. Quant aux non-carrés $a$, ce sont donc forcément les $a$ tels que $a^{\frac{p-1}{2}}=-1$

stfj

@depasse , @Paul Broussous , @gai requin , bonjour

Merci de votre aide. Avant de me lancer dans la démonstration, j'aimerais voir un peu comment fonctionne ce test. Les nombres de Fermat sont déjà intéressants, c'est le moins qu'on puisse dire. $$\forall n\in \mathbb N,\, F_n\doteq 2^{2^n}+1$$ $$F_1=5$$ $$3^{\frac{5-1}{2}}=3^2=4=-1$$Comment cela fonctionne-t-il avec $F_5=4\,294\,967\,297$?

Cordialement

Stéphane

gai requin

Pour compter le nombre de carrés non nuls, on peut étudier le morphisme $x\mapsto x^2$ du groupe $\mathbb F_p^{\times}$ dans lui-même.

Math Coss

sage: def F(n): return 2^(2^n)+1
sage: F(5)
4294967297
sage: (power_mod(3,(F(5)-1)//2,F(5))+1) % F(5)
10324304
sage: factor(F(5))
641 * 6700417

La fonction power_mod(n,a,m) calcule $n^a\pmod{m}$ – beaucoup plus efficacement que (n^a)%m.

stfj

Avec sagemath,

____________________

def F(n): return 2^(2^n)+1
power_mod(3,(F(5)-1)//2,F(5))

__________________________

fournit bien $10324303$, qui n'est pas égal à $-1$. D'après le test de Pépin, $F_5$ n'est donc pas premier.

gebrane

En exercice c'est mieux 

Exercice . On pose pour tout $n \in \mathbb{N}$, $F_n = 2^{2^n} + 1$ ; $F_n$ est par définition le $n$-ième nombre de Fermat.

(a) Soit $m \in \mathbb{N} \setminus \{0\}$. En utilisant la factorisation

$$X^{2n+1} + 1 = (X + 1)(X^{2n} - X^{2n-1} +\cdots + 1),$$

prouver que si $2^m + 1$ est premier alors $m$ est une puissance de 2.

(b) Calculer $F_n$ pour $n \leq 4$ et vérifier qu’ils sont tous premiers.

(c) Montrer que tout diviseur premier de $F_5$ est de la forme $64k + 1$.

(d) Montrer que $F_5$ est divisible par $641 = 1 + 5 \cdot 2^7 = 54 + 24$.

(e) Montrer que pour $n \neq m$, $F_n$ et $F_m$ sont premiers entre eux et en déduire l’existence d’une infinité de nombres premiers.

(f) Soit $p = F_n$ premier ; montrer qu’un élément de $(\mathbb{Z}/p\mathbb{Z})^*$ est générateur si et seulement s’il n’est pas un carré. En utilisant la loi de réciprocité quadratique, montrer que $3$, $5$, $7$ sont des générateurs de $(\mathbb{Z}/p\mathbb{Z})^*$ pour $n \geq 2$. En déduire alors le critère de Pépin : $p = F_n$ est premier si et seulement si $3^{(p-1)/2} \equiv -1 \mod p$.

stfj

La question (a) est un peu subtile. Si par exemple on considère $2^6+1$, il faut écrire $(2^2)^3+1=(2^2+1)\times ((2^2)^2-(2^2)^1+1))$

gebrane

Tu sais qu'un entier s'écrit comme une puissance de 2 multipliée par un entier impair, et en utilisant l' indication, tu démontres que l'entier impair est 1.

stfj

Soit $p=F_n$ premier ; montrer qu’un élément de $(\Z/p\Z)^∗$ est générateur si et seulement s’il n’est pas un carré.

________________________

Examinons le cas $n=1, F_1=5$. Les éléments de $(\Z/5\Z)^∗$ sont $-2,-1,1,2$. $1^2=1: 2^2=-1$. Les générateurs de $((\Z/5\Z)^∗,\times )$ sont bien $2$ et $-2$ : $$2^0=1;2^1=2;2^2=-1;2^3=-2$$

____________________________

Le problème des autres est que $$a^{\frac{p-1}{2}}=1$$

___________________________

Me reste à prouver que tout non-carré est un générateur.

______________________________

Si $F_n$ est premier, le symbole de Legendre $\left( \frac{3}{F_n} \right)=\left( \frac{F_n} {3}\right)=-1$ donc $3^{\frac{F_n-1}{2}}=-1$

gebrane

stfj a dit :

Soit $p=F_n$ premier ; montrer qu’un élément de $(\Z/p\Z)^∗$ est générateur si et seulement s’il n’est pas un carré.

________________________

Pour le sens direct, c'est simple si $a$ est un générateur et $a=b^2$ alors aussi $b$ est un générateur et donc l'ordre de $b$ doit etre egale à $p-1$   mais $a^{\frac{p-1}2}=(b^2)^{\frac{p-1}2}=b^{p-1}=1$ contradictoire avec $a$ d'ordre $p-1$

Julia Paule

Une autre méthode pour le critère d'Euler :

Si $a$ est un carré, alors $a=x^2, a^{\frac{p-1}{2}}=(x^2)^{\frac{p-1}{2}}=x^{p-1}=1$.

Si $a^{\frac{p-1}{2}}=1$, on distingue :

- si $p \equiv 1 \pmod 4$, euh non, c'est assez compliqué

- si $p \equiv 3 \pmod 4$, alors $a=aa^{\frac{p-1}{2}}=a^{\frac{p+1}{2}}=(a^{\frac{p+1}{4}})^2$.

gebrane

Pour la réciproque , si \( x \) n'est pas un résidu quadratique, il faut démontrer que son ordre dans \( (\mathbb{Z}/p\mathbb{Z})^* \) est exactement \( p - 1 \). (edit avec $p$ est une nombre  premier de Fermat pour éviter toute confusion ))

stfj

Ici, un document avec plusieurs exemples, mettant en place sur des exemples le vocabulaire de racine primitive de l'unité.

stfj

Comme $p=2^{2^n}+1$, $p-1=2^{2^n}$. Et $\frac{p-1}{2}=2^{2^n-1}$. Si l'ordre d'un non-carré $a$ n'était pas $p-1$, ce serait un diviseur de $p-1$, ie de la forme $2^{q}$. Le problème est qu'on aurait alors $a^{\frac{p-1}{2}}=1$ contrairement à ce que nous avons vu. Nous savons en effet que $$a^{\frac{p-1}{2}}=-1$$

____________________________

Voyons par exemple le cas $p=17=2^4+1$. Les carrés sont $1,4,9,16,8,2,15,13$. Si l'ordre de $3$ n'était pas $16$, ce serait $8,4,2$ ou $1$. Mais alors, $3^8$ serait égal à $1$ dans $\Z/17\Z$. Or, on sait que $$3^8=-1$$ce qu'il est par ailleurs aisé de vérifier.

stfj

Théorème : $\forall n\in \mathbb N^*, \,F_n \text{ premier }\implies 3^{\frac{F_n-1}{2}}\equiv -1\mod F_n$

__________________

Soit $F_n $ un nombre premier. Alors, d'après la loi de réciprocrité quadratique, le symbole de Legendre $$\left( \frac{3}{F_n} \right)=\left( \frac{F_n} {3}\right)=-1$$ puisque $2=-1,\,1^2=1$ et $2^2=1$ dans $\Z/3\Z$

Autrement dit $3$ n'est pas un carré de $\Z/F_n\Z$. Et donc $$3^{\frac{F_n-1}{2}}=-1.\square$$Ceci permet déjà de justifier que $F_5$ n'est pas premier, comme vu plus haut avec l'outil sagemath fourni par @Math Coss .

gebrane

stfj a dit :

 Le problème est qu'on aurait alors $a^{\frac{p-1}{2}}=1$ 
Tu n'expliques pas pourquoi ! il y a une petite finesse

stfj

L'exemple que je fournis juste après me paraît suffisant pour éviter de rentrer dans le détail. C'est de l'arithmétique : on manipule de vrais nombres entiers; le but n'est pas la logique, n'est-ce pas ?

Je suggèrerais plutôt si l'exemple de $17$ ne satisfait pas, de considérer $p=F_3=2^8+1$. Quels sont les diviseurs de $2^8$?

gai requin

@Julia Paule : Tu cherches $\alpha$ tel que $a=a^{2\alpha}$ donc si $a$ est d'ordre $\frac{p-1}2$, il vient $\frac{p-1}2$ divise $2\alpha-1$ ce qui est impossible quand $p=1\bmod 4$.
On peut s'en sortir en considérant un générateur $x$ du groupe cyclique $\mathbb F_p^{\times}$.
Soit donc $a$ tel que $a^{\frac{p-1}2}=1$ et $\beta$ tel que $a=x^{\beta}$.
On a $x^{\frac{p-1}2\beta}=1$ donc $p-1$ divise $\frac{p-1}2\beta$ donc $\beta$ est pair donc $a$ est un carré.

gebrane

L'exemple ne fait pas la démonstration !
Comme tu l'as remarqué l'ordre de $a$ divise $p-1=2^m$ (où je pose $m=2^n$)  donc l'ordre de $a$ doit être de la forme $2^q$ avec $q\in\{1,2\cdots m\}$ , le but est de démontrer que $q=m$, vois-tu comment ?

stfj

Oublions toutes ces lettres et faisons la démonstration sur l'exemple suffisamment général de 257. Les diviseurs de 256 sont outre 256, 128,64,32,...1. Si l'ordre d'un non-carré $a$ est 64, 32, ...1, le problème est qu'alors on aurait $a^{128}=1$. Or on sait que $a^{128}=-1.\square$

Pour moi, le but de l'arithmétique est de faire de ... l'arithmétique. Il y a plus d'arithmétique dans la découverte de Landry en 1880 du fait que $$2^{2^6}+1=174\,177\times 67\,280\,421\,310\,721$$que dans de nombreux manuels du secondaire.

gebrane

Je ne suis intervenu que pour t'aider, je t'explique  ce point et je te  laisse travailler l'arithmétique à ta façon 
Pa l'absurde supposons que $q<m$ alors $m-1-q\in\mathbb N$ et donc $2^{m-1-q}\in\mathbb N$ on a $x^{2^q}=1 (\mod p)$ on élève à la puissance entière $2^{m-1-q}$ d'où 
$$(x^{2^q})^{2^{m-1-q}}=x^{\frac{2^m}{2}}=x^{\frac{p-1}2}=1 (\mod p)$$ contradiction 

stfj

Pourquoi  "on a $x^{2^q}=1 (\mod p)$ "?

gebrane

 $x$ est l'entier $a$

stfj

Dans $\Z/257\Z$, l'ordre de $a$ divise $256=2^{2^3}=2^8$ donc l'ordre de $a$ doit être de la forme $2^q$, avec $q\in \{1,2,...,8\}$. Le but est de démontrer que $q=8$.

____________________________________________

Par l'absurde supposons que $q<8$. Alors $8-1-q\in \mathbb N$ on élève à la puissance entière $2^{7-q} $ d'où $$(a^{2^q})^{2^{7-q}}=a^{2^7}=a^{128}=1$$contradiction

_________________________________

J'ai repris tes écrits en remplaçant $m$ par $8$. On retrouve mon raisonnement : c'est en cela que je parle d' "exemple suffisamment général". Il suffit ensuite de remplacer $8$ par $m$ si on le juge utile.

gebrane

Comme tu veux 

stfj

Je ne cherche pas à avoir raison. Je me demande ce qu'il y a de plus ICI dans une démonstration avec des lettres, plutôt que dans l'examen de cas particuliers où l'on comprend ce qui se passe.

_________________

Reste à démontrer la réciproque de

Théorème : $\forall n\in \mathbb N^*, \,F_n \text{ premier }\implies 3^{\frac{F_n-1}{2}}\equiv -1\mod F_n$

________________________

La démonstration proposée par wikipedia devient alors claire. Mais dieu, que c'est mal écrit. Pas d'économie de papier !, serait-on tenté de dire.

JLapin

stfj a dit :

Je ne cherche pas à avoir raison. Je me demande ce qu'il y a de plus ICI dans une démonstration avec des lettres, plutôt que dans l'examen de cas particuliers où l'on comprend ce qui se passe.

Toi tu t'en fiches, mais un étudiant qui veut des points à son partiel aura intérêt à rédiger des démonstrations à la portée générale.

stfj

sagemath via

_________________

def F(n): return 2^(2^n)+1
power_(mod(3,(F(7)-1)//2,F(7)) +1)%F(7)

___________________

fournit $110780954395540516579111562860048860421$ et

nous ramène tranquillement en 1905 où Morehead & Western prouvent que $F_7$ est composé.

_____________________________________________________

Un petit saut d'une année, toujours sagemath fournit $5864545399742183862578018016183410025465491904722516203269973267547486512820\neq 0$

_________________________________________

Nous parvenons même en 1952 avec Robinson, ou plutôt sagemath à prouver que $F_9$ et $F_{10}$ sont également composés.

____________________________

$F_{11},F_{12}$ ne nous résistent pas davantage. Pas plus que $F_{13}$ et le résultat obtenu par Paxson en 1960. Puis Selfridge & Hurwitz en 1961 avec $F_{14}$.

___________________

Il est à noter que le compte-rendu de Pépin avait comme commissaires Charles Hermite et Pierre Bonnet. Un pépin garanti digeste, n'est-ce pas, @Calembour ?

Julia Paule

gai requin a dit :

@Julia Paule : Tu cherches $\alpha$ tel que $a=a^{2\alpha}$ donc si $a$ est d'ordre $\frac{p-1}2$, il vient $\frac{p-1}2$ divise $2\alpha-1$ ce qui est impossible quand $p=1\bmod 4$.

Merci. Mais si $p \equiv 5 \pmod 8$, et $a$ d'ordre $\frac{p-1}{4}$ (ce qu'on peut envisager car $a^{\frac{p-1}{2}}=1 \Leftrightarrow a^{\frac{p-1}{4}}=\pm1$), alors $a=(a^{\frac{p+3}{8}})^2$.

En utilisant un générateur $x$ de $\mathbb F_p^*$, alors $x$ n'est pas un carré (sinon l'ordre de $x$ divise $\frac{p-1}{2}$), alors les carrés de $\mathbb F_p^*$ sont les $x^{2k}$, et les non carrés sont les $x^{2k+1}$, pour $1 \leq k \leq \frac{p-1}{2}$, ce qui fournit une démonstration pour l'égalité du nombre de carrés et de non carrés dans $\mathbb F_p^*$.

Cela fournit aussi une démonstration pour la réciproque du critère d' Euler : si $a$ est non carré, alors $a$ s'écrit $a=x^{2k+1}$ et $a^{\frac{p-1}{2}}=(x^{2k+1})^\frac{p-1}{2}=-1$.

gai requin

Oui, mais il existe toujours un élément d'ordre $\frac{p-1}2$.

Julia Paule

Je n'ai pas dit le contraire. Par exemple, $x^2$ est d'ordre $\frac {p-1}{2}$ pour $x$ générateur de $\mathbb F_p^*$.

Toujours pour $p \equiv 5 \pmod 8$ et $a^{\frac{p-1}{4}}=-1$, on a $a=(2a.(4a)^{\frac{p-5}{8}})^2$.

Le cas le moins simple est pour $p \equiv 1 \pmod 8$.