Computing $7^{13} \mod 40$ I wanted to compute $7^{13} \mod 40$. I showed that 
$$7^{13} \equiv 2^{13} \equiv 2 \mod 5$$
and
$$7^{13} \equiv (-1)^{13} \equiv -1 \mod 8$$.
Therefore, I have that $7^{13} - 2$ is a multiple of $5$, whereas $7^{13} +1$ is a multiple of $8$. I wanted to make both equal, so I solved $-2 + 5k =  + 8n$ for natural numbers $n,k$ and found that $n = 9, k = 15$ gave a solution (just tried to make $3 + 8n$ a multiple of $5$. Therefore, I have that 
$$7^{13} \equiv -73 \equiv 7 \mod 40.$$
Is this correct? Moreover, is there an easier way? (I also tried to used the Euler totient function, but $\phi(40) = 16$, so $13 \equiv -3 \mod 16$, but I did not know how to proceed with this.)
 A: Yes, easier, by Fermat/Euler (or directly) $\ \color{}{7^{\large 4}\!\equiv 1}\,$ mod $\,5\,$ and $\,8,\,$ thus $\,5,8\mid 7^{\large 4}\!-1.\,$ 
Thus $\, {\rm lcm}(5,8)\!=\!40\mid \color{#c00}{7^{\large 4}\!-1}.\,$ So $\ {\rm mod}\ 40\!:\ 7^{\large 12}\!\equiv 7(\color{#c00}{7^{\large 4}})^{\large 3}\equiv 7(\color{#c00}1)^{\large 3}\equiv 7$
Remark $\ $ See Carmichael's Lambda Theorem for a general way to do this (it combines the Euler totient exponents for each prime power more efficiently using lcm, as done implicitly above).
A: You don't necessarily have to use the fact $40=8\times 5$ (but if you do, look up "Chinese remainder theorem".)

Otherwise, you know that 
$$7^2\equiv 49\equiv 9\pmod{40}.$$
So
$$7^3\equiv 63\equiv 23\pmod{40},$$
so
$$7^4\equiv 161\equiv 1\pmod{40}.$$
Then
$$7^{13}\equiv 7^{4\times 3}\times 7\equiv 1\times 7\equiv 7\pmod{40}.$$
A: The Carmichael function $\lambda$ is a stronger version of Euler totient function for this purpose which combines different prime factors by $\rm lcm$ rather than simple multiplication, and adjusts higher powers of $2$.
So $\lambda(40) = {\rm lcm}(\lambda(8),\lambda(5)) = {\rm lcm}(2,4) = 4$, and thus the cycle length of $7$ is divisible by $4$. Since $\gcd(7,40)=1$  and $13\equiv 1 \bmod 4$, this immediately gives $7^{13}\equiv 7 \bmod 40$.
A: $$\phi(40)=16 \to 7^{16}\equiv 1$$mod 40 $$7^{16}\equiv 1 \\7^{13}7^3\equiv 1\\
343.7^{13}\equiv 1 \\
(320+23).7^{13}\equiv 1\\
23.7^{13}\equiv 1\\
23.7^{13}\equiv 1+40 \equiv 1+80\equiv 1+120\equiv 1+160\\
23.7^{13}\equiv 161 \\23.7^{13}\equiv 7(23)$$ divide by $23$  , $(23,40)=1 
$
so 
$$23.7^{13}\equiv 7(23) \to 7^{13}\equiv 7$$
A: You could note that $\varphi(5) = 5-1 = 4$ and $\varphi(8) = 8- 4 = 4$. Hence $7^4 \equiv 1 \pmod 5$ and  $7^4 \equiv 1 \pmod 8$, in which case $7^4 \equiv 1 \pmod{40}$.
Hence $7^{13} \equiv (7^4)^3 \cdot 7 \equiv 7 \pmod{40}$.
