How to find a number $n$ when $n$ mod $n_1$ and $n$ mod $n_2$ is given?

Question

For example: suppose we need to find x given that x mod 7 = 5 and x mod 13 = 8.

x = 47 is a solution but needs hit and trial.

Is there any shortcut to calculate such number?

Answer 1

In general, if we are taking the moduli of pairwise coprime integers greater than $1$, then you can use the Chinese remainder theorem.

However for the case above, I will consider the definition of modular equivalence. That is, two integers are said to be congruent modulo $n$ if $n$ is a divisor of their difference.

$$x \equiv 5\pmod{7}\implies x=5+7k_{1}$$

for $k\in\mathbb Z$ and substituting into the second equation we obtain

$$x\equiv 8\mod{13}\implies5+7k_{1}\equiv8\mod{13}$$ $$\implies7k_{1}\equiv 3\pmod{13}$$

and then note that $7^{-1}\equiv 2\pmod{13},$ indeed $14\equiv 1\pmod{13}$. To compute these values, you can either use the Extended Euclidean algorithm or Euler's theorem.

Then we have

$$7k_{1}\equiv 3\pmod{13}$$ $$2\cdot 7k_{1}\equiv 2\cdot3\pmod{13}$$ $$k_{1}\equiv6\pmod{13}\implies k_{1}=6+13k_{2}$$

for $k_{2}\in\mathbb{Z}$ and substituting for $k_{1}$ we obtain the solutions to be given by

$$x=5+7k_{1}=5+7\left(6+13k_{2}\right)=47+91k_{2}$$

or $$x\equiv 47\pmod{91}$$

Answer 2

There exist a lot of ways to do this :

• Sequentially try values of $x$ (basic, 47 guesses maximum)
• Use the lowest congruence and work up in sequence( meh,13 guesses maximum )
• Use the highest congruence and work down sequence (okay 7 guesses maximum)
• Note if $x$ is odd the first congruence can only work at even multiples of $7$, and the second only at odd multiples of $13$. (cool)
• Use Chinese remainder theorem or extension ( typical)

Answer 3

$x=\frac{5*13+8*7}{7+13}=121/20=121*41=47\mod{(7*13)}$

$x=m_1\mod{n_1}$
$x=m_2\mod{n_2}$
$x=m_3\mod{n_3}$
...
$x=m_n\mod{n_n}$

$$x=\frac{m_1/n_1+m_2/n_2+m_3/n_3+...m_n/n_n}{1/n_1+1/n_2+1/n_3+...1/n_n}\mod{(n_1*n_2*n_3...n_n)}$$