# 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?

• Without any clue about how $c_1$ and $c_2$ have been computed, it's hard to tell. Dumping homework here is not a good idea anyway.
– fgrieu
Apr 12 '20 at 9:55
• @fgrieu updated with a link to the post, $c_1$ and $c_2$ are there. The post is very short Apr 12 '20 at 9:57

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$$.

• I'm sure I'm missing some math here. Could you explain why "it follows that one of the following holds"? Apr 15 '20 at 12:55
• @tasera: We proved that $q$ divides $z$. It is known that $n=p\,q$ with $p$ and $q$ primes. $z=0$ is a possibility matching the above. Otherwise, for $z\ne0$, we can define and compute $g=\gcd(z,n)$. Since $g$ divides $n$ by definition of $\gcd$, it is one of $1$, $p$, $q$, or $n$. Since $q$ divides $n$ and $z$, and $1<q$, we can't have $g=1$. If we had $g=p$, and $p\ne q$, both $p$ and $q$ would divides $z$, hence $n$ would divides $z$, hence $g\ge n$, thus $g\ne p$. That leaves $q$ and $n$ as the only possibilities for $g$. Thus one of $z=0$, $g=q$, $g=n$ holds, as stated in the answer.
– fgrieu
Apr 15 '20 at 14:02