Was ist die Reihenfolge von $\bar{2}$ in der multiplikativen Gruppe $\mathbb Z_{289}^×$?
Was ist die Reihenfolge von $\bar{2}$ in der multiplikativen Gruppe $\mathbb Z_{289}^×$?
ich weiß das $289 = 17 \times 17$
so wäre es $2^8\equiv 256\bmod17 =1$
und damit die Reihenfolge von $\bar{2}$ ist $8$? Da bin ich mir nicht sicher
Antworten
Dies kann mental sehr einfach mit nur trivialen Berechnungen geschehen.
$\!\bmod 17\!:\,\ 2^4\equiv -1\,\Rightarrow\, 2^8\equiv 1\Rightarrow 2\,$ hat Ordnung $\,\color{#c00}{o(2) = 8}\,$durch den Auftragstest.
$\!\bmod 17^2\!:\ n\!:=\!o(2)\Rightarrow\,2^n\equiv 1\,$ so $\bmod 17\!:\ 2^n\equiv 1\,$ so $\, \color{#c00}8\mid n\,$ damit $\,n = 8k$.
$\!\bmod 17\!:\ 2\equiv 6^2$ so $\,2\,$ ist ein $\rm\color{#0a0}{square}\bmod 17^2\:\!$ auch so $\,o(2)=8k\mid \phi(17^2)/\color{#0a0}2 = 8\cdot 17$.
Damit $\,k\!=\!1$ oder $17.\,$ Aber $\,k\!\neq\! 1\,$ durch $\,2^8\!\equiv\! 256\!\not\equiv \!1\pmod{\!289}\,$ damit $\,k\!=\!17,\,$ damit $\,o(2)\! =\! 8(17)\!=\!136$.
$256 \equiv 1 \pmod {17}$ aber $256\not \equiv 1 \pmod {289}$ was wir brauchen.
Aber nicht $289 = 17\times 17$ damit $\phi (289) = 17\cdot16$ damit $2^{17\cdot 16}\equiv 1\pmod {289}$ nach dem Satz von Eulers.
Aber die Reihenfolge könnte etwas kleiner sein, das teilt $17\cdot 16$.
Das können wir uns vorstellen $2^8 = 17*15 + 1 \equiv 17*(-2) + 1\pmod{17^2}$ damit
$2^{16} \equiv 17^2 *4 + 2*(-2)*17 + 1 \equiv -67 \pmod {289}$.
Also die Reihenfolge von $2$ ist nicht $16$ und damit nichts, was teilt $16$. Also die Reihenfolge von$2$ wird ein Vielfaches von sein $17$. ein Vielfaches von sein$17$ das teilt sich $16*17$.
Und $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}$.
Und so $2^{8*17}\equiv (-1)^2 \equiv 1 \pmod {289}$.
Also die Reihenfolge von $2$ ist $8*17= 136$.
Nein .
Die Reihenfolge von $\bar 2$ im $\mathbb Z_{17}^\times$ ist $8$ weil $2^8\equiv1\pmod{17}$.
Jedoch, $2^8\not\equiv1\pmod{289}$, damit $8$ ist nicht die Reihenfolge von $\bar2$ im $\mathbb Z_{289}^\times$.
Die Reihenfolge von $\bar 2$ im $\mathbb Z_{289}^\times$dh die kleinste positive ganze Zahl $k$ so dass $2^k\equiv1\pmod{289}$ist $136$. (Ich habe meinen Computer benutzt, um das zu bekommen.)
Tatsache:
Lassen $\operatorname {ord}_n(a)$ sei die Reihenfolge von $\bar a$ im $\mathbb Z_{n}^\times$. Dann für Prime$p$ und positive ganze Zahlen $k<l$, $$ \operatorname {ord}_{p^k}(a)\mid\operatorname {ord}_{p^l}(a). $$ Zum Beispiel, $8\mid136$.
$2^8\equiv1\bmod17$, damit
$2^{128}+2^{120}+2^{112}+\cdots+2^{16}+2^{8}+1\equiv1+1+1+\cdots+1+1+1=17\equiv0\bmod17,$
damit $2^{136}-1=(2^{128}+2^{120}+2^{112}+\cdots+2^{16}+2^{8}+1)(2^8-1)\equiv0\bmod289$,
aber $2^8-1=255\not\equiv0\bmod289$,
und $2^{68}-1\not\equiv0\bmod289$ weil $2^{68}-1\equiv2^4-1=15\not\equiv0\bmod17$,
also durch den Auftragstest (verknüpft in der Antwort von Bill Dubuque ) die Reihenfolge von$2$ mod $289$ ist $136$.
Definieren Sie den Satz $H \subset {\displaystyle (\mathbb {Z} /289\mathbb {Z} )^{\times }}$ durch
$\tag 1 H = \bigr\{[a + 17m] \,\large \mid \, \normalsize a \in \{-1,+1\} \text{ and } 0 \le m \lt 17\bigr\}$
Das ist leicht zu zeigen $H$ enthält genau $34$ Elemente.
Satz 1: Die Menge $H$wird unter Multiplikation geschlossen.
Beweis
Erwägen,
$\quad (a + 17m)(b+17n) = ab + 17(an +bm) + mn\cdot 17^2$
beim Teilen $an +bm$ durch $17$ um den nicht negativen Rückstand zu erhalten. $\quad \blacksquare$
So können wir sagen (siehe Kugel $1$von dieser elementaren Gruppentheorie)
Satz 2: Die Menge $H$ bildet eine Ordnungsgruppe $34$.
Auch weiterhin,
Satz 3: Das Element $[16]$ erzeugt $H$.
Beweis
Die Reihenfolge von$[16]$ muss teilen $34$.
Die Reihenfolge von$[16]$ ist ungleich zu $2$. Darüber hinaus können wir durch Anwendung des Binomialsatzes schreiben
$\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}$
und so die Reihenfolge von $[16]$ muss sein $34$. $\quad \blacksquare$
Es gibt zwei Methoden, mit denen wir die Reihenfolge von ermitteln können $[2]$.
Methode 1:
Schon seit $[2]^4 = [16]$ und $[2] \notin H$ Die Reihenfolge von $[2]$ ist streng größer als $34$. Auch mit dieser Tatsache und
$\quad [2]^{136} = [16]^{34} = [1]$
wir müssen daraus schließen, dass die Reihenfolge von $[2]$ entweder $68$ oder $136$.
Jetzt
$\quad [2]^{68} = [16]^{17} \ne [1]$
und wir schließen daraus, dass die Reihenfolge von $[2]$ ist $136$.
Methode 2
Schon seit $[2]^1, [2]^2, [2]^3 \notin H$ und $[2]^4 = [16] \in H$wir können die hier gefundene Gruppentheorie anwenden und daraus schließen, dass die Reihenfolge von$[2]$ ist $4 \times 34 = 136$.