I am following the procedure described on p. 319 of the fourth edition of Douglas Stinson and (since that edition) Maura Paterson's Cryptography − Theory and Practice (IBSN 978-1-03-247604-9).
The context is recovery of the nonce $k$ in ElGamal signature in $\mathbb Z_p^*$, assuming nonce reuse. We have two message/signature pairs $\bigl(x_1,(\gamma,\delta_1)\bigr)$ and $\bigl(x_2,(\gamma,\delta_2)\bigr)$. It holds $\gamma=\alpha^k\bmod p$, $\delta_i=(x_i-a\gamma)k^{-1}\bmod(p-1)$ where $\alpha$ is a generator and $a$ is the private key.
We are in the sub-case of $d=\gcd(\delta_1-\delta_2,p-1)\ne1$. It's computed $x'=(x_1-x_2)/d$, $\delta'=(\delta_1-\delta_2)/d$, and $p'=(p-1)/d$.
Then the congruence $x_1-x_2\equiv k(\delta_1-\delta_2)\pmod{p-1}$ becomes:
$$x'\equiv k\delta'\pmod{p'}.\tag{1}\label{eq1}$$
Since $\gcd(\delta',p')=1$, we can compute
$$\epsilon=(\delta')^{-1}\bmod p'.\tag{2}\label{eq2}$$
The value of $k$ is determined modulo $p'$ to be
$$k=x'\epsilon\bmod p'.\tag{3}\label{eq3}$$
This yields $d$ candidate values for $k$:
$$k=x'\epsilon+ip'\bmod(p-1)\tag{4}\label{eq4}$$
for some $i,0\le i\le d-1$. Of these $d$ candidate values, the (unique) correct one can be determined by testing the condition
$$\gamma=\alpha^k\pmod p.\tag{5}\label{eq5}$$
I wrote a program that does all calculations with random parameters and notice that not always can I compute $k$ using the formula $\ref{eq4}$. Nevertheless, sometimes it does work. So I wonder if I am doing something wrong, or there is an assumption on the parameters that I am missing.
For example, taking $$p=157, k = 79, a = 139, \alpha= 70, \beta = 152, x_1 = 116, x_2 = 65, \gamma = 87, \delta_1 = 113, \delta_2 =140,$$ we have $d=3$ and the values returned by formula $\ref{eq4}$ are $0, 52, 104$, none of which is equal to $79$.
