Inscription / Connexion Nouveau Sujet
Niveau Maths sup
Partager :

Ordre et racines primitives modulo p

Posté par
LucyHeartfilia
08-11-12 à 20:06

              Ordre et racines primitives modulo p

Dans tout le problème, p désigne un nombre premier.

Ordre d'un entier modulo p
Soit x. On appelle ordre de x modulo p le plus petit entier i 1 tel que xi 1 (p)
(s'il existe).

1. Quels sont les entiers relatifs qui possèdent un ordre modulo p ? Montrer que leur
ordre est inférieur ou égal à p- 1.
2. Déterminer l'ordre modulo 7 de tous les entiers relatifs (sous réserve d'existence).
3. Soit x un entier d'ordre r modulo p.
a. Montrer que la suite (xk)k est périodique modulo p et déterminer sa plus petite période.
b. Quels sont les entiers k tels que xk 1 (p) ?
c. Montrer que pour tous k,l, on a xk  xl (p) si et seulement si k l (r).
d. Déterminer, pour tout k , l'ordre de xk modulo p (en fonction de k et r).
Indication. On pourra commencer par examiner les entiers k premiers avec r.

4. a. On note (/p)* = /p \ {0}.
Vérifier que ((/p)*,)est un groupe
et que l'application
:  ((/p)*)
      (k xk)
est un morphisme de groupes (l'entier x étant toujours supposé d'ordre r modulo p).

b. Déterminer le noyau de ce morphisme puis retrouver très simplement à l'aide de les résultats des questions 3.b et 3.c.


Racines primitives modulo p

Un entier x est appelé une racine primitive modulo p s'il est d'ordre p-1 modulo p
(d'après la question 1, c'est la plus grande valeur envisageable pour l'ordre).

5. Exemples. Montrer que 2 est une racine primitive modulo 11. Déterminer toutes les
racines primitives modulo 7.

6. Montrer qu'un entier x est une racine primitive modulo p si et seulement si l'on a
(/p)*= {x,x2, ... , xp-1}

7. Un autre exemple.
a. Montrer que 2 est une racine primitive modulo 197 en efectuant le moins de
calcul possible (on indiquera les calculs efectués).
Indication. Utiliser la décomposition en facteurs premiers de p-1 pour chercher l'ordre
de 2 modulo p = 197.

b. Résoudre l'équation x5 1 (197).
c. Résoudre l'équation x7 1 (197).
On cherchera des méthodes évitant d'efectuer 197 essais !
d. Soit n 2 N. Combien l'équation xn 1 (197) possède-t-elle de solutions dans
l'intervalle [0; 196] ?


Nombre de racines d'un polynôme modulo p

Soit f : x a0 + a1x + ... + anxn un polynôme à coecients entiers (a0;...; an ),
de degré n, tel que annon 0 (p). Dans tout ce qui suit, la variable x sera supposée
appartenir à .
8. Comparer f(x) et f(x + p) modulo p.
On dit qu'un entier x0 est racine de f modulo p si l'on a f(x0) 0 (p). Le nombre de
racines de f modulo p est le nombre d'entiers de l'intervalle [0; p- 1] qui sont racines
de f modulo p.

9. a. Soit x0 une racine de f modulo p. Montrer qu'il existe un polynôme g à coe-
cients entiers tel que pour tout x ,
f(x) (x - x0)g(x) (p):
b. Montrer que f possède au plus n racines modulo p.

10. Application. Montrer que pour tout x , on a
xp-1 - 1 (x - 1)(x - 2)...(x - p + 1) (p):
En déduire une preuve du théorème de Wilson : (p - 1)! -1 (p).

Posté par
LucyHeartfilia
re : Ordre et racines primitives modulo p 08-11-12 à 20:08

Bonjour à tous, j'ai ce dm à faire et je bloque sur la question 3\d

Est-ce que quelqu'un pourrait m'aider ?

Merci d'avance

Posté par
-alison-
re : Ordre et racines primitives modulo p 08-11-12 à 20:40

Salut ! T'as réussi la 7 toi ?

Posté par
-alison-
re : Ordre et racines primitives modulo p 08-11-12 à 20:56

Pour la 3b) t'a mis quoi ? Est ce que tu as trouvé que k est multiple de i ?

Posté par
Galileo Galilei
re : Ordre et racines primitives modulo p 08-11-12 à 21:51

Bonsoir,
Sauf erreur de ma part,

pour la 3d, il faut utiliser l'indication (pensez au théorème de Bezout!) et conclure en utilisant la question 3c) (qui se démontrait elle même avec la question 3)b)qui utilisait 3)a) ... d'où l'intérêt de faire des sous-questions !)

pour la 3)b), k est effectivement multiple de r (dans la 3a, tu as du faire une division euclidienne par r pour montrer que c'est non seulement une période, mais c'est surtout la plus petite ! du coup le k est forcément congru à zéro modulo r pour la 3)b), tu vois pourquoi?)

Je n'ai pas d'idée particulière pour la 7) comme ça. J'attends vos réponses avant de m'y attaquer sérieusement. Essayez de donner les grandes lignes de ce que vous avez fait pour vérifier que tout va bien jusque là.

Posté par
Galileo Galilei
re : Ordre et racines primitives modulo p 08-11-12 à 22:03

Pardon, il n'est pas nécessaire de faire une division eucilidienne pour la 3)a, mais pour les 3)b et 3)c) je pense qu'on n'y échappe pas.

Posté par
Galileo Galilei
re : Ordre et racines primitives modulo p 08-11-12 à 22:20

Décidément... pour la 3)d) pas la peine d'utiliser le théorème de Bezout: On cherche u tel que (x^k)^u=1[p]. 1er cas : r et k sont premiers entre eux or d'après 3)c), r|ku (pourquoi?)... que dire avec l'indication et Gauss?

2e cas: on fait la division euclidienne de k par r, et on se ramène au 1er cas.

Posté par
-alison-
re : Ordre et racines primitives modulo p 08-11-12 à 22:54

Bonjour Galileo Galilei,
Pour la 3a) est ce que ça suffit si on fait : x^(k+r)=x^k*x^r(p)=x^k(p) (car x^r=1(p)) ?
Pour la 3b) Est ce que cette démonstration est bonne ? :
Par l'absurde on suppose que r ne divise pas k. Soit r=qk+s la division euclidienne de r par k (0<r<k-1).
Donc : 1=x^r(p)=(x^k)^q*x^r(p)=x^r(p), ce qui contredit le caractère minimal de r.
Pour la 3c) Je n'arrive pas à faire cette question ...
Pour la 3d)Celle ci non plus ...

Posté par
-alison-
re : Ordre et racines primitives modulo p 08-11-12 à 22:59

Pour la 3c, pour montrer que x^k=x^l(p)=>k=l(r), j'ai supposé par l'absurde que k est différent de l (r)

Donc par exemple, on peut prendre k>l, donc k=l+q (q entier)
Donc : x^(l+q)-x^l=0(p), d'où : x^l(x^q-1)=0(p) donc p divise x^l(x^q-1), mais après je ne sais pas quoi faire ...

Posté par
LucyHeartfilia
re : Ordre et racines primitives modulo p 08-11-12 à 23:08

Merci Galileo Galilei,

Je viens de finir la 3d,
Soit i l'ordre de xk modulo p
(xk)i1(p) donc d'après 3\b r divise ki

On pose d=pgcd(r,k)

Si d=1, d'après Gauss, r divise i donc r=i
Si d > 1, on pose r=r'd et k=k'd alors r' divise ik'
on déduit d'après le cas préscédent i=r' ie  i=r/d

On n'a même pas besoin d'utiliser la 3\c\ en fait ?

Posté par
-alison-
re : Ordre et racines primitives modulo p 08-11-12 à 23:11

Pour la 3d),

1er cas : r et k premiers entre eux :
On a r|ku car (r^k)û=1(p)=x^0(p) <=> ku=0(r)<=>r|ku => r|u (car k et r premiers entre eux donc on utilise Gauss)
Donc r|u, donc u est multiple de r

2ème cas : r et k ne sont pas premiers entre eux :
On fait la division euclidienne de k par r : k=rq+s (0<=s<r) mais après comment se ramener au premier cas ?

Posté par
-alison-
re : Ordre et racines primitives modulo p 08-11-12 à 23:16

Lucyheartfilia, est ce que tu as fais la suite après ?

Posté par
LucyHeartfilia
re : Ordre et racines primitives modulo p 08-11-12 à 23:21

Oui en tout cas j'essaye

Posté par
-alison-
re : Ordre et racines primitives modulo p 08-11-12 à 23:31

ok moi il me reste que la 7 et la partie facultative , tu l'as faite la 7 ?

Posté par
LucyHeartfilia
re : Ordre et racines primitives modulo p 08-11-12 à 23:42

non je recopie mon brouillon de la partie 1 pour l'instant

Posté par
-alison-
re : Ordre et racines primitives modulo p 08-11-12 à 23:51

Ah ok, comment t'as fait la 3c) toi ?

Posté par
LucyHeartfilia
re : Ordre et racines primitives modulo p 08-11-12 à 23:55

simplement par implication directe et reciproque

Pour la 4b, quand on doit determiner le noyau, je retombe sur la 3b, mais il demande de reprouver la 3b et la 3c après, comment tu as fait ?

Posté par
-alison-
re : Ordre et racines primitives modulo p 08-11-12 à 23:58

ah ok merci Celle la aussi j'ai pas réussi j'ai juste trouvé que le noyau c'était l'ensemble des multiples de r ... t'as trouvé ca aussi ?

Posté par
-alison-
re : Ordre et racines primitives modulo p 09-11-12 à 00:01

pour la 3c) pour montrer que x^k=x^l(p)=>k=l(r), est ce que t'as fait ca ?

Par l'absurde, on suppose que k est différent de l (r)

Donc par exemple, on peut prendre k>l, donc k=l+q (q entier)
Donc : x^(l+q)-x^l=0(p), d'où : x^l(x^q-1)=0(p) donc p divise x^l(x^q-1), mais après t'as fait fait quoi toi ?

Posté par
LucyHeartfilia
re : Ordre et racines primitives modulo p 09-11-12 à 00:16

implication directe:
si xkxl (p)
comme (xk) est périodique modulo p, il existe mtel que k=l+mr
donc kl(p)

Réciproque, si kl(p) etc

Posté par
LucyHeartfilia
re : Ordre et racines primitives modulo p 09-11-12 à 00:17

pardon c'est kl (r)

Posté par
-alison-
re : Ordre et racines primitives modulo p 09-11-12 à 00:30

Merci beaucoup si tu veux je te dis des que je trouve pour la 4b !

Posté par
LucyHeartfilia
re : Ordre et racines primitives modulo p 09-11-12 à 00:59

Bonjour à tous,
j'ai fini la partie 1 mais maintenant j'ai du mal pour la question 6

Si quelqu'un avait la gentillesse de m'aider

Posté par
-alison-
re : Ordre et racines primitives modulo p 09-11-12 à 01:36

Moi j'ai fait ça si tu veux :
On pose E={x,x2, ... , xp-1}
- On suppose E=(Z/pZ)*
D'abord tu montres que x n'est pas congru à 0 modulo p (par l'absurde)
Après par Fermat, x^(p-1) congru à 1 modulo p
Et après tu montre par l'absurde que pour tout k dans [1,p-2], x^(p-2) est non congru à 1 modulo p

Donc après on a x^(p-1)=1(p)

- On suppose x racine primitive modulo p
D'abord tu montres que E={x,x2, ... , xp-1} est inclu dans (Z/pZ)*
Après tu montres que x^n est non congru à 0 modulo p (par l'absurde) et que x^n appartient à Z/pZ (par stabilité comme c'est un groupe)
Et ils ont le même cardinal
Donc après on a E=(Z/pZ)*

T'as fait comment pour la 4b ? J'ai pas réussi ...

Posté par
LucyHeartfilia
re : Ordre et racines primitives modulo p 09-11-12 à 11:36

Merci, j'ai pas fait la 4b non plus,

Tu as reussi la 7 ?

Posté par
-alison-
re : Ordre et racines primitives modulo p 09-11-12 à 12:06

Non il me reste la 4b et la 7, et toi ? t'as fait la 7a) ?

Posté par
-alison-
re : Ordre et racines primitives modulo p 09-11-12 à 12:23

Pour résoudre les 2 équations tu sais comment on fait ? j'y arrive pas ...



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1742 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !