# What's the remainder of a natual number divided by lcm(m,n)?

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)}$

-
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

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$

-
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).

-
Thank you, I have improved my question. – Popopo Apr 6 '13 at 8:18