Find remainder of $\frac{17^{235}}{ 23}$

Question

I need to find remainder of $\frac{17^{235}}{ 23}$.

This is supposed to be solved using the following method:

1. $\varphi(23) = 22$
2. ${17}^{235} = (({17}^{22})^{10})\cdot {17}^{15}$
3. ${17}^{22}\equiv 1 \pmod{23}$
4. Then, according to Euler theorem, $17^{235} \equiv 17^{15} \pmod {23}$

and then i get stuck.

Answer 1

$17^{15}= 17^1\times 17^2\times17^4\times 17^8$. In the rhs every term is the square of the previous term.

$17^2=289=230+69-10\equiv \mathbf{-10}\pmod{23}$.

$17^4\equiv(-10)^2=100\equiv\mathbf{8}\pmod{23} $

$17^8\equiv 8^2=64\equiv\mathbf{-5}\pmod{23} $

Now multiply $17.(-10).8.(-5)\equiv\mathbf{-8}\pmod{23}$

The answer is 15.

The answer is 15.

Answer 2

You can, by fast exponentiation, check that $17^{11}\equiv-1\mod 23$. Thus, as $23$ is prime, Little Fermat entails that: $$17^{235}\equiv17^{235\bmod22}= 17^{15}\equiv -17^4=-(17^2)^2\equiv-13^2\equiv -8\equiv 15.$$

Answer 3

Ingenuity and persistence help. Since $23+1=24$ has a good number of factors, some negative numbers and negative exponents are easy to determine. Also, though I don't use it below, $70\equiv 1$ could be useful in determining multiplicative inverses. Here is an illustration of how it works (I've left out some of the details, but put in more than the base calculations.)

$17\equiv -6$ and $17^{22}\equiv 1$ so that $17^{21}\equiv -4$ (since $-4\times -6=24\equiv 1$)

Also $17^3\equiv-6^3=-216\equiv 14$ and $17^6\equiv 196 \equiv 12$ and $17^{-6}=2$

Whence $17^{21-6}\equiv -4\times 2\equiv -8\equiv 15$