Jaka jest kolejność $\bar{2}$ w grupie multiplikatywnej $\mathbb Z_{289}^×$?
Jaka jest kolejność $\bar{2}$ w grupie multiplikatywnej $\mathbb Z_{289}^×$?
wiem to $289 = 17 \times 17$
tak by było $2^8\equiv 256\bmod17 =1$
a zatem kolejność $\bar{2}$ jest $8$? Nie jestem tego pewien
Odpowiedzi
Można to zrobić bardzo łatwo, używając tylko trywialnych obliczeń.
$\!\bmod 17\!:\,\ 2^4\equiv -1\,\Rightarrow\, 2^8\equiv 1\Rightarrow 2\,$ ma porządek $\,\color{#c00}{o(2) = 8}\,$przez test zamówienia.
$\!\bmod 17^2\!:\ n\!:=\!o(2)\Rightarrow\,2^n\equiv 1\,$ a zatem $\bmod 17\!:\ 2^n\equiv 1\,$ a zatem $\, \color{#c00}8\mid n\,$ więc $\,n = 8k$.
$\!\bmod 17\!:\ 2\equiv 6^2$ a zatem $\,2\,$ jest $\rm\color{#0a0}{square}\bmod 17^2\:\!$ też tak $\,o(2)=8k\mid \phi(17^2)/\color{#0a0}2 = 8\cdot 17$.
Więc $\,k\!=\!1$ lub $17.\,$ Ale $\,k\!\neq\! 1\,$ przez $\,2^8\!\equiv\! 256\!\not\equiv \!1\pmod{\!289}\,$ więc $\,k\!=\!17,\,$ więc $\,o(2)\! =\! 8(17)\!=\!136$.
$256 \equiv 1 \pmod {17}$ ale $256\not \equiv 1 \pmod {289}$ których potrzebujemy.
Ale nie $289 = 17\times 17$ więc $\phi (289) = 17\cdot16$ więc $2^{17\cdot 16}\equiv 1\pmod {289}$ przez twierdzenie Eulersa.
Ale kolejność może być czymś mniejszym, co dzieli $17\cdot 16$.
Możemy to sobie wyobrazić $2^8 = 17*15 + 1 \equiv 17*(-2) + 1\pmod{17^2}$ więc
$2^{16} \equiv 17^2 *4 + 2*(-2)*17 + 1 \equiv -67 \pmod {289}$.
Więc kolejność $2$ nie jest $16$ a więc nic, co dzieli $16$. Więc kolejność$2$ będzie wielokrotnością $17$. być wielokrotnością$17$ to dzieli $16*17$.
I $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}$.
A więc $2^{8*17}\equiv (-1)^2 \equiv 1 \pmod {289}$.
Więc kolejność $2$ jest $8*17= 136$.
Nie .
Kolejność $\bar 2$ w $\mathbb Z_{17}^\times$ jest $8$ dlatego $2^8\equiv1\pmod{17}$.
Jednak, $2^8\not\equiv1\pmod{289}$, więc $8$ nie jest kolejnością $\bar2$ w $\mathbb Z_{289}^\times$.
Kolejność $\bar 2$ w $\mathbb Z_{289}^\times$, tj. najmniejsza dodatnia liczba całkowita $k$ takie że $2^k\equiv1\pmod{289}$, jest $136$. (Użyłem komputera, aby to uzyskać.)
Fakt:
Pozwolić $\operatorname {ord}_n(a)$ być kolejnością $\bar a$ w $\mathbb Z_{n}^\times$. Następnie za pierwszeństwo$p$ i dodatnie liczby całkowite $k<l$, $$ \operatorname {ord}_{p^k}(a)\mid\operatorname {ord}_{p^l}(a). $$ Na przykład, $8\mid136$.
$2^8\equiv1\bmod17$, więc
$2^{128}+2^{120}+2^{112}+\cdots+2^{16}+2^{8}+1\equiv1+1+1+\cdots+1+1+1=17\equiv0\bmod17,$
więc $2^{136}-1=(2^{128}+2^{120}+2^{112}+\cdots+2^{16}+2^{8}+1)(2^8-1)\equiv0\bmod289$,
ale $2^8-1=255\not\equiv0\bmod289$,
i $2^{68}-1\not\equiv0\bmod289$ dlatego $2^{68}-1\equiv2^4-1=15\not\equiv0\bmod17$,
tak więc, przez test zamówienia (powiązany w odpowiedzi Billa Dubuque ), kolejność$2$ mod $289$ jest $136$.
Zdefiniuj zestaw $H \subset {\displaystyle (\mathbb {Z} /289\mathbb {Z} )^{\times }}$ przez
$\tag 1 H = \bigr\{[a + 17m] \,\large \mid \, \normalsize a \in \{-1,+1\} \text{ and } 0 \le m \lt 17\bigr\}$
Łatwo to pokazać $H$ zawiera dokładnie $34$ elementy.
Twierdzenie 1: zbiór $H$zamyka się mnożeniem.
Dowód
Rozważać,
$\quad (a + 17m)(b+17n) = ab + 17(an +bm) + mn\cdot 17^2$
podczas dzielenia $an +bm$ przez $17$ aby uzyskać nieujemną resztę. $\quad \blacksquare$
Więc możemy stwierdzić (patrz punktor $1$od tej elementarnej teorii grup)
Twierdzenie 2: zbiór $H$ tworzy grupę zamówień $34$.
Kontynuacja,
Twierdzenie 3: element $[16]$ generuje $H$.
Dowód
Kolejność$[16]$ musi podzielić $34$.
Kolejność$[16]$ nie jest równe $2$. Ponadto, stosując twierdzenie dwumianowe, możemy pisać
$\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}$
a więc kolejność $[16]$ musi być $34$. $\quad \blacksquare$
Istnieją dwie metody, których możemy użyć, aby znaleźć kolejność $[2]$.
Metoda 1:
Od $[2]^4 = [16]$ i $[2] \notin H$ kolejność $[2]$ jest ściśle większa niż $34$. Również z tym faktem i
$\quad [2]^{136} = [16]^{34} = [1]$
musimy stwierdzić, że kolejność $[2]$ jest albo $68$ lub $136$.
Teraz
$\quad [2]^{68} = [16]^{17} \ne [1]$
i dlatego dochodzimy do wniosku, że kolejność $[2]$ jest $136$.
Metoda 2
Od $[2]^1, [2]^2, [2]^3 \notin H$ i $[2]^4 = [16] \in H$możemy zastosować znalezioną tutaj teorię grup i wywnioskować, że rząd$[2]$ jest $4 \times 34 = 136$.