1

How do I calculate $$ 25·41^{16} \bmod 17 $$

using Fermat's little theorem? More specifically, how do I find an $x$ such that $$ x \equiv 25·41^{16}\bmod 17 $$

One part of Fermat's theorem states that, if $p$ is a prime number and $a$ is an integer such that $a\nmid p$, then $a^p \equiv a\bmod p$. I was thinking of taking $a = 25·41^{16}$ and thus $(25·41^{16})^{17} \equiv 25·41^{16} \bmod 17$, but then you would have to do the multiplication, calculate the power, and then calculate the $\text{mod}$; but only Fermat's little theorem must be used: if we have to do these extra calculations anyway, why even use it?

Any help/hints would be appreciated.

Gary
  • 31,845
human bean
  • 113

1 Answers1

2

Actually, the hypothesis of Fermats little theorem is that $p\nmid a$, not $a\nmid p$ as you wrote. Given this hypothesis, Fermats little theorem says that $a^{p-1} \equiv 1$ mod p.

The equivalence you stated:

$a^p \equiv a$ mod $p$

holds for any prime $p$ and integer $a$, even when $p|a$. From what i've seen, it is usually stated as a corollary to Fermats little theorem.

Now, since $p$ is prime, $p \nmid a$ implies that $gcd(p,a)=1$ and thus $a$ has a multiplicative inverse mod p. Thus we can multiply both sides of

$a^p \equiv a$ mod p

by $a^{-1}$ to get

$a^{p-1} \equiv 1$ mod p

In our case, we can see that $17 \nmid 41$, and thus Fermat's little theorem gives us the follow congruence:

$41^{16} \equiv 1$ mod 17.

And thus:

$(25·41^{16}) \equiv 25·1 \equiv 8$ mod 17