Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $x,m,n \in \mathbb N$, $m,n>0$,

and $x \equiv r \pmod m$,

$x \equiv s \pmod n$ ($r-s \equiv 0 \pmod{gcd(m,n)}$).

It seems $x \equiv r \equiv s \pmod {gcd(m,n)}$;

But $x \equiv ? \pmod {lcm(m,n)}$

share|cite|improve this question
Look at some data. Try various triples of numbers $(x, m, n)$, and try to formulate a conjecture. Then, prove it. – Sammy Black Apr 5 '13 at 16:55
Look at Chinese Remainder Theorem. – Thomas Andrews Apr 5 '13 at 16:55
up vote 1 down vote accepted

The general solution first requires that you solve the equation $mu+nv=\gcd(m,n)$.

Then the value is $$x\equiv \frac{(s-r)}{\gcd(m,n)}mu+r\pmod {lcm(m,n)}$$

That might seem a bit gross, but it is just an application of the Chinese Remainder Theorem. It obviously only works if $\gcd(m,n)|s-r$.

It's clear that this $x$ satisfies $x\equiv r\mod m$. substituting $mu=\gcd(m,n)-nv$ shows that $x\equiv s\pmod n$

share|cite|improve this answer
Yes, I understand. Thank you. – Popopo Apr 5 '13 at 18:28
@Popopo See my answer for a proof, and derivation of the above formula. – Math Gems Apr 5 '13 at 20:19

Existence: $\rm\ \ d = (m,n)\mid m\mid x\!-\!r,\ \ d\mid n\mid x\!-\!s\ \Rightarrow\ \color{#C00}{d\mid r\!-\!s}\, =\, x\!-\!s-(x\!-\!r)\:$ is necessary; $\ $ sufficient too: $ $ Bezout $\rm\,\Rightarrow\:\exists\,j,\,k\in\Bbb Z\!:\ kn-jm = r\!-\!s,\: $ so $\rm\ x = s+kn = r+jm\ $ is a solution.

Uniqueness: $\rm\:x,x'$ solutions $\rm\!\iff\! x'\equiv x\ mod\ m,n\!\iff\! m,n\mid x'\!-\!x\!\iff\! lcm(m,n)\mid x'\!-\!x.$

Construction: $ $ use the extended Euclidean algorithm to find $\rm\:u,v\in\Bbb Z\!:\ um+vn = d = (m,n)\:$ then multiply this equation by $\rm\:(r\!-\!s)/d,\:$ yielding $\rm\:kn-jm = r\!-\!s,\:$ then proceed as above. This yields the formula in the answer of Thomas (general CRT = Chinese Remainder Theorem).

share|cite|improve this answer
Thank you, I have improved my question. – Popopo Apr 6 '13 at 8:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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