How can one show that an ElGamal-like signature verification scheme is valid?

For an ElGamal-like signature scheme, I am given two things:

1. The signing function,
2. the verification function.

How can I show that the verification function is valid?

Example 1:

Signing: $s := x^{-1}(m - k·r) \pmod {p - 1}$

Verification: $g^m = (g^x)^s · r^r \pmod p$

NOTES:

$g$ is the generator over the set $\mathbb Z^*_p$.

$x$ is the secret value, $g^x$ the public one.

$r := g^k \pmod p$

-
Your scheme is not the original ElGamal scheme, and I doubt that it is valid at all. First, ElGamal uses a hash of the message where you are using the message itself (which will make the scheme less secure, and only applicable for short messages, but verification should still work). Second, in the exponents of the verification you switched $s$ and $r$. Is this a typo (and you want actually a proof for the original ElGamal), or do you really search a proof for this modified scheme? –  Paŭlo Ebermann Nov 27 '11 at 13:23

Your scheme is not the "true" ElGamal signature scheme: you swapped $x$ and $k$. I assume that $m$ is the hash of the message to sign, not the message itself.
Your scheme is sound, which means that the verification algorithm will return "ok" for a signature which has been generated as you suggest. To see that, remember Fermat's Little Theorem which says that for a prime $p$ and every integer $a$ (not multiple of $p$), we have $a^{p-1} = 1 \pmod p$. This means that when dealing with exponents, we can compute them modulo $p-1$.