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.
Best Answer
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