1
$\begingroup$

I tried to solve this 2 questions but without a success:

  1. Is $13$ a sixth power modulo $289$?
  2. Find all the solutions of $x^{8}\equiv 3\mod 13$

In question 1, I tried to see if $13$ is a quadratic residue modulo $289$, but we didn't learn how to do it (I know how to do it only modulo primes), I would like to get help and ideas of how to solve this question.

$\endgroup$
  • $\begingroup$ $289 = 17^2$. If $13$ is a quadratic residue modulo $289$, then it also is a quadratic residue modulo $17$ ($x^2 \equiv 13 \pmod{289} \implies x^2 \equiv 13 \pmod{17}$). If you have never heard of Hensel lifting, that might still give you an idea how to check whether $13$ is a quadratic residue modulo $289$. $\endgroup$ – Daniel Fischer May 15 '15 at 21:47
  • $\begingroup$ The answer to (1) is yes, but you're not going to find it by accident. $66^6\equiv 223^6\equiv 13 \bmod 289$. It seems odd to choose $289$ for this exercise when $6 \nmid (17-1)$, so the proof is more difficult (although that judgement depends what tools you have available for modular exponentiation). $\endgroup$ – Joffan May 15 '15 at 22:30
1
$\begingroup$

For (1), see Hensel's Lemma. You can also do it explicitly: first find a solution $x$ mod $17$, then try $y$ where $y = x + 17 t$.

$\endgroup$
1
$\begingroup$

2) $x^8\equiv 3 \implies x^4\equiv \pm 4 \equiv \{4,9\} \implies x^2 \equiv \{\pm 2^*, \pm 3 \} \\ \implies x \equiv \{\pm 4,\pm 6 \} \equiv \{4,6,7,9 \} \bmod 13$

You only need to check around the first three multiples of $13$ to get squares, by symmetry. $\pm 2$ are not quadratic residues.

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