Find smallest $n$ such that $2^n \equiv 1 \pmod{51}$

Question

From Euler's Theorem, I know that $2^{32} \equiv 1 \pmod{51}$, since $\varphi(51) = 32$. But, is there a way to efficiently calculate the lowest power of $2$, so that it is still congruent to $1 \pmod {51}$? (I'm aware that it's $2^8$, by trial and error, I just don't understand the connection and efficient way to do this).

Answer 1

Hint $\bmod 17\!:\ 2^4\equiv \color{}{-1\not\equiv 1}\,$ so $\ 2^8\equiv 1,\,$ so $\,2\,$ has order $\,\color{}8\,$ by the Order Test.

Further $\bmod 3\!:\ 2^2\equiv 1\,\Longrightarrow\, 2^8\equiv 1\,$

Thus $\,3,17\mid 2^8-1\,\Rightarrow\, 51=3(17)\mid 2^8-1,\,$ so $\,2\,$ has order $8 \pmod {\!51}\ $ (it can't be $n<8$ else $2^n \equiv 1$ would also hold $\bmod 17$ contra above)

Remark $ $ Generally we can show $\,o_{mn}(a) = {\rm lcm} (o_m(a),o_n(a)),\,$ $\,o_n(a):= {\rm ord}(a)\pmod{\! n}\ $ for coprime $\,m,n,\,$ by using $\,\mathbb Z/mn\, \cong\, \mathbb Z/m \times \mathbb Z/n\,$ by CRT.

Answer 2

The efficient way uses the Chinese remainder theorem: it is the smallest exponent $n$ such that $n$ such that $2^n\equiv 1$ both $\bmod 3$ and $\bmod 17$, i.e. the l.c.m. of the smallest $n$s working mod. $3$ and mod. $17$.

For $3$ the answer is obvious : it is $n=2$. For $17$, it is a divisor of $16$, i.e. a power of $2$. Now $2^4\equiv -1\bmod 17$, so the corresponding $n$ is indeed $8$.