Find remainder of $\frac{17^{235}}{ 23}$ I need to find remainder of $\frac{17^{235}}{ 23}$.
This is supposed to be solved using the following method:


*

*$\varphi(23) = 22$

*${17}^{235} = (({17}^{22})^{10})\cdot {17}^{15}$

*${17}^{22}\equiv 1 \pmod{23}$

*Then, according to Euler theorem, $17^{235} \equiv 17^{15} \pmod {23}$


and then i get stuck.
 A: $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.
A: 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$
A: 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.$$
