Find all incongruent solutions to this equation

431 Views Asked by At

Find all incongruent solutions to $$11x^{33} \equiv 2 \pmod{17} $$

2

There are 2 best solutions below

0
On

Observe \begin{align} 11a\equiv 1 \mod 17 \ \ \Rightarrow \ \ a \equiv 14 \mod 17 \end{align} which means \begin{align} x^{33}\equiv 11 \mod 17. \end{align} Using Euler's theorem, we have that \begin{align} x^{33}\equiv x \equiv 11 \mod 17. \end{align}

1
On

$x^{16}\equiv1 \pmod {17}$ by Fermat's little theorem. (unless $x$ is a multiple of $17$, but this case obviously doesn't generate solutions to the problem at hand).

So $11x^{33}\equiv11x \equiv2\pmod {17}$

$x\equiv\frac{2}{11}\equiv\frac{2}{-6}\equiv-\frac 13 \equiv \frac{33}{3}\equiv11 \pmod {17}$

So the solutions are $x=11+17k$