# $(a,b) = 1$ implies $a|n$ and $b|n \implies ab|n$

Prove if $(a,b) = 1$ implies $a|n$ and $b|n \implies ab|n$.

I'm pretty sure this has been asked before but I cannot find anything online.... I also have no idea how to solve it, I get stuck with al = bk for some l,k in the integers.

If $\gcd(a,b) = 1$ then the Bezout identity gives some $x,y$ such that $ax+by = 1$. Hence $axn+byn = n$, and since $ab \mid axn$ and $ab \mid byn$ we have $ab \mid n$.

• This mainly shows that it is possible to invoke a Bezout identity in just about any question about relative primality, even in those cases where it is much easier to do without. – Marc van Leeuwen Feb 23 '14 at 7:58
• I don't get your point. Bézout's identity is fairly elementary, it appears in the first few pages of my copy of Stark's "Introduction to number theory". – copper.hat Feb 23 '14 at 8:11
• My point was not the the existence of a Bezout identity is hard to see, but that it seems not really needed in showing that if $\gcd(a,b)=1$, then $ab$ is the least common multiple of $ab$: if $ab/d$ is a common multiple of $a,b$, then $d$ is a common divisor of $a,b$. But I guess one needs to show at some point that least (in the sense of divisibility) common multiples exist in $\mathbf Z$, and that would involve invoking a Euclidean division too; so I should replace "much easier" by "a bit easier" in my previous comment. – Marc van Leeuwen Feb 23 '14 at 11:01
• You can eliminate Bezout's Identity by using the GCD Distributive Law $\,(an,bn) = (a,b)n,\,$ see my answer. – Gone Feb 23 '14 at 21:06
• @copper.hat It depends on the background of the reader what will be clearer or more intuitive. The advantage of the gcd approach is that it works more generally, e.g. in domains that have gcds but not Bezout identities, e.g. non-PID UFDs such as $\,\Bbb Z[x]\,$ and $\,\Bbb Q[x,y].\ \$ – Gone Feb 24 '14 at 1:10

Modular arithmetic to the rescue!

If

$$n \equiv 0 \bmod a$$ $$n \equiv 0 \bmod b$$

then by the Chinese Remainder Theorem,

$$n \equiv 0 \bmod \operatorname{lcm}(a,b)$$

• I think this direction does not really need the CRT: the system is asking for a common multiple of $a,b$, and by definition $\operatorname{lcm}(a,b)$ is the smallest positive solution to that. And the solution set is clearly a set of congruence classes (in fact just one class) modulo this lcm. This is in particular true whether or not $a,b$ are coprime. – Marc van Leeuwen Feb 23 '14 at 11:07
• This would yield a circular proof in many (most) textbook developments. – Gone Feb 23 '14 at 19:11
• @Bill: Deriving a subject from first principles is a very different topic than solving problems once you've learned the basics. – user14972 Feb 23 '14 at 19:11
• So you propose to use CRT without first proving it? That's even worse than I surmised! – Gone Feb 23 '14 at 20:07
• @Bill: Yes, I do propose to use CRT without first proving it. I proved it long ago, and learned it long before that. It's far easier to solve a problem in number theory by using all of these fancy tools they teach us rather than starting from scratch at Peano's axioms every time. – user14972 Feb 23 '14 at 20:08

The proof comes out of intuition as follows:

Since $a \mid n$, Let $q$ the quotient.

$b \mid n$ $\implies b \mid q$. Since $a$ doesn't remove any of the factors of $b$ from $n$ as there are no common factors between $a$ and $b$.

$\implies ab \mid n$

• It seems that you have implicitly invoked the fundamental theorem of arithmetic (existence and uniqueness of prime factorizations) or some equivalent (e.g. Euclid's Lemma). As an illustrious mathematician (Gauss) once remarked on such topics, one should not resort to handwaving when simple rigorous proofs are available. See here for one way to make this intuition rigorous. – Gone Feb 23 '14 at 20:30
• I thought existence and uniqueness of prime factorizations was quite intuitive. :) – nitish712 Feb 24 '14 at 2:53
• Why do you think it is "intuitive"? – Gone Feb 24 '14 at 3:05

As I've been commenting that this is simpler than some other answers suggest, let me be fair and say what minimum knowledge I think is required for this conclusion. I'll assume (though the question does not say so) $a,b$ are supposed to be nonzero; anyway either being $0$ would force $n=0$, a trivial case.

You must (as is often the case when reasoning about integers) at some point use the possibility of integer division: for integer $k,l$ with $l>0$ there exist integer $q,r$ with $k=ql+r$ and $0\leq r<l$. Here it can be used to show that the smallest positive common multiple $m$ of $a,b$ (which certainly exists because $|ab|$ is a positive common multiple) divides any other common multiple $c$ of $a,b$: writing $c=qm+r$ with $0\leq r<m$ one easily sees that $r=c-qm$ is a common multiple of $a,b$, so $r=0$ by minimality of$~m$.

Now things are easy. If the least common multiple$~m$ of $a,b$ were smaller than $|ab|$, then by the above it would divide $|ab|$, and $|ab|/m>1$ would be a common divisor of $a,b$, contradicting the hypothesis $\gcd(a,b)=1$. So $m=|ab|$, and as we saw it divides any common divisor of $a,b$, such as$~n$.

Notice $\ a,b\mid n\,\Rightarrow\ ab\mid an,bn \,\Rightarrow\, ab\mid (an,bn)=(a,b)n = n\$ by the GCD Distributive Law.

Remark $\,$ This generalizes to $\ ab = \gcd(a,b) {\rm lcm}(a,b)\$ if $\ {\rm lcm}(a,b)\,$ exists (true in any domain).

Note that if something is divisible by both $a$ and $b$, it must also be divisible by the least common multiple of $a$ and $b$. Hence, we have that $lcm(a,b)\ |\ n$.

You're already given that $gcd(a,b) = 1$, what can you conclude from that about $lcm(a,b)$?

If $\ \color{#0a0}{(a,b)=1}\,$ then $\ a,b\mid n\,\Rightarrow\, \color{#0a0}a\mid \color{#0a0}b\,(n/b)\,\overset{\color{#c00}{\rm(E)}}\Rightarrow\, a\mid n/b\,\overset{\times\ b}\Rightarrow\,ab\mid n\$ by $\,\color{#c00}{\rm(E)} =$ Euclid's Lemma.