2
$\begingroup$

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!!

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

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.

$\endgroup$
1
  • $\begingroup$ Very detailed, thanks!! $\endgroup$ – Paul Mar 20 '13 at 22:59
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.