# Modular Binomial Problem

The solution to the problem of finding the primes $$p$$ and $$q$$ that have the following form:

$$c_1 = (a_1 p + b_1 q)^{e_1} \mod{N} \\ c_2 = (a_2 p + b_2 q)^{e_2} \mod{N}$$

Given the values of $$c_i$$, $$a_i$$, $$b_i$$, $$e_i$$ and $$N$$ where $$N = pq$$.

Can be found in this writeup online. I follow the solution right up to the very last line where the author concludes that from the expression.

$$a_2^{-e_1e_2}c_2^{e_1}-a_1^{-e_1e_2}c_1^{e_2}=a_2^{-e_1e_2}(b_2q)^{e_1e_2}+a_1^{-e_1e_2}(b_1q)^{e_1e_2} \mod{N}$$

We can find $$q$$ as:

$$q = \gcd\left( a_2^{-e_1e_2}c_2^{e_1} - a_1^{-e_1e_2}c_1^{e_2} \mod{N}, N \right)$$

Perhaps because the expression has gotten so unweildy I've missed something simple but this seems like such a massive leap and there is no additional explanation.

• $$a_2^{-e_1e_2}c_2^{e_1}-a_1^{-e_1e_2}c_1^{e_2}=a_2^{-e_1e_2}(b_2q)^{e_1e_2}+a_1^{-e_1e_2}(b_1q)^{e_1e_2} \mod{N}$$ $$a_2^{-e_1e_2}c_2^{e_1}-a_1^{-e_1e_2}c_1^{e_2}= q^{e_1e_2}\left( a_2^{-e_1e_2}(b_2)^{e_1e_2}+a_1^{-e_1e_2}(b_1)^{e_1e_2}\right) \mod{N}$$ $$a= q b \mod{N}$$ $$ab^{-1}= q \mod{N}$$ Oct 15, 2023 at 19:12
• @kelalaka Apologies for the topic necromancy, but I'm having a little bit of trouble seeing the relationship between your second line and your third. I see the format of $\textrm{expr} = \left(q^\textrm{exp}\right) \cdot \left(\textrm{expr}\right) \pmod{N}$, but I don't understand why the exponent on the $q$ can be dropped (or, honestly, how that results in a solution of $q$ being equal to a gcd). Apr 6 at 5:30
• @apnorton It is just renaming. Once you know $c_1, c_2, a_1, a_2, e_1, e_2, N$ then you have the $q$ Apr 6 at 19:20