Quel est l'ordre de $\bar{2}$ dans le groupe multiplicatif $\mathbb Z_{289}^×$?
Quel est l'ordre de $\bar{2}$ dans le groupe multiplicatif $\mathbb Z_{289}^×$?
je le sais $289 = 17 \times 17$
alors serait-ce $2^8\equiv 256\bmod17 =1$
et donc l'ordre de $\bar{2}$ est $8$? Je n'en suis pas trop sûr
Réponses
Cela peut être fait très facilement mentalement en utilisant uniquement des calculs triviaux.
$\!\bmod 17\!:\,\ 2^4\equiv -1\,\Rightarrow\, 2^8\equiv 1\Rightarrow 2\,$ a ordre $\,\color{#c00}{o(2) = 8}\,$par le test de commande.
$\!\bmod 17^2\!:\ n\!:=\!o(2)\Rightarrow\,2^n\equiv 1\,$ Donc $\bmod 17\!:\ 2^n\equiv 1\,$ Donc $\, \color{#c00}8\mid n\,$ alors $\,n = 8k$.
$\!\bmod 17\!:\ 2\equiv 6^2$ Donc $\,2\,$ est un $\rm\color{#0a0}{square}\bmod 17^2\:\!$ aussi, donc $\,o(2)=8k\mid \phi(17^2)/\color{#0a0}2 = 8\cdot 17$.
Alors $\,k\!=\!1$ ou $17.\,$ Mais $\,k\!\neq\! 1\,$ par $\,2^8\!\equiv\! 256\!\not\equiv \!1\pmod{\!289}\,$ alors $\,k\!=\!17,\,$ alors $\,o(2)\! =\! 8(17)\!=\!136$.
$256 \equiv 1 \pmod {17}$ mais $256\not \equiv 1 \pmod {289}$ dont nous avons besoin.
Mais non $289 = 17\times 17$ alors $\phi (289) = 17\cdot16$ alors $2^{17\cdot 16}\equiv 1\pmod {289}$ par le théorème d'Eulers.
Mais l'ordre pourrait être quelque chose de plus petit qui divise $17\cdot 16$.
Nous pouvons comprendre que $2^8 = 17*15 + 1 \equiv 17*(-2) + 1\pmod{17^2}$ alors
$2^{16} \equiv 17^2 *4 + 2*(-2)*17 + 1 \equiv -67 \pmod {289}$.
Donc, l'ordre de $2$ n'est pas $16$ et donc rien qui divise $16$. Donc, l'ordre de$2$ sera un multiple de $17$. être un multiple de$17$ qui divise $16*17$.
Et $2^{17} \equiv -8*17+2$
$2^{2*17} \equiv (-8*17+2)^2 \equiv -32*17+ 4\equiv 2*17+4 \equiv 38\pmod{289}$.
$2^{4*17} \equiv 4^2*17^2 + 16*17 + 4^2 \equiv 16*17 +16\equiv 18*16\equiv 1*(-1)\equiv -1 \pmod {289}$.
Et donc $2^{8*17}\equiv (-1)^2 \equiv 1 \pmod {289}$.
Donc, l'ordre de $2$ est $8*17= 136$.
Non .
L'ordre de $\bar 2$ dans $\mathbb Z_{17}^\times$ est $8$ car $2^8\equiv1\pmod{17}$.
cependant, $2^8\not\equiv1\pmod{289}$, alors $8$ n'est pas l'ordre de $\bar2$ dans $\mathbb Z_{289}^\times$.
L'ordre de $\bar 2$ dans $\mathbb Z_{289}^\times$, c'est-à-dire le plus petit entier positif $k$ tel que $2^k\equiv1\pmod{289}$, est $136$. (J'ai utilisé mon ordinateur pour l'obtenir.)
Fait:
Laisser $\operatorname {ord}_n(a)$ être l'ordre de $\bar a$ dans $\mathbb Z_{n}^\times$. Puis, pour prime$p$ et entiers positifs $k<l$, $$ \operatorname {ord}_{p^k}(a)\mid\operatorname {ord}_{p^l}(a). $$ Par exemple, $8\mid136$.
$2^8\equiv1\bmod17$, alors
$2^{128}+2^{120}+2^{112}+\cdots+2^{16}+2^{8}+1\equiv1+1+1+\cdots+1+1+1=17\equiv0\bmod17,$
alors $2^{136}-1=(2^{128}+2^{120}+2^{112}+\cdots+2^{16}+2^{8}+1)(2^8-1)\equiv0\bmod289$,
mais $2^8-1=255\not\equiv0\bmod289$,
et $2^{68}-1\not\equiv0\bmod289$ car $2^{68}-1\equiv2^4-1=15\not\equiv0\bmod17$,
ainsi, par le test d'ordre (lié dans la réponse de Bill Dubuque ), l'ordre de$2$ mod $289$ est $136$.
Définir l'ensemble $H \subset {\displaystyle (\mathbb {Z} /289\mathbb {Z} )^{\times }}$ par
$\tag 1 H = \bigr\{[a + 17m] \,\large \mid \, \normalsize a \in \{-1,+1\} \text{ and } 0 \le m \lt 17\bigr\}$
Il est facile de montrer que $H$ contient exactement $34$ éléments.
Proposition 1: L'ensemble $H$est fermé sous multiplication.
Preuve
Considérer,
$\quad (a + 17m)(b+17n) = ab + 17(an +bm) + mn\cdot 17^2$
en divisant $an +bm$ par $17$ pour obtenir le résidu non négatif. $\quad \blacksquare$
Nous pouvons donc déclarer (voir puce $1$de cette théorie élémentaire des groupes)
Proposition 2: L'ensemble $H$ forme un groupe d'ordre $34$.
Continuant,
Proposition 3: L'élément $[16]$ génère $H$.
Preuve
L'ordre de$[16]$ doit diviser $34$.
L'ordre de$[16]$ n'est pas égal à $2$. De plus, en appliquant le théorème binomial, nous pouvons écrire
$\quad 16^{17} = \bigr((-1) + 17\bigr)^{17} = (-1)^{17} + \binom{17}{16}(-1)^{16}\cdot 17^{1} + K\cdot 17^2 \equiv -1 \pmod{289}$
et donc l'ordre de $[16]$ doit être $34$. $\quad \blacksquare$
Il existe deux méthodes que nous pouvons utiliser ici pour trouver l'ordre de $[2]$.
Méthode 1:
Depuis $[2]^4 = [16]$ et $[2] \notin H$ l'ordre de $[2]$ est strictement supérieur à $34$. Aussi, avec ce fait et
$\quad [2]^{136} = [16]^{34} = [1]$
nous devons conclure que l'ordre de $[2]$ est soit $68$ ou $136$.
Maintenant
$\quad [2]^{68} = [16]^{17} \ne [1]$
et nous concluons donc que l'ordre de $[2]$ est $136$.
Méthode 2
Depuis $[2]^1, [2]^2, [2]^3 \notin H$ et $[2]^4 = [16] \in H$nous pouvons utiliser la théorie des groupes trouvée ici et conclure que l'ordre de$[2]$ est $4 \times 34 = 136$.