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.

"If $a \equiv b \pmod m$ and $a \equiv b \pmod n$ and $gcd(m,n)=1$, then $a \equiv b \pmod {mn}$ "

Is that a true theorem? I can't find it in my textbook!

share|improve this question
6  
You should probably use a letter that isn't "o", which looks like $0$. –  Omnomnomnom Mar 25 at 13:22
    
But yes, it's true. –  Daniel Fischer Mar 25 at 13:23

6 Answers 6

This theorem can be seen as a particular instance of the Chinese remainder theorem. So yes, it is true.

share|improve this answer

See the Chinese Remainder Theorem.

share|improve this answer

Yes, $\ n,o\mid a\!-\!b\,\iff\, \color{#c00}{{\rm lcm}(n,o)}\mid a\!-\!b,\,$ and $\ \color{#c00}{{\rm lcm}(n,o) = no}\ $ by $\ \gcd(n,o)=1.$

Remark $\ $ Generally $\ {\rm lcm}(n,o) = \dfrac{no}{\gcd(n,o)}.\, $ While this can be deduced as a special case of the Chinese Remainder Theorem (CRT), generally lcm laws are more applicable, so it's essential to be familiar with basic lcm laws (the first $\iff$ above is the universal property of the lcm).

share|improve this answer
1  
Was it intentional that you wrote "n,o" immediately after "yes"? –  rah4927 Mar 25 at 18:19
    
@rah $\ y,e,s.\ \ $ –  Bill Dubuque Mar 25 at 18:23

Yes. This is just a special case of the Chinese Remainder Theorem

share|improve this answer

To counter a bit the many answers suggesting the contrary, this is true independently of the Chinese remainder theorem, which states that if $\gcd(m,n)=1$ then any pair of congruences $x\equiv a\pmod m$, $x\equiv b\pmod n$ has a solution for $x$. Of course the question bears some relation to CRT, but the result is more a preliminary to it: it shows that the solutions to such a pair of congruences occupy at most one congruence class modulo$~nm$. Indeed one can deduce the CRT from it by a counting argument: since there are $nm$ possible pairs of congruences, and as many classes modulo$~nm$, it must be that every pair of congruences admits a single class as solution. (Other proofs are more helpful for finding that solution.)

Given that $a\equiv b\pmod m$ and $a\equiv b\pmod n$, in other words that $a-b$ is a common multiple of $m$ and $n$, the essential property of the least common multiple (namely that it divides all other common multiples) says that $\def\lcm{\operatorname{lcm}}\lcm(n,m)\mid a-b$, in other words $a\equiv b\pmod{\lcm(n,m)}$. So all that is needed here is to check that $\lcm(m,n)=mn$, which clear from the general rule $\gcd(n,m)\lcm(n,m)=nm$ (or directly: since $nm$ is a common multiple of $n,m$ one has $\lcm(n,m)\mid nm$, and $nm/\lcm(n,m)$ then is a common divisor of $n,m$, hence divides $\gcd(n,m)=1$). This is the same as what Bill Dubuque says more succinctly.

To make point that this result is really independent of the CRT, all the above (and therefore the statement of the question) is valid more generally than in $\Bbb Z$. Namely, it is valid in all integral domains where a $\gcd$ and $\lcm$ of two elements always exists, so called GCD-domains; in particular it holds in any Unique Factorisation Domain like a ring of multivariate polynomials, even though the Chinese Remainder Theorem does not hold there. Of course this generality is superfluous if you are only interested in arithmetic of the the integers, but the only way I can argue convincingly that this is independent of CRT is to look at a situation the statement makes sense, but where CRT fails.

The mentioned essential property of $\lcm(n,m)$ is clear in $\Bbb Z$, since the set of common multiples of $n,m$ is closed under addition and subtraction, and therefore equal to the set of multiples of its least positive element, which is $\lcm(n,m)$. In more general settings where "least" has no obvious meaning, the property serves as definition of $\lcm(n,m)$, just like being a common divisor divisible by all other common divisors becomes the definition of $\gcd(n,m)$. Note that without any assumption other than working in an integral domain, these definitions do not ensure that $\lcm(n,m)$ or $\gcd(n,m)$ always exist; this is why I mentioned that the result does depend on the assumption that $\lcm(n,m)$ exists.

share|improve this answer
    
Actually, most statements of the CRT include both existence and uniqueness, i.e. $x\equiv a\pmod m$, $x\equiv b\pmod n$ has a unique solution $x\equiv y\pmod{mn}$, up to a multiple of $mn$, which is why everyone else is calling the uniqueness part a corollary of the CRT. Also, I think the term "independent of" the CRT is misused, since it is implied by CRT (independence means neither theorem implies the other). –  Mario Carneiro Mar 25 at 20:56

It is equivalent to saying that if $c$ is a multiple of $n$ and if $c$ is a multiple of $o$ and if $gcd(n,0)=1$ then $c$ is a multiple of $no$.

So yes, it is true

share|improve this answer

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.