# $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?

• Hint: for $n$ prime to $55$, it may be more useful to use the fact that $n^{10}\equiv 1 \pmod {11}$.
– lulu
Commented Mar 20, 2017 at 16:45
• @lulu What do you mean? The congruence is based on mod 55 not mod 11 Commented Mar 20, 2017 at 16:51
• Yes, but as you correctly remark it suffices to address the issue mod $5$ and $11$. Or at least that's how I interpreted your introduction of $11$. In any case, it does suffice to work mod those two primes, by the Chinese Remainder Theorem.
– lulu
Commented Mar 20, 2017 at 16:54
• @lulu Thank you very much! Commented Mar 20, 2017 at 17:03

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)

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}$

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$.

• This answer is mathematically correct, and offers a simple solution that none of the existing answers did. What is the reason for the downvote? Commented Aug 29, 2017 at 9:20

You use the Chinese Remainder Theorem:

$$$$\begin{cases} n^{41}\equiv n \mod(11)\\n^{41}\equiv n \mod(5) \end{cases}$$$$

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{cases} n^{4\phi(11)+1}\equiv n \mod(11)\\n^{10\phi(5)+1}\equiv n \mod(5) \end{cases}$$$$

$$$$\begin{cases} n^{4\cdot10+1}\equiv n \mod(11)\\n^{10\cdot4+1}\equiv n \mod(5) \end{cases}$$$$

Which gives you the result.

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.