Saturday, July 9, 2016

elementary number theory - 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.


Answer




$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.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...