0
$\begingroup$

I wish to find all b such that $9x^8 \equiv b \pmod{17}$ has a solution using index arithmetic. I have figured out that 3 is a primitive root, giving:

$$\text{ind}_39+8\text{ind}_3x \equiv 2+8\text{ind}_3x \equiv \text{ind}_3b \pmod{16}$$

But, where can I go from here? A hint would be appreciated.

$\endgroup$
  • 1
    $\begingroup$ $$x^8\in\{-1,0,1\}\pmod{17},$$ can you guess why? $\endgroup$ – Jack D'Aurizio Dec 19 '17 at 2:26
  • $\begingroup$ No, can you explain further? $\endgroup$ – zz20s Dec 19 '17 at 2:27
  • $\begingroup$ en.wikipedia.org/wiki/Fermat%27s_little_theorem $\endgroup$ – DanielV Dec 19 '17 at 2:31
  • 1
    $\begingroup$ AH! Yes. Thank you. That clears it right up. Does anyone know of a way to salvage my approach, though? $\endgroup$ – zz20s Dec 19 '17 at 2:32
  • $\begingroup$ @zz20s: for any odd prime $p$ (and $17$ is an odd prime) $$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod{p}$$ is the Legendre symbol, which equals zero if $a$ is a multiple of $p$ and $\pm 1$ otherwise, according to $a$ being a quadratic residue $\!\pmod{p}$ or not. In particular the given problem has a solution iff $b\in\{0,8,9\}\pmod{17}$. $\endgroup$ – Jack D'Aurizio Dec 19 '17 at 2:34
1
$\begingroup$

Clearly, if $17|b,17\mid x$

otherwise,

$$\text{ind}_3b-2\equiv8\text{ind}_3x \pmod{16}\begin{cases}0 &\mbox{if } \text{ind}_3x \text{ is even}\iff b\equiv3^2\pmod{17} \\8& \mbox{if }\text{ind}_3x \text{ is odd}\iff b\equiv3^{8+2}\end{cases}$$

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