Solve congruence with gcd In a solution to the problem of finding $q$ in

$$
c_1^{e_2}\cdot 5^{e_1e_2} - c_2^{e_1}\cdot 2^{e_1e_2} = q^{e_1e_2} \bmod n
$$

it is given as:

$$
q = \gcd\big(c_1^{e_2}\cdot 5^{e_1e_2} - c_2^{e_1}\cdot 2^{e_1e_2}, n\big)
$$

How can $q$ be found like that?
The way $c_1$ and $c_2$ have been obtained, algebra has shown that the quantity $z={c_1}^{e_2}\,5^{e_1\,e_2}-{c_2}^{e_1}\,2^{e_1\,e_2}$ is such that $z\equiv q^{e_1\,e_2}\pmod n$, where $n$ is an RSA modulus with $q$ one of the prime factors of $n$, $e_1$ and $e_2$ are RSA exponents valid for the modulus $n$.

From $n=p\,q$, we know that $q$ divides $n$.

From $z\equiv q^{e_1\,e_2}\pmod n$, and since $q$ divides $n$, we know that $z\equiv q^{e_1\,e_2}\pmod q$. Since neither $e_1$ nor $e_2$ are zero, it holds $q^{e_1\,e_2}\equiv0\pmod q$. Therefore, $z\equiv0\pmod q$, that is $q$ divides $z$.

Hence, $q$ is a common divisor of $n$ and $z$. With $n=p\,q$ with $p$ prime, it follows that one of the following holds:


$z=0$
$\gcd(z,n)$ is $q$
$\gcd(z,n)$ is $n$.


The way $z$ was constructed gives no particular reason to believe that $p$ divides $z$, and that's highly unlikely for a random integer. It follows that $\gcd(z,n)=q$ is the only likely possibility in the above three. 

The quantity ${c_1}^{e_2}\,5^{e_1\,e_2}-{c_2}^{e_1}\,2^{e_1\,e_2}\bmod n$ can efficiently be computed from givens, and that allows to compute $\gcd(z,n)$ (since the first step of that can be to reduce $z$ modulo $n$), and thus allows to compute $q$.