# Solve the special congreuences equation?

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.

example:

$\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.$
• 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.\$ – Math Gems Apr 11 '13 at 4:03
• 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... – Easy Apr 11 '13 at 4:59