Un test de primalité

[ludo60]

Bonjour à tous,

Dans le cadre d'une leçon, j'aimerais exposer un test de primalité que j'ai trouvé dans le gourdon et qui me semble être une bonne application du calcul de la fonction indicatrice d'Euler... Il s'agit du test c p 36 de la dernière édition.
Il affirme que:

Soit p>2 est premier et soit h est un entier tel que .
On pose . Si et si n'est pas congrus à 1 modulo n, alors n est premier.

Je cree cette discussion pour les questions que je vais surement avoir concernant cette démonstration. Et ça commence mal: la preuve débute ainsi: soit m l'ordre de la classe de 2 dans le groupe des inversibles de . Pourquoi la classe de 2 serait nécessairement un inversible dans l'anneau Z/nZ ? Merci d'avance !

[ludo60]

Je suis également intéressé pour toute information concernant ce test dont je n'ai jamais entendu parlé.

[ludo60]

Je penses avoir compris mais j'aimerais confirmation: par hypothèse, . Cela signifie que la classe de est l'inverse de la classe de 2 dans Z/nZ ?

[Elias]

Salut,

c'est bien ça. Il faut aussi dire que n-2>0, ce qui est évident puisque p>2 et h>=1 donc hp^2 >4 et donc n >5.

[ludo60]

Super, merci !

[ludo60]

Je suis presque à la fin de la preuve. Il y a une étape que je ne vois pas.
On a prouvé l'existence de deux entiers, et tels que:

. De cela, le Gourdon déduit plusieurs choses dont une que je ne comprends pas, à savoir que .

[Elias]

Je n'ai pas le Gourdon sous les yeux mais tu es sûr que c'est une déduction ? Car h <= p-1 faisait parti des hypotheses de départ (relis ton 1er message)

[ludo60]

Oups !Je suis trop bête ! Non, il déduit plusieurs choses sans préciser... J'avais oublié cette hypothèse, trop pris dans la logique des enchaînements... Encore merci ^^

[Ben314]

Salut,
C'est plus un problème de "vocabulaire" que réellement de maths., mais à mon avis, si expose un truc pareil, je pense pas qu'il faille appeler ça un "test de primalité" :
A mon sens un "test de primalité", tu lui donne à manger un (grand) entier relativement quelconque et il te répond (plus ou moins) s'il est premier (en fait soit avec une certaine proba, soit une certitude qu'il ne l'est pas, soit rarement une certitude qu'il l'est).
Or, là, des entiers n tels que n-1 soit divisible par le carré d'un premier p et en plus tel que le quotient de la division soit <p, ben le moins qu'on puisse dire, c'est que c'est pas franchement fréquent.
Donc si tu prend un (grand) entier au pif, il est quasi certain que ton "test" ne va pas s'appliquer.

Là où il peut éventuellement être utile, c'est plutôt dans l'autre sens, c'est à dire pour fabriquer des nombres premiers en partant de premiers déjà connus : tu part de p premier (grand) connu, tu calcule n=1+h.p^2 pour un certain h plus ou moins au pif et ton test permet de voir si ce n là est ou pas premier.

[ludo60]

Oui, je comprends bien ta remarque. D'ailleurs, M.Gourdon que cette propriété permet d'obtenir des nombres premiers ayant une forme particulière et en 1951, il fut utilisé pour montrer que le nombre 1+190p² avec est premier.