순서는 무엇입니까 $\bar{2}$ 곱셈 그룹에서 $\mathbb Z_{289}^×$?

Nov 26 2020

순서는 무엇입니까 $\bar{2}$ 곱셈 그룹에서 $\mathbb Z_{289}^×$?

알아 $289 = 17 \times 17$

그래서 그럴까요 $2^8\equiv 256\bmod17 =1$

따라서 순서 $\bar{2}$ 이다 $8$? 이것에 대해 잘 모르겠습니다

답변

5 BillDubuque Nov 26 2020 at 13:36

이것은 사소한 계산만을 사용하여 정신적으로 매우 쉽게 할 수 있습니다.

$\!\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$.

2 fleablood Nov 26 2020 at 13:14

$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$.

2 Lapin Nov 26 2020 at 11:48

아니 .

의 순서 $\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$.

1 J.W.Tanner Nov 26 2020 at 21:53

$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$,

따라서 주문 테스트 ( Bill Dubuque 의 답변에 링크 됨 )에 의해$2$ 모드 $289$ 이다 $136$.

CopyPasteIt Nov 28 2020 at 20:43

세트 정의 $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$곱셈으로 닫힙니다.
증명

Consider,

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

while dividing $an +bm$ by $17$ to get the non-negative residue. $\quad \blacksquare$

So we can state (see bullet $1$ of this elementary group theory)

Proposition 2: The set $H$ forms a group of order $34$.

Continuing,

Proposition 3: The element $[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$.