the following congruencies

$\begin{matrix} x_1\equiv1~(\mod m_1)\\ x_2\equiv1~(\mod m_2)\\ \vdots\\ x_n\equiv1~(\mod m_n)\\ \end{matrix}$

where $m_i, m_j(i\neq j)$ are pairwise coprime. Now, I known the value of $x_i(i=1~\text{to}~n)$ and $s = \prod\limits_{i=1}^n m_i$. Any algorithm can calclute the value of $m_i(i=1~\text{to}~n)$? The value of $m$ and $x_i$ may be vary large.


$\begin{matrix} 2338762918 \equiv 1~(\mod m_1)\\ 1299869595 \equiv 1~(\mod m_2) \end{matrix}$ and $m_1\times m_2=99221$, the answer $m_1=317, m_2=313$. But this $m_i$ and $s$ is too small, many algorithms can do this.

I have found the method to solve this problem with the help of @Math Gems. Tks very much.

The useful Corollary described as follow. The original problem had ignore a important condition $\gcd(x_i-1,s/m_i)=1$ for $i=1$ to $n$.

Assume that $\{m_i\}_{i=1}^n$ are n pairwise coprime positive integers, $s = \prod\limits_{i=1}^n m_i$, $x_i\equiv 1\pmod{m_i}$. If $\gcd(x_i-1,s/m_i)=1$, then $m_i=\gcd(x_i,s)$.


Hint $\ $ If $\rm\:(x_i\!-\!1)/m_i\:$ is coprime to the other moduli then you can recover the moduli $\rm\: m_i\:$ by taking gcds, e.g. in your example $$\begin{eqnarray}\rm gcd(2338762918\!-\!1,99221)\!\! &=& 317\\ \rm gcd(1299869595\!-\!1,99221)\!\! &=& 313\end{eqnarray}$$

If that does not hold true, then the problem may require factorization, e.g. in the worst case $\rm\:x_i = 1+ m_1\cdots m_n\:$ which yields no gcd splittings of $\rm\: s = m_1\cdots m_m,\:$ so the problem reduces to factoring $\rm\:s.$

  • $\begingroup$ but when the numbers go large, there would be many possible combinations. How do you know which one will work? $\endgroup$ – Easy Apr 11 '13 at 3:51
  • $\begingroup$ Such combinatorics seems inherent in the problem, e.g. if $\rm\:x_i = 1 + m_1\cdots m_n\:$ then it reduces to a pure factoring problem. On the other extreme, if $\rm\: (x_i\!-\!1)/m_i\:$ is coprime to the other moduli, then gcds immediately yield the $\rm\:m_i.\ $ $\endgroup$ – Math Gems Apr 11 '13 at 4:03
  • $\begingroup$ @Easy But it is if you want to find all solutions. $\endgroup$ – Math Gems Apr 11 '13 at 4:28
  • $\begingroup$ the problem is if you find a possible combination $(m_1,\cdots,m_n)$ from $x_1-1$, this combination might not satisfy $m_2|x_2-1$, etc... $\endgroup$ – Easy Apr 11 '13 at 4:59
  • $\begingroup$ @Easy I don't see why you think that is related to what I wrote. $\endgroup$ – Math Gems Apr 11 '13 at 5:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.