の順序は何ですか $\bar{2}$ 乗法群で $\mathbb Z_{289}^×$？

Question

の順序は何ですか $\bar{2}$ 乗法群で $\mathbb Z_{289}^×$？

そんなこと知ってる $289 = 17 \times 17$

そうだろう $2^8\equiv 256\bmod17 =1$

したがって、 $\bar{2}$ です $8$？これについてはよくわかりません

Answer 1

これは、些細な計算だけを使用して精神的に非常に簡単に行うことができます。

$\!\bmod 17\!:\,\ 2^4\equiv -1\,\Rightarrow\, 2^8\equiv 1\Rightarrow 2\,$ 注文があります $\,\color{#c00}{o(2) = 8}\,$注文をテスト。

$\!\bmod 17^2\!:\ n\!:=\!o(2)\Rightarrow\,2^n\equiv 1\,$ したがって、 $\bmod 17\!:\ 2^n\equiv 1\,$ したがって、 $\, \color{#c00}8\mid n\,$ そう $\,n = 8k$。

$\!\bmod 17\!:\ 2\equiv 6^2$ したがって、 $\,2\,$ は $\rm\color{#0a0}{square}\bmod 17^2\:\!$ あまりにもそう $\,o(2)=8k\mid \phi(17^2)/\color{#0a0}2 = 8\cdot 17$。

そう $\,k\!=\!1$ または $17.\,$ だが $\,k\!\neq\! 1\,$ 沿って $\,2^8\!\equiv\! 256\!\not\equiv \!1\pmod{\!289}\,$ そう $\,k\!=\!17,\,$ そう $\,o(2)\! =\! 8(17)\!=\!136$。

Answer 2

$256 \equiv 1 \pmod {17}$ だが $256\not \equiv 1 \pmod {289}$ 必要なものです。

だがしかし $289 = 17\times 17$ そう $\phi (289) = 17\cdot16$ そう $2^{17\cdot 16}\equiv 1\pmod {289}$ オイラーの定理による。

しかし、順序は分割するより小さなものかもしれません $17\cdot 16$。

私たちはそれを理解することができます $2^8 = 17*15 + 1 \equiv 17*(-2) + 1\pmod{17^2}$ そう

$2^{16} \equiv 17^2 *4 + 2*(-2)*17 + 1 \equiv -67 \pmod {289}$。

だからの順序 $2$ ではありません $16$ したがって、分割するものは何もありません $16$。だからの順序$2$ の倍数になります $17$。の倍数になる$17$ 分割する $16*17$。

そして $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}$。

など $2^{8*17}\equiv (-1)^2 \equiv 1 \pmod {289}$。

だからの順序 $2$ です $8*17= 136$。

Answer 3

いいえ。

の順 $\bar 2$ に $\mathbb Z_{17}^\times$ です $8$ なぜなら $2^8\equiv1\pmod{17}$。

しかしながら、 $2^8\not\equiv1\pmod{289}$、 そう $8$ の順序ではありません $\bar2$ に $\mathbb Z_{289}^\times$。

の順 $\bar 2$ に $\mathbb Z_{289}^\times$、つまり最小の正の整数 $k$ そのような $2^k\equiv1\pmod{289}$、です $136$。（これを取得するためにコンピューターを使用しました。）

事実：

しましょう $\operatorname {ord}_n(a)$ の順序である $\bar a$ に $\mathbb Z_{n}^\times$。次に、プライムのために$p$ および正の整数 $k<l$、 $$ \operatorname {ord}_{p^k}(a)\mid\operatorname {ord}_{p^l}(a). $$ 例えば、 $8\mid136$。

Answer 4

$2^8\equiv1\bmod17$、 そう

$2^{128}+2^{120}+2^{112}+\cdots+2^{16}+2^{8}+1\equiv1+1+1+\cdots+1+1+1=17\equiv0\bmod17,$

そう $2^{136}-1=(2^{128}+2^{120}+2^{112}+\cdots+2^{16}+2^{8}+1)(2^8-1)\equiv0\bmod289$、

だが $2^8-1=255\not\equiv0\bmod289$、

そして $2^{68}-1\not\equiv0\bmod289$ なぜなら $2^{68}-1\equiv2^4-1=15\not\equiv0\bmod17$、

したがって、注文テスト（ビル・ドゥビュークの回答にリンクされている）によって、$2$ モッド $289$ です $136$。

Answer 5

セットを定義する $H \subset {\displaystyle (\mathbb {Z} /289\mathbb {Z} )^{\times }}$ 沿って

$\tag 1 H = \bigr\{[a + 17m] \,\large \mid \, \normalsize a \in \{-1,+1\} \text{ and } 0 \le m \lt 17\bigr\}$

それを示すのは簡単です $H$ 正確に含まれています $34$ 要素。

命題1：セット $H$乗算で閉じられます。
証明

考えてみてください

$\quad (a + 17m)(b+17n) = ab + 17(an +bm) + mn\cdot 17^2$

分割しながら $an +bm$ 沿って $17$ 非負の残差を取得します。 $\quad \blacksquare$

だから私たちは述べることができます（箇条書きを参照） $1$この基本群論）

命題2：セット $H$ 秩序のグループを形成する $34$。

続けて、

提案3：要素 $[16]$ generates $H$.
Proof
The order of $[16]$ must divide $34$.
The order of $[16]$ is not equal to $2$. Moreover, by applying the binomial theorem we can write

$\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}$

and so the order of $[16]$ must be $34$. $\quad \blacksquare$

There are two methods we can use here to finding the order of $[2]$.

Method 1:

Since $[2]^4 = [16]$ and $[2] \notin H$ the order of $[2]$ is strictly greater than $34$. Also, with this fact and

$\quad [2]^{136} = [16]^{34} = [1]$

we must conclude that the order of $[2]$ is either $68$ or $136$.

Now

$\quad [2]^{68} = [16]^{17} \ne [1]$

and we therefore conclude that the order of $[2]$ is $136$.

Method 2

Since $[2]^1, [2]^2, [2]^3 \notin H$ and $[2]^4 = [16] \in H$ we can employ the group theory found here and conclude that the order of $[2]$ is $4 \times 34 = 136$.