Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
2  
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

2 Answers 2

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|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|improve this answer
    
Thank you, I have improved my question. –  Popopo Apr 6 '13 at 8:18

Your Answer

 
discard

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.