# Solving Non-Linear Congruences

I'm trying to solve an exercise from Niven I.M "An Introduction to Theory of Numbers" on page 106, problem 10. The problem wants you to find all the solutions to the congruence $$\begin{equation*} x^{12} \equiv 16 \quad (\text{mod }17) \end{equation*}$$ Here is my attempt;

First I found that $$3$$ is a primitive root in $$(mod 17)$$, i.e $$3^{16} \equiv 1 \quad (\text{mod }17)$$.

This means that we can write $$16 \equiv 3^{8} \quad (\text{mod }17)$$. So we have $$\begin{equation*} x^{12} \equiv 3^{8} \quad (\text{mod }17) \end{equation*}$$ Then multiplying the congruence by $$3^{16}$$ we see that $$\begin{equation*} x^{12} \equiv 3^{24} \quad (\text{mod } 17) \end{equation*}$$ We see that $$x=9$$ is a solution because $$9=3^2$$.

To find the remaining solution I think we need to have $$\begin{equation*} x^{12} \equiv 3^{8+16k} \quad (\text{mod }17) \end{equation*}$$ for $$k \in \mathbb{Z}/17\mathbb{Z}$$.

So we need $$12|(8+16k)$$. However, I'm not sure about my last argument that $$12|(8+16k)$$. Is it right or wrong? Any help is appreciated.

• Also $x=2$ and $x=8$ and $x=15$ are solutions. – Dietrich Burde Oct 11 '19 at 14:40
• $x=2,8,9,15$ are solutions. – Dr. Sonnhard Graubner Oct 11 '19 at 14:41
• How? Is my argument correct? – eloparti Oct 11 '19 at 14:46
• What is your argument? What has $k\in \Bbb Z/17$ to do with it? – Dietrich Burde Oct 11 '19 at 14:48
• In order to get other solutions, I need to have $12|(8+16k)$. These $k$'s will produce the remaining solutions right? – eloparti Oct 11 '19 at 14:50

$$k$$ would be in $$\mathbb{Z}$$ . You can Also note both 12 and $$16k+8$$ divide by 4. This means, 3 would need to divide $$4k+2$$. Using mod 3, we get $$k$$ congruent to 1 mod 3. $$k=1$$ gives a cube root of 9. $$k=4$$ gives 15, $$k=7$$ gives 8, and $$k=10$$ gives 2. You intuition works, but your reduction could have gone further.

$$x^{12}\equiv16\pmod{17}$$

$$\implies12\cdot$$ind$$_3x\equiv4\cdot$$idx$$_32\pmod{16}$$

$$\iff3\cdot$$ind$$_3x\equiv$$idx$$_32\pmod4$$

$$\iff$$ind$$_3x\equiv-$$idx$$_32\pmod4\ \ \ \ (1)$$ as $$3^{-1}\equiv-1\pmod4$$

Now $$3^2=9\equiv-8,3^4\equiv81\equiv-4,3^8\equiv16\equiv-1\pmod{17}$$

$$2\equiv-32\equiv3^{8+4+2}$$

By $$(1),$$ind$$_3x\equiv-14\pmod4\equiv2$$

$$\implies x\equiv3^{2+4k}\pmod{17}$$ where $$0\le1+4k\le16\iff0\le k\le3$$