Reduce $39^{13} \text{ (mod 55)}$ I am trying to reduce $39^{13} \text{ (mod 55)}$. I first tried taking successive powers of 39 to find some pattern:
$39^2\equiv36\text{ (mod 55)}$
$39^3\equiv29\text{ (mod 55)}$
$39^4\equiv31\text{ (mod 55)}$
$39^5\equiv54\text{ (mod 55)}$
$39^6\equiv16\text{ (mod 55)}$
$39^7\equiv59\text{ (mod 55)}$
$39^8\equiv46\text{ (mod 55)}$  
but it seems that it is not very helpful.
Also, 55 is composite, so we cannot make use of any theorem like Euler's Theorem.
I also tried factoring $39^{13}=3^{13}\times13^{13}$, but this way will make the calculation even longer.
Is there any better approach?
Many thanks for the help! 
 A: You missed a trick there. Note that,
$$39^5\equiv54 \equiv -1\pmod {55}$$
More generally, you can


*

*Factor the 55 into 11 and 5 and apply CRT. This is what Euler88 did.

*Factor 39 into 3 and 13 and calculate $13^{13},\    3^{13} \pmod{55}$
A: Note that $39^{13}\equiv -1 \pmod5$ and $39^{13}\equiv -4\pmod{11}.$
A: Following your route, you're almost done. Note that $39^{13} = 39^{8+4+1} = 39^8\cdot 39^4 \cdot 39$. Also, you didn't need any of $39^3, 39^5, 39^6$ nor $39^7$ to calculate this.
This is how computers usually calculate powers, it's a method called repeated squaring. We have $39^1 = 39$, and $39^2 \equiv 36$. Then $39^4 = (39^2)^2 \equiv 31$. Lastly $39^8 = (39^4)^2 \equiv 46$. Any power can be calculated this way, and you don't need to do very many calculations. Of course, the Chinese remainder theorem makes for a faster solution in this case; there are always tricks you can use. This method, however, doesn't rely on anything special about the numbers involved (like prime factorizations, or that $39^5 \equiv -1$) and that's why computers use it.
A: Here is a method a bit different from the one you suggested.
Since $55=5\times 11$ you can work modulo $5$ and $11$ to identify powers of $39$ which are easy to work with - ideally $\equiv \pm 1 \bmod 55$ but other small integers will do.
Now $39\equiv -1 \bmod 5$ so that $39^r\equiv (-1)^r\bmod 5$ and that is very easy to compute.
Modulo $11$ we know from little Fermat that $39^{10}\equiv 1 \bmod 11$ and also from the previous remark $39^{10}\equiv 1\bmod 5$ so that $39^{10}\equiv 1 \bmod 55$ (note that this doesn't need the full machinery of the Chinese Remainder theorem).
So $39^{13}\equiv 39^3 \bmod 55$
It might also help you to observe that $39\equiv -16$ and $39^2\equiv (-16)^2=256\equiv 36$ using the fact that $16^2$ is well known to those who know their powers of $2$.
Then $39^3\equiv 39\times 36 = 52 \times 27 \equiv -3\times 27 \equiv -81 \equiv 29$ (first find a factor near to $55$ or some multiple to simplify the arithmetic, then add $110$ for the last part)
A: Let's follow the pattern $39^5\equiv54\pmod{55}$:


*

*$39^5\equiv54\pmod{55}\implies$

*$39^5\equiv-1\pmod{55}\implies$

*$(39^5)^2\equiv(-1)^2\pmod{55}\implies$

*$39^{10}\equiv1\pmod{55}$


You've already noticed that $39^3\equiv29\pmod{55}$.
Hence $39^{13}\equiv39^{10}\cdot39^3\equiv1\cdot29\equiv29\pmod{55}$.
A: As $39\equiv-16\pmod{55},$
and as $16=-2^4,39^{13}\equiv(-16)^{13}$
Now $(-16)^{13}=-16^{13}=-(2^4)^{13}=-2^{52}$
Now using Carmichael function $\lambda(55)=\cdots=20,52\equiv12\pmod{20}$
$\implies-2^{52}\equiv-2^{12}\equiv-(2^6)^2\equiv-9^2\equiv29\pmod{55}$
A: Note that $55=5\cdot11$, so we can use Euler's theorem mod 5 and mod 11, and then use the Chinese Remainder Theorem:
$$39^{13}\equiv39^1{\pmod 5}\equiv4{\pmod5}$$
$$39^{13}\equiv39^3{\pmod {11}}\equiv7{\pmod {11}}$$
Now the Chinese Remainder Theorem says there is a unique integer(mod 5*11) that is equivalent to $4{\pmod 5}$ and to $7{\pmod {11}}$.  In this case, that integer is $29$, so $39^{13}\equiv29{\pmod {55}}$
