Role of Fermat's little theorem in the proof of correctness of ElGamal signature
Thanks to fgrieu's comment above and the following quote from here (PDF):


  Theorem:
  
  Let $p$ be a prime and let $a$ be a number not divisible by $p$. Then if
  $$ r \equiv s \pmod {p − 1} $$
  we have
  $$ a^r \equiv a^s \pmod p$$ In brief, when we work $\mod p$, exponents can be taken $\mod{p − 1}$.


I (think i) understood, how the first (implicit) step relies on Fermat's little theorem:
$$\begin{align}
g^{H(m) \pmod{p-1}} &amp;= g^{xr+sk \pmod{p-1}} \\
g^{H(m)} &amp;\equiv g^{xr+sk} \pmod p
\end{align}$$