1
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Hint: for $n$ prime to $55$, it may be more useful to use the fact that $n^{10}\equiv 1 \pmod {11}$. $\endgroup$
    – lulu
    Commented Mar 20, 2017 at 16:45
  • $\begingroup$ @lulu What do you mean? The congruence is based on mod 55 not mod 11 $\endgroup$ Commented Mar 20, 2017 at 16:51
  • 1
    $\begingroup$ 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. $\endgroup$
    – lulu
    Commented Mar 20, 2017 at 16:54
  • $\begingroup$ @lulu Thank you very much! $\endgroup$ Commented Mar 20, 2017 at 17:03

5 Answers 5

1
$\begingroup$

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)

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

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

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .