Exercice corrigé Ancien programme

ordre d'un entier modulo p

Soit p un nombre premier et a un entier non divisible par p.

On considère l'ensemble

1. Démontrer que E n'est pas vide.

2. Soit h le plus petit entier appartenant à E : on dit que h est l'ordre de a modulo n.

Soit Démontrer que h divise n.

3. En déduire que h divise

4. Exemples : déterminer les ordres de 2, 3, 5 et 12 modulo 13.

Les deux exercices suivants utilisent les résultats démontrés dans l'exercice précédent. Soit p un nombre premier et a un entier non divisible par p :

Il existe un plus petit entier h tel que (modulo p).

Si n est un autre entier supérieur à 1 tel que (modulo p), alors h divise n (donc h divise d'après le petit théorème de Fermat).

1. Puisque p est premier et que a n'est pas divisible par p, alors d'après

le petit théorème de Fermat, (modulo p), donc .

Donc.

2. On effectue la division euclidienne de n par h :

il existe avectel que .

car, soit (modulo p),

donc (modulo p) car .

Si, alors , ce qui est absurde car h est le plus petit entier appartenant

à E, donc nécessairement et .

Si , alors n est divisible par h.

3. Comme (question 1.) alors h divise (question 2.).

4. D'après le petit théorème de Fermat :

(modulo 13), donc les ordres modulo 13 de 2, 3, 5, 12 sont des diviseurs positifs de 12 soit 1, 2, 3, 4, 6 ou 12.

2, , et ne sont pas congrus à 1 modulo 13, donc l'ordre de 2 modulo 13 est 12.

3 et ne sont pas congrus à 1 modulo 13 et (modulo 13), donc l'ordre de 3 modulo 13 est 3.

5, et ne sont pas congrus à 1 modulo 13 et(modulo 13), donc l'ordre de 5 modulo 13 est 4.

(modulo 13) et (modulo 13), donc l'ordre de 12 modulo 13 est 2.

Accéder à tous les contenus
dès 6,79€/mois

  • Les dernières annales corrigées et expliquées
  • Des fiches de cours et cours vidéo/audio
  • Des conseils et méthodes pour réussir ses examens
  • Pas de publicités
S'abonner