Annuler
connectez vous
arithmétique en post-bac
- Arithmétique dans Z - supérieur
- Exercice : le petit théorème de Fermat
- Équations différentielles : un Cours complet avec des exemples
- Généralités sur les matrices, applications linéaires, changement de base, rang d'une matrice - supérieur
- Ensemble et application Partie II
- Un best-of d'exos de probabilités (après le bac)
- Espaces vectoriels et Applications linéaires - supérieur
Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Autre ArithmétiqueTopics traitant de arithmétique [tout]Lister tous les topics de mathématiques
Niveau autre
arithmetique dans Z/nZ : racines primitives modulo p
Posté par Mihawk
bonsoir,
j'ai un exercice d'arithmetique que je n'arrive pas a resoudre. Il concernce les racines primitives modulo p.
Voici l'enonce : toute aide est la bienvenue.
Citation :
Soit n > 1 tel que p = 2n + 1 soit premier. On va démontrer par l'absurde que 3 est une racine primitive modulo p.
1) On suppose que 3 n'est pas une racine primitive modulo p. Montrer que 3 est un carré modulo p.
2) Montrer qu'il existe a
tel que a² 
-3 [p] (indication : utiliser le fait que p est de type 1)
3) Trouver u tel que 2u a - 1 [p]
4) Montrer que u est d'ordre 3 dans Up.
5) conclure.
Soit n > 1 tel que p = 2n + 1 soit premier. On va démontrer par l'absurde que 3 est une racine primitive modulo p.
1) On suppose que 3 n'est pas une racine primitive modulo p. Montrer que 3 est un carré modulo p.
2) Montrer qu'il existe a
tel que a² -3 [p] (indication : utiliser le fait que p est de type 1)
3) Trouver u tel que 2u
a - 1 [p]
4) Montrer que u est d'ordre 3 dans Up.
5) conclure.
je rappelle que k est une racine primitive modulo p signifie : kn = 1 et que
m divisant n, m 
n, km 1
p un premier de type 1 signifie que p est congru a 1 modulo 4
Up est le groupe des unites de
/p, c'est a dire les inversibles de /p
j'y ai passé trois heures dessus hier et j'ai remis ca aujourd'hui pour une bonne heure et j'avoue que je seche lamentablement...meme pas un debut de piste...
alors si vous en avez : "a vot' bon coeur m'sieur dames" j'en ai bien besoin ^^;
merci d'avance.
Mihawk
Bonjour
1) Le groupe Up est cyclique d'ordre 2n. Soit g un générateur. Les autres générateurs sont les g2k+1 (car 2k+1 est premier avec 2n). Si 3 n'est pas générateur, il est de la forme g2k, c'est donc un carré.
2) En principe on sait que -1 est un carré dans Up si et seulement si p-1 est divisible par 4. Donc ici 3 et -1 sont tous deux des carrés, donc -3=a2 (mod p)
3) 2 étant inversible dans Z/pZ, on multiplie a-1 par son inverse et on trouve u.
4) 8u3=a3-3a2+3a-1=a(-3)+9+3a-1
et 8 est inversible!
bonjour Camélia,
désolé de repondre aussi tard, j'etais sur autre chose.
pour la question 1 tu dis que si on prends un générateur g alors les autres générateurs sont les g2k+1 car 2k+1 est premier avec 2n.
je ne comprends pas pourquoi... Pour moi tout ce qu'on peut dire c'est qu'il y a générateurs. Je ne vois pourquoi ceux la seraient les g2k+1...
peux tu m'expliquer?
De plus tu supposes que 3 n'est pas générateur. une racine primitive est un générateur du groupe cyclique mais un générateur est-il forcément une racine primitive? ie y a t'il équivalence entre le fait d'etre générateur et le fait d'être une racine primitive ?
je viens de parcourir mon cours et tout ce que j'ai trouvé c'est racine primitive => générateur...
pour la deuxieme question, je ne savais pas que -1 est un carré dans Up si et seulement si p-1 est divisible par 4.
mais j'ai fait comme ca :
on a (-1)² = 1. Donc -1 n'est pas une racine primitive modulo p (car 2 | 2n qui ets l'ordre du groupe).
Alors par la question 1 : -1 est de la forme g2k et don il existe un nombre a tel que a² = -1.
-3 = -1 * 3 = g2k * g2m = g2(k+m)
alors a = gk+m où g est un générateur.
mais j'ai l'impression que quelque chose cloche quelquepart... et je sias pas où ><
Qu'en penses tu?
Rebonjour
Ca peut marcher comme ça. Mais comme dans l'énoncé il était question de p "de type 1" (en fait je n'ai jamais entendu ce terme), je pensais que tu étais au courant.
En fait comme c'est bon à savoir:
Si -1=a2, alors a est d'ordre 4, donc 4 divise p-1.
Si 4 divise p-1, il existe un élément a d'ordre 4, donc a2 est d'ordre 2 et vérifie (a2)2=1, donc a2=-1.
ok merci.
et pour l'équivalence entre le fait d'etre générateur et le fait d'être une racine primitive... c'est vrai ca?
parce que si j'ai bien compris c'est ce que tu utilises pour la question 1 non?
ca oui...
ce qui me pose probleme c'est : "tous les générateurs sont ils des racines primitives?"
l'autre implication quoi ^^
je vois pas de contre exemple mais je l'ai pas trouver dans mon cours... et je me dis que le prof nous l'aurait dit si c'etait vrai... (en meme tps on a pas fini le cours ^^; )
ok merci 
Plus que deux exos a faire ^^;
mais la j'etais moins bloqué ^^
Si j'ai un probleme je creerai un autre topic.
Merci beaucoup pour tes explications patientes