exo arithmétique

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: alex26

Bonjour, je suis bloqué sur cet exercice. Pourriez vous m'aider?

Soit n un entier de la forme n = h*2^m + 1 avec m et h entiers tels que m> 2 et 0 <h<2m.
Soit p>3 un nombre premier tel que n n’est pas un résidu quadratique modulo p.
On veut montrer que n est premier si et seulement si p^((n-1)/2)=-1 mod n.
a) Montrer que, si n est premier, cette congruence est bien vérifiée.(cette question j'ai trouvé)
b) Soit q un nombre premier divisant n.
En étudiant l’ordre de la classe de p dans (Z/qZ,×), montrer que q est de la forme q =
h′*2^m+1. (là je bloque)
c) Conclure.


Posted by: abcd22

Pour faire la question b) on suppose que p^{\frac{n-1}{2}} \equiv -1 \pmod{n} ? D'après la conclusion je dirais oui, mais c'est pas écrit dans la question.


Posted by: alex26

Oui, on suppose p^((n-1)/2)=-1 mod n. C'est la réciproque qu'on veut démontrer


Posted by: abcd22

Dans ce cas, on a p^{\frac{n-1}{2}} + 1 \in n\mathbb{Z} \subset q\mathbb{Z} puisque q divise n, donc p^{\frac{n-1}{2}} \equiv -1 \pmod{q}, et avec ça on a des informations sur l'ordre de p dans \( \mathbb{Z}/q\mathbb{Z} \)^\times, et on sait aussi que cet ordre divise q-1...


Posted by: yos

Citation:
Posté par abcd22
Dans ce cas, on a p^{\frac{n-1}{2}} + 1 \in n\mathbb{Z} \subset q\mathbb{Z} puisque q divise n, donc p^{\frac{n-1}{2}} \equiv -1 \pmod{q}, et avec ça on a des informations sur l'ordre de p dans \( \mathbb{Z}/q\mathbb{Z} \)^\times, et on sait aussi que cet ordre divise q-1...

donc l'ordre est un entier r de la forme h'2^{m'} et qui divise q-1. Si on suppose h' impair et m'<m, on aurait p^{\frac{n-1}{2}}\equiv 1 \pmod n, alors que cette congruence est -1.
Question : où est ce qu'on utilise (\frac{n}{p})=-1 ?


Posted by: abcd22

Citation:
Posté par yos
Question : où est ce qu'on utilise (\frac{n}{p})=-1 ?

Pour la question a), non ?


Posted by: alex26

Yos, je suis ok. Donc m'>=m. Comment mq m'=m? (car rien ne prouve que m'=<m, ce qui permetrait de conclure)


Posted by: yos

Citation:
Posté par alex26
Yos, je suis ok. Donc m'>=m. Comment mq m'=m? (car rien ne prouve que m'=<m, ce qui permetrait de conclure)

Ben on demande pas que h soit impair non? Donc on peut lui fourguer les "2" en trop?


Posted by: alex26

Ok tu as raison, je croyais que h était sous entendu impair. Merci


Posted by: yos

Citation:
Posté par abcd22
Pour la question a), non ?

Pour cette question, j'ai dit que d'après Fermat, p^((n-1)/2) est racine de X²-1 dans Fp et comme ce polynôme n'a que 1 et -1 comme racines, on a p^((n-1)/2) =1 ou -1 modulo p. Pourquoi c'est pas 1?


Posted by: abcd22

J'ai utilisé la loi de réciprocité quadratique : \( \frac{n}{p} \) \( \frac{p}{n} \) = (-1)^{\frac{(n-1)(p-1)}{4}} = 1 car l'hypothèse m > 2 assure que n-1 est divisible par 8 donc \frac{(n-1)(p-1)}{4} est pair. Ca suppose que la réciprocité quadratique ait été vue avant, il y a peut-être une démonstration qui ne l'utilise pas, mais c'est la première chose à laquelle j'ai pensé.


Posted by: yos

Oui merci.
Ce doit être la bonne méthode.










-