Discussion:Théorème de Proth

La condition "a non résidu de p"

Je ne suis pas un spécialiste des tests de primalité, donc la réponse à ma question se trouve peut-être dans la littérature. Je suis intrigué par la condition "a non résidu de p" ajoutée par Proth à son théorème III. Effectivement, si on trouve un a tel que $a^{(p-1)/2}\equiv -1{\pmod {p}}$, alors, d'après le théorème de Proth, p sera premier, donc a ne sera pas congru à un carré modulo p. On dirait donc que le raisonnement de Proth est le suivant : si on trouve un bon a, il ne sera pas congru à un carré modulo p, donc il ne faut pas perdre son temps à essayer les a qui sont congrus à des carrés modulo p. Le problème, me semble-t-il, c'est que, tant qu'on ne sait pas si p est premier, il n'est pas si vite fait de savoir si un nombre a donné est congru à un carré modulo p. Il me semble cependant qu'on peut améliorer l'idée. Si on trouve un bon a, p sera premier, donc le symbole de Jacobi $({\frac {a}{p}})$, défini même si p n'est pas premier, sera égal à - 1. Donc il ne faut pas perdre son temps à essayer les a pour lesquels $({\frac {a}{p}})=1$. Ceci est peut-être bien intéressant, car le symbole de Jacobi se calcule assez vite grâce à la loi de réciprocité quadratique de Jacobi (sans qu'il soit nécessaire de connaître la décomposition de p en facteurs premiers). Je me demande donc si Proth, quand il parlait d'un a non résidu de p n'entendait pas un a tel que le symbole de Jacobi $({\frac {a}{p}})$ soit égal à -1. Il serait intéressant de savoir si, à l'époque, il était habituel de s'exprimer ainsi. Marvoir (discuter) 18 janvier 2016 à 10:02 (CET)

Au risque d'être agaçant, je reviens sur cette question. Il y a deux bonnes raisons de se limiter aux nombres a tels que le symbole de Jacobi $({\frac {a}{p}})$ soit égal à -1. Tout d'abord, comme dit dans l'article, il est plus facile de tester la condition $({\frac {a}{p}})=-1$ que la condition « a n'est pas congru à un carré modulo p ». Il y a une seconde bonne raison, c'est que si $({\frac {a}{p}})=1$, même si a n'est pas congru à un carré modulo p, on sait d'avance que

$a^{(p-1/2)}\not \equiv -1{\pmod {p}}.$

En effet, si on avait $a^{(p-1/2}\equiv -1{\pmod {p}},$ alors, d'après le théorème de Proth, p serait premier, donc la relation $a^{(p-1/2}\equiv -1{\pmod {p}}$ entraînerait $({\frac {a}{p}})=-1$, contradiction.

Par exemple, supposons qu'on cherche à savoir si 33 est premier. (C'est un nombre de Proth.) Le nombre a = 2 n'est pas congru à un carré modulo 33 (c'est clair si on connaît la décomposition de 33, puisque 2 n'est pas congru à un carré modulo 3), mais il ne sert à rien de l'essayer, car $({\frac {2}{33}})=1$, ce qui résulte immédiatement du fait que si n est un nombre naturel (premier ou non) congru à 1 modulo 8, alors $({\frac {2}{n}})=1$.

J'ai l'impression que Proth, quand il disait « a non résidu de p », voulait dire que le symbole de Jacobi $({\frac {a}{p}})$ est égal à -1, mais cela demanderait une petite enquête. Marvoir (discuter) 19 janvier 2016 à 12:50 (CET)

À mon avis, la meilleure façon d'énoncer le théorème serait celle-ci (en deux assertions) :

« Soit p un nombre de Proth. Pour que p soit premier, (il faut et) il suffit qu'il existe un entier a tel que a ^(p–1)/2 ≡ –1 (mod p). Un nombre a tel que le symbole de Jacobi $({\frac {a}{p}})$ soit égal à 1 ne satisfait pas à cette congruence (et ne doit donc pas être essayé). »

La seconde assertion ne me semble pas triviale, puisqu'elle se déduit de la première. Marvoir (discuter) 19 janvier 2016 à 14:44 (CET)

Un drôle de théorème de Proth

Dans le tome 83 (1876) des Comptes rendus de l'Académie des Sciences (voir Gallica), p. 1288, il y a une note de F. Proth intitulée « Enoncés de divers théorèmes sur les nombres », où on lit : « Si P est premier, le nombre (2^P - 2) est divisible par P; mais non par P², ni P³ ». Il y a peut-être quelque chose qui m'échappe, mais après avoir démontré qu'un nombre n'est pas divisible par P², je ne m'inquiéterais pas de savoir s'il est divisible par P³. Et si par (2^P - 2), Proth entend 2^P - 2, son énoncé est faux, puisqu'il existe bien des nombres premiers de Wieferich... Marvoir (discuter) 19 janvier 2016 à 16:41 (CET)