What is the order of $\bar{2}$ in the multiplicative group $\mathbb Z_{289}^×$? What is the order of $\bar{2}$ in the multiplicative group $\mathbb Z_{289}^×$?
I know that $289 = 17 \times 17$
so would it be $2^8\equiv 256\bmod17 =1$
and therefore the order of $\bar{2}$ is $8$? I'm not too sure about this
 A: This can be done very easy mentally using only trivial calculations.
$\!\bmod 17\!:\,\ 2^4\equiv -1\,\Rightarrow\, 2^8\equiv 1\Rightarrow 2\,$ has order $\,\color{#c00}{o(2) = 8}\,$ by the Order Test.
$\!\bmod 17^2\!:\ n\!:=\!o(2)\Rightarrow\,2^n\equiv 1\,$ thus $\bmod 17\!:\ 2^n\equiv 1\,$ thus $\, \color{#c00}8\mid n\,$ so $\,n = 8k$.
$\!\bmod 17\!:\ 2\equiv 6^2$ thus $\,2\,$ is a $\rm\color{#0a0}{square}\bmod 17^2\:\!$ too, so $\,o(2)=8k\mid \phi(17^2)/\color{#0a0}2 = 8\cdot 17$.
So $\,k\!=\!1$ or $17.\,$ But $\,k\!\neq\! 1\,$ by $\,2^8\!\equiv\! 256\!\not\equiv \!1\pmod{\!289}\,$ so $\,k\!=\!17,\,$ so $\,o(2)\! =\! 8(17)\!=\!136$.
A: No.
The order of $\bar 2$ in $\mathbb Z_{17}^\times$ is $8$ because $2^8\equiv1\pmod{17}$.
However, $2^8\not\equiv1\pmod{289}$, so $8$ is not the order of $\bar2$ in $\mathbb Z_{289}^\times$.
The order of $\bar 2$ in $\mathbb Z_{289}^\times$, i. e. the smallest positive integer $k$ such that $2^k\equiv1\pmod{289}$, is $136$. (I used my computer to get this.)
Fact:
Let $\operatorname {ord}_n(a)$ be the order of $\bar a$ in $\mathbb Z_{n}^\times$. Then, for prime $p$ and positive integers $k<l$,
$$
\operatorname {ord}_{p^k}(a)\mid\operatorname {ord}_{p^l}(a).
$$
For example, $8\mid136$.
A: $256 \equiv 1 \pmod {17}$ but $256\not \equiv 1 \pmod {289}$ which we need.
But not $289 = 17\times 17$ so $\phi (289) = 17\cdot16$ so $2^{17\cdot 16}\equiv 1\pmod {289}$ by Eulers theorem.
But the order might be something smaller that divides $17\cdot 16$.
We can figure that $2^8 = 17*15 + 1 \equiv 17*(-2) + 1\pmod{17^2}$ so
$2^{16} \equiv 17^2 *4 + 2*(-2)*17 + 1 \equiv -67 \pmod {289}$.
So the order of $2$ is not $16$ and thus not anything that divides $16$.  So the order of $2$ will be a multiple of $17$.  be a multiple of $17$ that divides $16*17$.
And $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}$.
And so $2^{8*17}\equiv (-1)^2 \equiv 1 \pmod {289}$.
So the order of $2$ is $8*17= 136$.
A: $2^8\equiv1\bmod17$, so
$2^{128}+2^{120}+2^{112}+\cdots+2^{16}+2^{8}+1\equiv1+1+1+\cdots+1+1+1=17\equiv0\bmod17,$
so $2^{136}-1=(2^{128}+2^{120}+2^{112}+\cdots+2^{16}+2^{8}+1)(2^8-1)\equiv0\bmod289$,
but $2^8-1=255\not\equiv0\bmod289$,
and $2^{68}-1\not\equiv0\bmod289$ because $2^{68}-1\equiv2^4-1=15\not\equiv0\bmod17$,
so, by the order test (linked in Bill Dubuque's answer), the order of $2$ mod $289$ is $136$.
A: Define the set $H \subset {\displaystyle (\mathbb {Z} /289\mathbb {Z} )^{\times }}$ by
$\tag 1 H = \bigr\{[a + 17m] \,\large \mid \, \normalsize  a \in \{-1,+1\} \text{ and } 0 \le m \lt 17\bigr\}$
It is easy to show that $H$ contains exactly $34$ elements.
Proposition 1: The set $H$ is closed under multiplication.
Proof
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$.
