Exercice racines primitives modulo n

[Fleykha]

Bonjour, je fais l'exercice de maths suivant :

n premier, Z/nZ*=Z/nZ privé de {0barre}

1) Montrer qu'un entier x est une racine primitive mod n ssi : (Z/nZ)*={xbarre,xbarre²,...,xbarre(n-1)}
2) Démontrer que 2 est racine primitive mod 197
3) Résoudre x^5=1(197) et x^7=1(197)
4) Combien l'équation suivante possède de solutions dans [0,196] : x^m=1(197) où m appartient à N* ?

Voici ce que j'ai fait :
1) Pour cette question je ne sais pas du tout comment m'y prendre ... J'ai montré avant que l' application f : Z -> (Z/nZ*,*) et qui à k associe (xbarre)^k était un morphisme de groupe (avec x d'ordre r mod n) et j'ai trouvé son noyau aussi
2) J'ai utilisé le petit théorème de fermat mais je ne sais pas si c'est bon parce que dans l'exercice on nous donne l'indication d'utiliser la décomposition en facteurs premiers de n-1 pour chercher l'ordre mod 197
3)Je ne sais pas du tout comment faire, j'ai essayé plein de méthode mais ça ne marche pas ... Auriez vous une idée s'il vous plaît ?
4) je n'y arrive pas non plus ...

Pourriez-vous m'aider s'il vous plaît ?

Merci d'avance :)

[Doraki]

C'est quoi une racine primitive ?

[Anonyme]

Bonjour, Doraki c'est moi Fleykha (parce que j'avais oublié mon mot de passe donc j'ai fait un autre compte)
Une racine primitive est un entier x d'ordre n-1 modulo n, tel que x^(n-1)=1(n) (n premier) et n-1 est le plus petit entier i>=1 tel que x^i=1(n)
J'ai réussi en fait la première question, mais par contre la suite non

Pour la 2) J'ai montré avec fermat que : 2^196=1(197) mais j'ai pas réussi à montrer que 196 était le plus petit entier i supérieur à 1 tel que 2^i=1(197) (j'ai pensé à utiliser la décomposition en facteurs premiers de n-1 pour trouver l'ordre de 2 modulo n=197, mais je n'y arrive pas ...)

[Doraki]

Donc tu sais que l'ordre de 2 divise 196.
196 = 2*2*7*7, donc il reste à vérifier que 2^28 <> 1 mod 197 (sinon l'ordre de 2 diviserait 28) et que 2^98 <> 1 mod 197 (sinon il diviserait 98) (et puisque (2^98)² = 1, 2^98 ne peut valoir que -1 ou 1 donc on devrait trouver -1)

Commence par calculer 2^7 mod 196,
puis calcule 2^14, 2^28, 2^21, 2^49, et enfin 2^98

[Anonyme]

Merci beaucoup pour ta réponse :)
Mais pourquoi l'ordre de 2 divise 196 (par fermat ?) ?

[Doraki]

Oui c'est une conséquence du théorème de Fermat (ou du théorème de Lagrange à propos du sous-groupe de (Z/197Z)* engendré par 2)

Ou même plus simplement : 2^196 * (1*2*3*...*196) = (2*1)*(2*2)*(2*3)*...*(2*196) = 1*2*3*...*196 (puisque la multiplication par 2 ne fait que permuter les éléments du groupe), et donc en simplifiant par 1*2*3*...*196, on en déduit que 2^196 = 1.

L'ordre de 2 dans le groupe ((Z/197Z)*,*) c'est le plus petit entier n tel que 2^n = 1 (mod 197), c'est donc l'entier n pour lequel on a l'équivalence 2^m = 1 <=> m est multiple de n.
On sait que 2^196 = 1. Comme les diviseurs de n sont 1,2,4,7,14,28,49,98,196, il y a a priori 8 ordres possibles.
Par exemple 1 est d'ordre 1 parceque 1^1 = 1, 196 est d'ordre 2 parceque 196^2 = 1 et que 196^1 est différent de 1, etc.
Pour montrer que 2 est d'ordre 196 il suffit de montrer que 2^98 et 2^28 sont différents de 1.

[Anonyme]

Ah oui merci ta reponse m a beaucoup aidee ,
Pr la question suivante , pour resoudre l'equation je ne vois pas quelle methode utiliser , je voulais utiliser la question 1) ...

[Anonyme]

Merci pour ta reponse qui m a beaucoup aidé , pour la resolution de l'equation je ne vois pas comment la resoudre par contre ... Je voulais utiliser la question 1) ...

[Doraki]

Oui il faut utiliser les questions 1 et 2. Maintenant que tu as vérifié que 2 est une racine primitive de Z/197Z*,
ça implique que le sous-groupe cyclique de Z/197Z* engendré par 2 est Z/197Z* lui-même :
Z/197Z* = {2^0, 2^1, 2^2, 2^3, ...., 2^195}, et donc tout élément de Z/197Z* s'écrit de manière unique sous la forme 2^k avec 0 <= k < 196.

En cherchant les solutions de x^5 = 1 et de x^7 = 1 sous cette forme, ce n'est pas difficile de trouver tous les k qui donnent les solutions.