|
||||||||||||||||||||||||||||||||||||||||
|
ORDRE MULTIPLICATIF RACINE PRIMITIVE Notion
de la théorie des nombres faisant intervenir la congruence des puissances d'un
nombre modulo un autre. Avant
de partir vers plus d'abstraction, il est utile de bien comprendre ces deux
notions à partir d'exemples. |
Anglais:
multiplicative order / primitive root
Rappels
|
Nombres premiers entre eux:
aucun facteur commun – Notés (a, b) = 1 Indicatrice
d'Euler (ou totient): quantité de premiers avec m et inférieurs à m –
Notée Congruence de a modulo
m: reste de la division de a par m; on dit résidu et on note:
|
|
de 2026 = 3,
5, 7, 17, 27, 29, 31, 33, 37, 39, …, 363, 365,
369, …, 2021, 2023. |
Exemple pour 365:
Les puissances de 365 modulo 2026 parcourent exactement les 1012 entiers
compris entre 1 et 2025 qui sont premiers avec 2026, c’est-à-dire
les entiers impairs non multiples de 1013, avant de revenir à 1. Autrement
dit, 365 engendre tout le groupe multiplicatif modulo 2026. Le
nombre 365 a été choisi en rapport avec l'année 2026 et son nombre de
jours. Métaphore Pensons à une horloge de 1012 positions :
certains nombres avancent par petits pas et retombent vite sur 1, Le nombre 365
avance avec un pas particulier qui
l’oblige à passer par toutes
les positions avant de revenir au point de départ. Plus petites racines primitives Le
nombre 2026 possède 440 racines primitives dont les dix plus petites sont
données. Entre
2020 et 2023, seuls les nombres: 2003, 2011, 2018, 2019, 2026, 2027, 2029 ont
des racines primitives. |
|
Toutes
les racines primitives des nombres de 3 à 100
|
3 [2] 4 [3] 5 [2, 3] 6 [5] 7 [3, 5] 8 : non 9 [2, 5] 10 [3, 7] 11 [2, 6, 7, 8] 12 : non 13 [2, 6, 7, 11] 14 [3, 5] 15 : non 16 : non 17 [3, 5, 6, 7, 10, 11, 12, 14] 18 [5, 11] 19 [2, 3, 10, 13, 14, 15] 20 : non 21 : non 22 [7, 13, 17, 19] 23 [5, 7, 10, 11, 14, 15, 17,
19, 20, 21] 24 : non 25 [2, 3, 8, 12, 13, 17, 22, 23] 26 [7, 11, 15, 19] 27 [2, 5, 11, 14, 20, 23] 28 : non 29 [2, 3, 8, 10, 11, 14, 15, 18,
19, 21, 26, 27] 30 : non 31 [3, 11, 12, 13, 17, 21, 22,
24] 32 : non 33 : non 34 [3, 5, 7, 11, 23, 27, 29, 31] 35 : non 36 : non 37 [2, 5, 13, 15, 17, 18, 19,
20, 22, 24, 32, 35] 38 [3, 13, 15, 21, 29, 33] 39 : non 40 : non 41 [6, 7, 11, 12, 13, 15, 17,
19, 22, 24, 26, 28, 29, 30, 34, 35] 42 : non 43 [3, 5, 12, 18, 19, 20, 26,
28, 29, 30, 33, 34] 44 : non 45 : non 46 [5, 7, 11, 15, 17, 19, 21,
33, 37, 43] 47 [5, 10, 11, 13, 15, 19, 20,
22, 23, 26, 29, 30, 31, 33, 35, 38, 39, 40, 41, 43, 44, 45] 48 : non 49 [3, 5, 10, 12, 17, 24, 26,
33, 38, 40, 45, 47] 50 [3, 13, 17, 23, 27, 33, 37,
47] 51 : non 52 : non 53 [2, 3, 5, 8, 12, 14, 18, 19,
20, 21, 22, 26, 27, 31, 32, 33, 34, 35, 39, 41, 45, 48, 50, 51] 54 [5, 11, 23, 29, 41, 47] 55 : non 56 : non 57 : non |
58 [3, 11, 15, 19, 21, 27, 31,
37, 39, 43, 47, 55] 59 [2, 6, 8, 10, 11, 13, 14, 18,
23, 24, 30, 31, 32, 33, 34, 37, 38, 39, 40, 42, 43, 44, 47, 50, 52, 54, 55,
56] 60 : non 61 [2, 6, 7, 10, 17, 18, 26, 30,
31, 35, 43, 44, 51, 54, 55, 59] 62 [3, 11, 13, 17, 21, 43, 53,
55] 63 : non 64 : non 65 : non 66 : non 67 [2, 7, 11, 12, 13, 18, 20,
28, 31, 32, 34, 41, 44, 46, 48, 50, 51, 57, 61, 63] 68 : non 69 : non 70 : non 71 [7, 11, 13, 21, 22, 28, 31,
33, 35, 42, 44, 47, 52, 53, 55, 56, 59, 61, 62, 63, 65, 67, 68, 69] 72 : non 73 [5, 11, 13, 14, 15, 20, 26,
28, 29, 31, 33, 34, 39, 40, 42, 44, 45, 47, 53, 58, 59, 60, 62, 68] 74 [5, 13, 15, 17, 19, 35, 39,
55, 57, 59, 61, 69] 75 : non 76 : non 77 : non 78 : non 79 [3, 6, 7, 28, 29, 30, 34, 35,
37, 39, 43, 47, 48, 53, 54, 59, 60, 63, 66, 68, 70, 74, 75, 77] 80 : non 81 [2, 5, 11, 14, 20, 23, 29,
32, 38, 41, 47, 50, 56, 59, 65, 68, 74, 77] 82 [7, 11, 13, 15, 17, 19, 29,
35, 47, 53, 63, 65, 67, 69, 71, 75] 83 [2, 5, 6, 8, 13, 14, 15, 18,
19, 20, 22, 24, 32, 34, 35, 39, 42, 43, 45, 46, 47, 50, 52, 53, 54, 55, 56,
57, 58, 60, 62, 66, 67, 71, 72, 73, 74, 76, 79, 80] 84 : non 85 : non 86 [3, 5, 19, 29, 33, 55, 61,
63, 69, 71, 73, 77] 87 : non 88 : non 89 [3, 6, 7, 13, 14, 15, 19, 23,
24, 26, 27, 28, 29, 30, 31, 33, 35, 38, 41, 43, 46, 48, 51, 54, 56, 58, 59,
60, 61, 62, 63, 65, 66, 70, 74, 75, 76, 82, 83, 86] 90 : non 91 : non 92 : non 93 : non 94 [5, 11, 13, 15, 19, 23, 29,
31, 33, 35, 39, 41, 43, 45, 57, 67, 69, 73, 77, 85, 87, 91] 95 : non 96 : non 97 [5, 7, 10, 13, 14, 15, 17,
21, 23, 26, 29, 37, 38, 39, 40, 41, 56, 57, 58, 59, 60, 68, 71, 74, 76, 80,
82, 83, 84, 87, 90, 92] 98 [3, 5, 17, 33, 45, 47, 59,
61, 73, 75, 87, 89] 99 : non 100 : non |
|
|
||
|
Prenons
deux nombres premiers entre eux: 2 et 9. Calculons
les puissances successives du premier nombre (2), et leur reste dans la
division par le second nombre (modulo 9). Nous
observons que les restes suivent une périodicité: 2, 4, 8, 7, 5 et 1. L'exposant ( = 6) pour lequel le modulo de la puissance
vaut 1 est défini comme l'ordre multiplicatif
de 2 modulo 9. On dit aussi parfois que 2 appartient à l'exposant 6 modulo 9. Ainsi,
tableau du bas, l'ordre multiplicatif de 2 modulo 5 est 4. Dans ce
cas, notez que la période est 4 (= 5 – 1) et que tous les restes possibles
(de 1 à 4, sauf le 0) font partie de la période. On dit,
dans ce cas, que 2 est une racine primitive
modulo 5 |
L'ordre
multiplicatif de 2 par rapport à 9 est 6. Plus petit exposant tel que 2k
divisé par 9 produit un reste égal à 1.
L'ordre
multiplicatif de 2 par rapport à 5 est 4. Le
nombre 2 est une racine primitive modulo 5 car, avec les puissances
précédentes nous avons eu tous les restes possibles. |
|
Analyse
des puissances premières de 2
|
Lecture:
pour p = 7 et k = 3, 23 = 8
qui est congru à 1
mod 7; c'est la plus petite puissance pour laquelle le résidu vaut 1. La
puissance 3 est l'ordre de 2 modulo 7. Notez que pour 5, 11, 13, 19 et 29,
la ligne comporte tous les restes possibles de la division par ce nombre. 2
est une racine primitive de tous ces nombres premiers. L'ensemble de tous les
restes est nommé: classe des résidus
modulo p. Remarque: la classe des résidus ne
contient par le 0. En effet, 2 et p sont premiers entre eux. Une puissance de
2 ne peut pas être divisible par p. |
Analyse
des puissances premières de 3
|
Lecture:
pour p = 7 et k = 6, 36 = 32
x 32 x 32 ≡ 2 x 2 x 2 ≡ 8 ≡ 1 mod 7 ; c'est la plus petite puissance pour
laquelle le résidu vaut 1. La puissance 6 est l'ordre de 3 modulo 7. De plus,
tous les résidus ont été balayés. On remarque que k = 6 = 7 – 1. Le nombre 3
est racine primitive du nombre premier 7. Pour p = 13, la longueur du cycle
des résidus est 3 au lieu de 12, si on avait affaire à une racine primitive.
Mais, et c'est une propriété, 3 est un diviseur
de 12. |
|
|
||
|
Définition Soit m un entier positif et a un entier
quelconque, avec a et m premiers entre eux. Soit k le plus petit entier tel que: a puissance k est congru à 1.
L'exposant k est appelé ordre
(multiplicatif) de a modulo m. Définition mathématique Soit m L'ordre
de a modulo m est l'entier k tel que:
|
(a,
m) = 1
ordm(a) = k
ord9(2) = 6
ord5(2) = 4 |
|
|
Propriétés L'ordre
multiplicatif k est toujours inférieur à m ( démonstartion avec le petit théorème de Fermat). La valeur
de k est au plus égale à l'indicatrice
d'Euler (théorème
d'Euler). Si (a, m)
= 1, alors k divise Phi (m). Si m est
premier, alors k est un diviseur de Phi (p) = p – 1. |
|
|
|
|
||
|
Définition On dit
que a est une racine primitive modulo m si l'ordre de a est égal à Phi (m). C'est-à-dire
si Phi (m) est effectivement le plus petit exposant pour lequel le résidu
vaut 1. |
|
|
|
Propriétés Chacune
de racines primitives forme un système réduit de résidus. Si m est un nombre
premier la classe des résidus est complète. Dit
autrement: avec un nombre premier p,
l'ordre vaut p – 1 et tous les restes possibles précédant cette
puissance. |
|
|
Tableau de comparaison entre ordre et phi
|
Lecture:
On calcule k le plus petit, tel que ak
congru à 1 modulo m et on compare à la valeur de Phi (m). En jaune, les cas
où il y a égalité entre l'ordre et Phi. On se souvient que Phi (p) = p – 1. La ligne avec un Non, indique
qu'aucun résidu égal à 1 ne peut être trouvé pour cette configuration. |
|
|
|||
|
Tout
premier p possède Phi (p – 1)
primitives |
Dans le tableau ci-dessus, la quantité de ligne jaune pour un nombre
premier est égale à Phi du nombre précédent. Ainsi 17 compte 8 lignes jaunes (8 racines primitives) et Phi (16) =
8. |
||
|
Si m
n'est pas premier, les racines primitives n'existent que si => |
m = (2, 4, ou pk ou 2pk) avec p premier impair |
||
|
Si a est
d'ordre k modulo m, alors l'ordre de a puissance h est égal à k / (k, h) |
Ord5 (3) = 4 Ord5 (32) = 4 / (4, 2) = 4 / 2 = 2 Ord7 (3) = 6 Ord7 (311) = 6 / (6, 11) = 6 / 1 = 6 |
||
|
Si a est
d'ordre k modulo m et si b est d'ordre
h modulo m et si (k, h ) = 1, alors ab est d'ordre hk modulo m. |
Ord5 (2) = 4 Ord5 (3) = 4 Ord5 (6) = 16 |
||
|
Soit les
entiers naturels m et n. Les propositions suivantes sont équivalentes:
|
(m, n) = 1
|
||
|
Si p est
premier et (a, p) = 1, alors
possède
(n, p – 1) solutions à condition que:
Et aucune
solution sinon. |
x5 Test d'existence de solution:
En effet, en mod 101 Quantité de solutions: (5, 100) = 5 Un calcul donnerait ces cinq solutions: x |
||
|
|
|
|
Let m denote a positive integer and a any integer such that (a, m) =
1. Let k be the smallest positive integer such that |
|
|
Voir |
|
|
Livre |
|
|
Sites |
|
|
Cette page |
