How to solve exponential format modular equation have the same base

Question

I'm reading the paper of Taher Elgamal whichs talks about his digital signature scheme.

For example a user needs to sign a document $m \in [0, p-1]$ where $p$ is a large prime number. His private key is $x$ and the public key is $y \equiv \alpha ^{x} \pmod{p}$ where $\alpha$ is a primitive element mod $p$.

The signature of the document is a pair $(r, s)$ where $0 \leq r,s \leq q-1$ such that the equation $\alpha ^{m} \equiv y^{r}r^{s}$ is satisfied.

The signing procedure consists of 3 steps :

1. Choose a random number $k \in [0, p-1]$ such that $gcd(k, p-1) = 1$.
2. Compute $r \equiv \alpha ^{k} \pmod{p}$.
3. Rewrite $\alpha ^{m} \equiv y^{r}r^{s} \pmod{p}$ to $\alpha ^{m} \equiv \alpha ^{xr} \alpha ^{ks} \pmod{p}$.

Then the author said we can compute $s$ by using $m \equiv xr + ks \pmod{p-1}$.

Here is my question: Why it's $p-1$ now? I know that the equation has a solution for $s$ if and only if $gcd(k, p-1) = 1$, but how can we get $m \equiv xr + ks \pmod{p-1}$ from $\alpha ^{m} \equiv \alpha ^{xr} \alpha ^{ks} \pmod{p}$?

Thanks.

Answer 1

If $\alpha^m\equiv \alpha^n\pmod p $ where $m>n$ and $(\alpha,p)=1$

So, $\alpha^{m-n}\equiv1\pmod p \implies ord_p\alpha\mid(m-n)$ (Proof)

If $\alpha$ is is a primitive element $\pmod p, ord_p\alpha=p-1$