# Let $a$ and $b$ be non-zero integers, and $c$ be an integer. Let $d = \gcd(a, b)$. Prove that if $a|c$ and $b|c$ then $ab|cd$.

Let $a$ and $b$ be non-zero integers, and $c$ be an integer. Let $d = hcf(a, b)$. Prove that if $a|c$ and $b|c$ then $ab|cd$.

We know that if $a|c$ and $b|c$ then $a\cdot b\cdot s=c$ (for some positive integer $s$). $(ab|c)$

Then doesn't $ab|dc$ since $ab|c$?

I feel like I'm misunderstanding my givens.

Can we say $\operatorname{lcm}(a,b)=c$, $\operatorname{hcf}(a,b)=d$, and $\operatorname{lcd}(a,b) \operatorname{hcf}(a*b)=a*b$?
Thus, $ab|dc$ as $dc = ab$.

• $4|12$ and $6|12$ but there is no integer $s$ such that $24s | 12$. – Tyler Holden May 7 '14 at 19:45
• Your second statement is wrong, as Tyler has pointed out. However, the assertion holds true when ${\rm gcd}(a,b)=1.$ – Indrayudh Roy May 7 '14 at 19:55

Hint $$\,\ a,b\mid c\,\Rightarrow\, ab\mid ca,cb\,\Rightarrow\, ab\mid (ca,cb) = c(a,b)\,$$ by the GCD Distributive Law (below).

Below are four proofs of the GCD Distributive Law $$\rm\:(ax,bx) = (a,b)x\:$$ using various approaches: Bezout's identity, the universal gcd property, unique factorization, and induction.

First we show that the gcd distributive law follows immediately from the fact that, by Bezout, the gcd may be specified by linear equations. Distributivity follows because such linear equations are preserved by scalings. Namely, for naturals $$\rm\:a,b,c,x \ne 0$$

$$\rm\qquad\qquad \phantom{ \iff }\ \ \ \:\! c = (a,b)$$

$$\rm\qquad\qquad \iff\ \: c\:\ |\ \:a,\:b\ \ \ \ \ \ \&\ \ \ \ c\ =\ na\: +\: kb,\ \ \$$ some $$\rm\:n,k\in \mathbb Z$$

$$\rm\qquad\qquad \iff\ cx\ |\ ax,bx\ \ \ \&\ \ \ cx = nax + kbx,\ \,$$ some $$\rm\:n,k\in \mathbb Z$$

$$\rm\qquad\qquad { \iff }\ \ cx = (ax,bx)$$

The reader familiar with ideals will note that these equivalences are captured more concisely in the distributive law for ideal multiplication $$\rm\:(a,b)(x) = (ax,bx),\:$$ when interpreted in a PID or Bezout domain, where the ideal $$\rm\:(a,b) = (c)\iff c = gcd(a,b)$$

Alternatively, more generally, in any integral domain $$\rm\:D\:$$ we have

Theorem $$\rm\ \ (a,b)\ =\ (ax,bx)/x\ \$$ if $$\rm\ (ax,bx)\$$ exists in $$\rm\:D.$$

Proof $$\rm\quad\: c\ |\ a,b \iff cx\ |\ ax,bx \iff cx\ |\ (ax,bx) \iff c\ |\ (ax,bx)/x\ \ \$$ QED

The above proof uses the universal definitions of GCD, LCM, which often served to simplify proofs, e.g. see this proof of the GCD * LCM law.

Alternatively, comparing powers of primes in unique factorizations, it reduces to the following $$\begin{eqnarray} \min(a+x,\,b+x) &\,=\,& \min(a,b) + x\\ \rm expt\ analog\ of\ \ \ \gcd(a \,* x,\,b \,* x)&=&\rm \gcd(a,b)\,*x\end{eqnarray}\qquad\qquad\ \$$

The proof is precisely the same as the prior proof, replacing gcd by min, and divides by $$\,\le,\,$$ and using the universal property of min instead of that of gcd, i.e.

$$\begin{eqnarray} {\rm employing}\quad\ c\le a,b&\iff& c\le \min(a,b)\\ \rm the\ analog\ of\quad\ c\ \, |\, \ a,b&\iff&\rm c\ \,|\,\ \gcd(a,b) \end{eqnarray}$$

Then the above proof translates as below, $$\$$ with $$\,\ m(x,y) := {\rm min}(x,y)$$

$$c \le a,b \!\iff\!c\!+\!x \le a\!+\!x,b\!+\!x\!$$ $$\!\iff\! c\!+\!x \le m(a\!+\!x,b\!+\!x)\!$$ $$\!\iff\!\! c \le m(a\!+\!x,b\!+\!x)\!-\!x$$

Theorem $$\ \$$ If $$\ a,b,x\$$ are positive naturals then $$\ (ax,bx) = (a,b)x$$

Proof $$\$$ By induction on $$\color{#0a0}{{\rm size}:= a\!+b}.\,$$ If $$\,a=b,\,$$ $$\,(ax,bx) = (ax,ax) = (a)x = (a,b)x\,$$ hence it is true.  Else $$\,a\neq b;\,$$ wlog, by symmetry, $$\,a > b\,$$ so $$\,(ax,bx) = (ax\!-\!bx,bx) = \color{}{((a\!-\!b)x,bx)}\,$$ with smaller $$\rm\color{#0a0}{size}$$ $$\,(a\!-\!b) + b = a < \color{#0a0}{a\!+b},\,$$ therefore $$\,((a\!-\!b)x,bx)\!\underset{\rm induct}=\! (a\!-\!b,b)x = (a,b)x$$.

For completeness below we present a proof of the LCM Distributive Law with notation $$\,[x,y] := {\rm lcm}(x,y),\,$$ using the LCM universal property and basic divisibility properties.

Theorem $$\ \ [ax,bx] = [a,b]x$$

Proof $$\ \ [ax,bx]\mid c\iff ax,bx\mid c\iff a,b\mid c/x\iff [a,b]\mid c/x\iff [a,b]x\mid c$$

Therefore $$\ [ax,bx] = [a,b]x\,$$ since they divide each other by above.

• what do you mean by $(ax,bx)/x$ ? Do you mean inverse of $x$ ? – user228168 Sep 19 '16 at 8:19
• @SaunDev $\ (m,n)\,$ means $\,\gcd(m,n).\,$ This notation is widely used in number theory. – Bill Dubuque Sep 19 '16 at 14:49
• Dubuque : yes I perfectly understand that ... what I mean to say is what do you mean by that $1/x$ ? [ $x$ is not necessarily unit ... ] – user228168 Sep 19 '16 at 15:00
• @SaunDev $\ x\mid ax,bx\,\Rightarrow\, x\mid (ax,bx),\,$ so it denotes the quotient. – Bill Dubuque Sep 19 '16 at 15:02
• Dubuque : ah yes ... I see , thank you – user228168 Sep 19 '16 at 15:03

As an extreme example, let $a=b=c=4$. Then $a$ divides $c$ and $b$ divides $c$, but $ab$ does not divide $c$. So the approach you suggested will need modification.

Now let us prove the stated result. Because $d$ is the highest common factor of $a$ and $b$, there exist integers $s$ and $t$ such that $as+bt=d$. (This is often called Bézout's lemma.) It follows that $$cas+cbt=cd.$$ Because $b$ divides $c$, we have $ab$ divides $cas$. Because $a$ divides $c$, we have $ab$ divides $cbt$. So $ab$ divides $cas+cbt$, that is, $ab$ divides $cd$.

• Remark that the above proof essentially employs the gcd distributive law (see the first Bezout-based proof in my answer). – Bill Dubuque May 7 '14 at 20:50

Let us put it this way: Define a', b' so that a=a'd and b=b'd, where d=GCD(a,b). Then a|c means c = a'ds for some s, and b|c means c = b'dt for some t. But that doesn't mean ab|c because we could have a'|t and b'|s, i.e c = a'b'du for some u. I.e in dividing c, a and b are sharing d between them.

Of course, if c = a'b'du, cd = a'db'du = abu.