Finding common modulo

47 Views Asked by At

given these two modulo equations $c_1 = m_1^a (\mod n)$, $c_2 = m_2^a (\mod n)$

Where '$a$' is prime and $n$ is a product of two primes, and the only unknown is $n$, is it possible to solve for $n$? I thought maybe you would have to use the Chinese remainder theorem but I am not sure how to apply it here.

1

There are 1 best solutions below

1
On

$c_1 \equiv m_1^a \mod n$ says $n$ divides $m_1^a - c_1$. Similarly for $c_2 \equiv m_2^a \mod n$. So you want $n$ to divide $\text{gcd}(m_1^a - c_1, m_2^a-c_2)$. If there are two primes that do so, take their product.