École AVOSZ

Connectez-vous

389. Le nombre 14 est primitif modulo 29 mais ne l’est pas modulo 841

Yannis TRIANTAPHYLIDES

Dans tout ce contenu, vous noterez $G$ le groupe multiplicatif des éléments inversibles de $\Z/29\Z.$ De même, vous noterez $H$ le groupe multiplicatif des éléments inversibles de $\Z/841\Z.$

Montrez que la classe de $14$ dans $\Z/29\Z$ est un générateur du groupe multiplicatif des inversibles de $\Z/29\Z$

Comme $\pgcd(14,29)=1$ la classe de $14$ appartient bien à $G.$ Notez que, grâce au théorème de Lagrange, $14^{28} \equiv 1\quad[29].$ Donc l’ordre de la classe de $14$ est un diviseur de $28.$

Comme $29$ est un nombre premier, les inversibles de $\Z/29\Z$ sont au nombre de $29-1=28.$ Pour montrer que la classe de $14$ est un générateur de $G$ il faut démontrer que l’ordre de $14$ modulo $29$ est précisément égal à $28.$

Comme la décomposition en produit de nombres premiers de $28$ est $28 = 2^2\times 7$ il suffit de démontrer que $14^{14}$ et $14^4$ ne sont pas congrus à $1$ modulo $29.$ En effet, dans la décomposition en produit de nombres premiers de $28\comma$ seuls $2$ et $7$ sont les nombres premiers utilisés. Si $\frac{28}{2}=14$ n’est pas un multiple de l’ordre de la classe de $14$ et si $\frac{28}{7}=4$ ne l’est pas non plus, alors l’ordre de la classe de $14$ sera bien égal à $28.$ En effet, tout diviseur strict de $28$ est soit un diviseur de $14$ soit un diviseur de $4.$

D’une part :

\begin{align*} 14^2 &\equiv 196 \quad[29] \\ &\equiv 196-6\times 29 \quad[29]\\ &\equiv 196-6\times (30-1) \quad[29]\\ &\equiv 196-180+6 \quad[29]\\ &\equiv22 \quad[29]\\ &\equiv22-29 \quad[29]\\ &\equiv -7 \quad[29]. \end{align*}

D’autre part :

\begin{align*} 14^4 &\equiv (14^2)^2 \quad[29] \\ &\equiv (-7)^2\quad[29]\\ &\equiv 49 \quad[29]\\ &\equiv 20 \quad[29]\\ &\equiv -9 \quad[29]. \end{align*}

Vous avez donc $14^{4} \not\equiv 1 \quad[29].$

Il reste à calculer $14^{14}$ modulo $29.$

\begin{align*} 14^8 &\equiv (14^4)^2 \quad[29] \\ &\equiv (-9)^2\quad[29]\\ &\equiv 81 \quad[29]\\ &\equiv 81-3\times(30-1) \quad[29]\\ &\equiv 81-90+3 \quad[29]\\ &\equiv -6 \quad[29]. \end{align*}
\begin{align*} 14^{14}&\equiv 14^8 \times 14^4 \times 14^2\quad[29] \\ &\equiv (-6)\times (-9) \times (-7)\quad[29]\\ &\equiv 54 \times (-7) \quad[29]\\ &\equiv (54-29\times 2) \times (-7) \quad[29]\\ &\equiv (54-58) \times (-7) \quad[29]\\ &\equiv (-4) \times (-7) \quad[29]\\ &\equiv 28 \quad[29]\\ &\equiv -1 \quad[29]. \end{align*}

Vous avez donc $14^{14} \not\equiv 1 \quad[29].$

Donc $14$ est primitif modulo $29.$

Montrez que la classe de $14$ dans $\Z/841\Z$ n’est pas un générateur du groupe multiplicatif des inversibles de $\Z/841\Z$

Le groupe multiplicatif des inversibles de $\Z/841\Z$ possède $\varphi(841)$ éléments où $\varphi$ est la fonction indicatrice d’Euler. Or :

\begin{align*} \varphi(841) &=\varphi(29^2)\\ &= 29^2-29\\ &=29\times 28\\ &=(30-1)(30-2)\\ &=30(30-2-1)+2\\ &=30\times 27 +2\\ &= 812. \end{align*}

Tout d’abord, la classe de $14$ appartient bien au groupe $H.$ En effet, comme $\pgcd(14,29)=1$ il s’ensuit que $\pgcd(14,29^2)=1.$

Il s’agit de démontrer que la classe de $14$ n’a pas un ordre égal à $812.$ Par le théorème de Lagrange, vous savez déjà que $14^{812}\equiv 1\quad[841].$ L’ordre $d$ de $14$ divise donc $812.$ La décomposition en produit de nombres premiers de $812=29\times 28$ est $29\times 7\times 2^2.$ Le quotient de $812$ par $29$ étant égal à $28\comma$ vous allez calculer $14^{28}.$

Vous calculez successivement des puissances de $14$ modulo $841.$ Pour des raisons de lisibilité, la mention du module $841$ est omise après la première ligne de chaque calcul.

14^2 \equiv 196\quad[841].
\begin{align*} 14^4&\equiv (14^2)^2\quad[841] \\ &\equiv 196^2\\ &\equiv (200-4)^2 \\ &\equiv 200^2 -8\times 200 + 16 \\ &\equiv 40000 -1600 + 16 \\ &\equiv 40016 -1600 \\ &\equiv 40016 -2000+400 \\ &\equiv 38416\\ &\equiv 38416 -841\times 10\\ &\equiv 30006 -841\times 20\\ &\equiv 30006 -16820\\ &\equiv 14006-820\\ &\equiv 13006+180\\ &\equiv 13186\\ &\equiv 13186-8410\\ &\equiv 5186-410\\ &\equiv 4776\\ &\equiv 4776-841\times 2\\ &\equiv 4776-1682\\ &\equiv 3176-82\\ &\equiv 3076+18\\ &\equiv 3094\\ &\equiv 3094-1682\\ &\equiv 1412\\ &\equiv 1412-841\\ &\equiv 612-41\\ &\equiv 512+59\\ &\equiv 571\\ &\equiv 571-841\\ &\equiv – 270. \end{align*}
\begin{align*} 14^8 &\equiv (14^4)^2 \quad[841] \\ &\equiv (-270)^2\\ &\equiv 27^2\times 100\\ &\equiv 72900\\ &\equiv 72900 – 841\times 100\\ &\equiv 72900 – 84100\\ &\equiv -(84100-72900)\\ &\equiv -(12100-900)\\ &\equiv -(11100+100)\\ &\equiv -11200\\ &\equiv -(11200-841\times 10)\\ &\equiv -(11200-8410)\\ &\equiv -(3200-410)\\ &\equiv -(2200+590)\\ &\equiv -(2790)\\ &\equiv -(2790 – 841\times 2)\\ &\equiv -(2790 – 1682)\\ &\equiv -(1110 – 2)\\ &\equiv -1108\\ &\equiv -(1108-841)\\ &\equiv -(308-41)\\ &\equiv -267. \end{align*}
\begin{align*} 14^{16} &\equiv (14^8)^2 \quad[841] \\ &\equiv (-267)^2\\ &\equiv (-270+3)^2\\ &\equiv 270^2 -2\times 3\times 270+9\\ &\equiv -267 -2\times 3\times 270+9\\ &\equiv -270+3 -2\times 3\times 270+9\\ &\equiv -270 -2\times 3\times 270+12\\ &\equiv -270 -6 \times 270+12\\ &\equiv – 7 \times 270+12\\ &\equiv – 1890+12\\ &\equiv – (1890-12)\\ &\equiv – 1878\\ &\equiv – (1878-841\times 2) \\ &\equiv – (1878-1682) \\ &\equiv – (278-82) \\ &\equiv – (178+18) \\ &\equiv – 196. \end{align*}
\begin{align*} 14^{12} &\equiv 14^{8} \times 14^{4}\quad[841]\\ &\equiv (-267)\times (-270)\\ &\equiv 267\times 270\\ &\equiv (270-3)\times 270\\ &\equiv 270^2 -3 \times 270\\ &\equiv 27^2\times 100 – 810\\ &\equiv 729 \times 100 – 810\\ &\equiv (729 – 841)\times 100 – (810-841)\\ &\equiv -(841-729 )\times 100 + (841-810)\\ &\equiv -(121-9 )\times 100 + 31\\ &\equiv -(112 )\times 100 + 31\\ &\equiv -(1120 )\times 10 + 31\\ &\equiv -(1120 -841)\times 10 + 31\\ &\equiv -(320 -41)\times 10 + 31\\ &\equiv -(220 +59)\times 10 + 31\\ &\equiv -279\times 10 + 31\\ &\equiv -2790 + 31\\ &\equiv -2759 \\ &\equiv -(2759-2\times 841) \\ &\equiv -(2759-1682) \\ &\equiv -(1159-82) \\ &\equiv -(1059+18) \\ &\equiv -1077 \\ &\equiv -(1077-2\times 841) \\ &\equiv -(1077-1682) \\ &\equiv 1682 -1077 \\ &\equiv 605\\ &\equiv 605-841\\ &\equiv -(841-605)\\ &\equiv -236. \end{align*}
\begin{align*} 14^{28} &\equiv14^{12}\times 14^{16}\quad[841]\\ &\equiv (-236)\times (-196)\\ &\equiv 236\times 196\\ &\equiv 236\times (200-4)\\ &\equiv 4720\times 10- 944\\ &\equiv (4720 – 841\times 4)\times 10- (944-841)\\ &\equiv (4720 – 1682\times 2)\times 10- 103\\ &\equiv (4720 – 3364)\times 10- 103\\ &\equiv (1420 – 64)\times 10- 103\\ &\equiv (1320 + 36)\times 10- 103\\ &\equiv 1356 \times 10- 103\\ &\equiv (1356 – 841\times 2) \times 10- 103\\ &\equiv (1356 – 1682) \times 10- 103\\ &\equiv -(1682-1356 ) \times 10- 103\\ &\equiv -326 \times 10- 103\\ &\equiv -3260 – 103\\ &\equiv -(3260-841\times 2) – 103\\ &\equiv -(3260-1682) – 103\\ &\equiv -(1260+318) – 103\\ &\equiv -1578 – 103\\ &\equiv -1681 \\ &\equiv -1681 +2\times 841\\ &\equiv -1681 +1682\\ &\equiv 1. \end{align*}

Comme $14^{28}$ est congru à $1$ modulo $841$ vous avez démontré que la classe de $14$ n’est pas un générateur du groupe multiplicatif des inversibles de $\Z/841\Z.$ Autrement dit, $14$ n’est pas primitif modulo $841.$

Pour aller plus loin, déterminez l’ordre de $14$ modulo $841$

Soit $d\in\NN$ l’ordre de $14$ modulo $841\comma$ c’est-à-dire le plus petit entier naturel non nul $n$ tel que $14^n\equiv 1\quad[841].$

Vous savez déjà que $14^{28}\equiv 1 \quad[841]$ ce qui entraîne $d\mid 28.$

Or, par définition de $d\comma$ vous avez $14^d \equiv 1\quad[841].$ Comme $29 \mid 841$ vous avez aussi $14^d \equiv 1 \quad[29].$ Or vous avez établi dans ce contenu que $14$ est primitif modulo $29$ ce qui prouve que l’ordre de $14$ modulo $29$ est égal à $28.$ Du coup, $28\mid d.$ Comme $d\mid 28$ et que $d$ et $28$ sont des entiers naturels non nuls, vous obtenez $d=28.$

Pour conclure, $14$ est d’ordre $28$ modulo $841.$

Prolongement

Soit $p$ un nombre premier. Ce contenu montre que, si $a$ est primitif modulo $p\comma$ alors $a$ n’est pas nécessairement primitif modulo $p^2$ même si en pratique cela reste fréquent. Trouver un élément qui soit primitif modulo $p^2$ à partir d’un élément primitif modulo $p$ c’est trouver ce qui s’appelle un relèvement.

Pourriez-vous proposer une méthode permettant de trouver un tel relèvement ?