$n^{41}\equiv n\bmod 55$ by Fermat's little theorem 
Knowing that $p$ is prime and $n$ is a natural number show that
  $$n^{41}\equiv n\bmod 55$$
  using Fermat's little theorem
  $$n^p\equiv n\bmod p$$

If the exercise was to show that
$$n^{41}\equiv n\bmod 11$$ I would just rewrite $n^{41}$ as a power of $11$ and would easily prove that the congruence is true in this case but I cannot apply the same logic when I have $\bmod55$ since $n^{41}$ cannot be written as power of $55$.
Any hint?
 A: You have two Fermat's Little Theorem results that you can use:
$$n^5 \equiv n \bmod 5 \\ n^{11} \equiv n \bmod 11  $$
Then successive application of these - for example, $n^9 \equiv n^5n^4 \equiv n\cdot n^4 \equiv n^5 \equiv n \bmod 5$ - gives 
$$n^{41} \equiv n \bmod 5 \\ n^{41} \equiv n \bmod 11  $$
And the Chinese reminder theorem gives 
$$n^{41} \equiv n \bmod 55 $$
as required.
(Note that you can also show $n^{21} \equiv n \bmod 55$, foreshadowing Carmichael's theorem)
A: Since $n^{10} \equiv 1 \pmod{11}$ Then $n^{10\cdot k} \equiv 1 \pmod{11}$ 
Thus for $k=4 \Rightarrow n^{40} \equiv 1 \pmod{11}$ then $n \equiv n^{41} \pmod{11}$ (using Fermat Little's).
For modulus $55$ you can use the fact that $55=11.5$ so:
$n^{11} \equiv n \pmod{11}$ and $n^{5} \equiv n \pmod 5$
Then regroup using CRT for modulo $55$:
$45n + 11n \equiv 56n \equiv n \pmod{55}$
A: Actually the chinese remainder theorem is unnecessary here.
$n^{41} \equiv n \pmod{5}$ and hence $n^{41}-n = 5c$ for some integer $c$.
$n^{41} \equiv n \pmod{11}$ and hence $11 \mid n^{41}-n = 5c$.
$11$ is prime and does not divide $5$, so by Euclid's lemma $11 \mid c$.
A: You use the Chinese Remainder Theorem:
$$\begin{equation}
   \begin{cases}
   n^{41}\equiv n \mod(11)\\n^{41}\equiv n \mod(5)
   \end{cases}
\end{equation}$$
Now you can apply the Fermat's little theorem, using the fact that $n^{\phi(n)}\equiv1 \mod(p)$  (Euler's Theorem) to obtain:
$$\begin{equation}
   \begin{cases}
   n^{4\phi(11)+1}\equiv n \mod(11)\\n^{10\phi(5)+1}\equiv n \mod(5)
   \end{cases}
\end{equation}$$
$$\begin{equation}
   \begin{cases}
   n^{4\cdot10+1}\equiv n \mod(11)\\n^{10\cdot4+1}\equiv n \mod(5)
   \end{cases}
\end{equation}$$
Which gives you the result.
A: We have


*

*mod $\ \ 5:\quad$ $n^{41} \equiv (n^8)^5n \equiv n^8 n \equiv n^9 \equiv n^5 n^4 \equiv n n ^4 \equiv n^5 \equiv n$

*mod $11:\quad$ $n^{41} \equiv (n^3)^{11} n^8 \equiv n^3 n^8 \equiv n^{11}  \equiv n$
Now apply the Chinese reminder theorem.
