# Fermat's Little Theorem: $r \equiv s \pmod {p-1} \implies a^r \equiv a^s \pmod p$

An implication of Fermat's Little Theorem is the following:

If $$p$$ is prime, and $$a$$ is not a multiple of $$p$$, then $$r \equiv s \pmod {p-1} \implies a^r \equiv a^s \pmod p.$$

I need this implication to prove the verification of the Elgamal signature, but I honestly do not see how to derive from Fermat's Little Theorem to this implication and I could not find any proof of this.

Any help would be much appreciated!

Assume without loss of generality that $r\geq s$, so $r=s+k(p-1)$ for some $k\geq 0$. Then $a^r=a^sa^{k(p-1)}$. Can you see how to get from here to what you want?
• Yes, because $a^{k(p-1)}= a^{(p-1)^k} = 1^k = 1$. Thank you! – Joey Jun 10 '18 at 10:22