$n^{41}\equiv n\bmod 55$ by Fermat's little theorem

Question

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?

Answer 1

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.

Answer 2

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)

Answer 3

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.

Answer 4

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

Answer 5

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