Fermat's little theorem $a^y \pmod{p}$ when $y<p$

Question

I have a problem where I need to guess $425^{17} \pmod{541}$

$p=541$ is prime so, applying Fermat's little Theorem $a^{p-1} \equiv 1 \pmod{p}$ we got

$425^{540} \equiv 1 \pmod{541}$

But how should I continue?

I am trying $\frac{17}{540}= 0*540 + 17$ but nothing to do with this...

Answer 1

If you insist on doing it by hand, use repeated squaring (via a calculator for squaring and "remaindering" by $541$):

• $425^2 $ has remainder $472$ on division by $541$.
• So $425^4 = 272^2 \pmod{541}$ and that is again (by a standard calculator) equal to $433$.
• Hence $425^8 = 433^2 \pmod{541}$ which equals $303$.
• Hence $425^{16} = 303^2 \pmod{541}$, and this is $380$.
• So finally $425^{17}= 425 \cdot 380 \pmod{541} = 282$.

Which Python will immediately compute (essentially via this same algorithm ) by pow(425,17,451), which is a bit easier.