# Find all solutions of $7x^2 \equiv 1 \pmod {17}$

Find all solutions of $7x^2 \equiv 1 \pmod {17}$

I found out all the primitive root of $U_{17}$ to be : $\{3,5,6,7,10,12,14\}$.

To continue with the computation, I think i need to use the theorem which is $x^2 \equiv1\pmod{n}$. But Im not sure how to connect it with the question?

Thanks!!

• Can a primitive root be a quadratic residue? – Yoni Rozenshein Mar 20 '13 at 22:41
• Quicker to use $5 \cdot 7 = 35 \equiv 1 \pmod {17}$ and find the square roots of 5. – Will Jagy Mar 20 '13 at 22:41

I would probably first get rid of the $7$, by multiplying by the inverse of $7$ modulo $17$. Note that $(5)(7)=35\equiv 1\pmod{17}$. So our congruence can be rewritten as $x^2\equiv 5\pmod{17}$.

There will be $0$ or $2$ solutions. You can search, it is short, since we really only have to try $x=1$ to $8$. If none of these work, nothing can work. And if among these you find an $a$ such that $a^2\equiv 5\pmod{17}$, then $-a$, also known as $17-a$, will be the other solution.

Or you can use machinery such as Quadratic Reciprocity, if that has been done, and save yourself the (minor) trouble of searching for a solution when in fact there isn't one.

If you already happen to have a list of primitive roots, then you can notice that $5$ is one of them, so is not a quadratic residue. If you have a single primitive root, you can calculate its even powers, and find that $5$ does not occur.

• Very detailed, thanks!! – Paul Mar 20 '13 at 22:59

Note that $5 \cdot 7 \equiv 1 \pmod {17}$, so you are solving $x^2 \equiv 5 \pmod {17}$.

Now $5$ is not a quadratic residue modulo $17$, as $5^{(17-1)/2} = 5^8 \equiv - 1 \pmod {17}$.

Hint $\rm\ mod\ 17\!:\ 1/7 \equiv 5\:$ is not a square by Euler's Criterion, since

$$\rm 5^8 \equiv (25)^4 \equiv (2^3)^4\equiv (2^4)^3 \equiv (-1)^3 \equiv -1$$

$$7x^2 \equiv 1 \pmod{17} \implies x^2 \equiv 7^{-1} \pmod{17} \implies x^2 \equiv 5 \pmod{17}$$ When $(x,17) = 1$ from little-Fermat, we have $$x^{16} \equiv 1 \pmod{17}$$ But we also need $x^2 \equiv 5 \pmod{17}$. This means $$x^{16} = {x^2}^8 \equiv 5^8 \pmod{17} \equiv (25)^4 \pmod{17} \equiv 8^4 \pmod{17} \equiv (64)^2 \pmod{17}$$ $$(64)^2 \pmod{17} \equiv 13^2 \pmod{17} \equiv 169 \pmod{17} \equiv -1 \pmod{17}$$ contradicting little-Fermat.