Find all the $16^{th}$ roots of $2 \bmod 178481$

Find all the $16^{th}$ roots of $2 \bmod 178481$.

I tried to solve it by the Chinese Remainder Theorem.

Solution 1:

Extended hints/steps:

1. Prove that $p=178481$ is a prime.
2. Factor $p-1=2^4p_1p_2p_3$, where $p_1<p_2<p_3$ are three distinct odd primes.
3. Check that $2^{p_2}\equiv1\pmod p$. Why does this prove that $2$ is a sixteenth power modulo $p$? Why does this, together with step 2, prove that there are sixteen distinct solutions.
4. Show that $9p_2+1=16k$ for some integer $k$.
5. Why does that show that $x=2^k$ satisfies the congruence $x^{16}\equiv2\pmod p$?
6. Find a primitive sixteenth root of unity $w$ modulo $p$. Hint: for any integer $a, \gcd(a,p)=1$, we have that $a^{p_1p_2p_3}$ is a sixteenth root of unity modulo $p$. The catch is to find a primitive one by testing various values of $a$. In the interest of not being too cruel I will tell you that a choice $a, 0<a<5$, will work.
7. Show that all the pairwise non-congruent solutions are $xw^i$, $i=0,1,\ldots,15$.

I hope you can use a CAS. Otherwise you are gonna have a long night. Step six in particular may be time consuming - the others are relatively quick to do. Unless you come up with something more clever that is.

Solution 2:

$p = 178481\,$ is prime. $ $ mod $\,p\!:\ 2$ has order dividing $\,p\!-\!1 = 16\cdot 11155.$ By CAS $\,2^{11155}\equiv 1.\,$ By Bezout, ${\rm mod}\ 11155\!:\ 1/16 \equiv 3486.\,$ Thus $\ {\rm mod}\ p\!:\ 2^{1/16}\equiv 2^{3486}\equiv 8192\equiv 2^{13}$

Thus the $16$'th roots of $\,2\,$ are $2^{13} w^k\,$ for a primitive $16$th root of unity $w$. Find one by randomly searching for a nonsquare $\,a\,$ (i.e. $\,a^{(p-1)/2}\not\equiv 1),\,$ then computing $\,w = a^{11155}$

Remark $\ $ Above we exploited the fact that it is easy to compute $k$'th roots in groups whose order is coprime to $k$. More generally one may apply generalizations of the Shanks or Tonelli square-root algorithm., e.g. see Section 3.2: Extensions of Shanks's algorithm to r'th roots in cyclic groups in Lindhurst: Computing roots in finite fields and groups, with a jaunt through sums of digits. One can also generalize the Euler criterion for square-roots - see my post here and Chapter 4 of Ireland and Rosen, A Classical Introduction to Modern Number Theory.