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

Dans toute cette chronique, 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$ est égal précisément égal à $28$ modulo $29.$

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$, 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.$ Divisant $812$ par $29$ qui a pour quotient $28$ vous allez calculer $14^{28}.$

Vous calculez successivement des puissances de $14$ modulo $841.$ Pour des raisons de lisibilité, les modulos $841$ ont été omis après la première ligne pour chaque calcul effectué.

\begin{align*} 14^2& \equiv 196\quad[841]. \end{align*}

\begin{align*} 14^4&= (14^2)^2\quad[841] \\ &= 196^2\\ &= (200-4)^2 \\ &= 200^2 -8\times 200 + 16 \\ &= 40000 -1600 + 16 \\ &= 40016 -1600 \\ &= 40016 -2000+400 \\ &= 38416\\ &= 38416 -841\times 10\\ &= 30006 -841\times 20\\ &= 30006 -16820\\ &=14006-820\\ &=13006+180\\ &=13186\\ &=13186-8410\\ &=5186-410\\ &=4776\\ &=4776-841\times 2\\ &=4776-1682\\ &=3176-82\\ &=3076+18\\ &=3094\\ &=3094-1682\\ &=1412\\ &=1412-841\\ &=612-41\\ &=512+59\\ &=571\\ &=571-841\\ &=- 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 $r\in\NN$ l’ordre de $14$ modulo $841$, 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$, 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, $d\mid 28$ et par conséquent $d=28.$

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

Prolongement

Soit $p$ un nombre premier. Cet article montre que, si $a$ est primitif modulo $p$, 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 ?

Partagez maintenant !

Aidez vos amis à découvrir cet article et à mieux comprendre le sujet.

Aidez-moi sur Facebook !

Vous appréciez cet article et souhaitez témoigner du temps que j'y ai passé pour le mettre en œuvre. C'est rapide à faire pour vous et c'est important pour moi, déposez un j'aime sur ma page Facebook. Je vous en remercie par avance.

Lisez d'autres articles !

Parcourez tous les articles qui ont été rédigés. Vous en trouverez sûrement un qui vous plaira !