Prove that $(ma, mb) = |m|(a, b)\$ [GCD & LCM Distributive Law]

I'm trying to prove that $$(ma, mb) =$$|$$m$$|$$(a, b)$$ , where $$(ma, mb)$$ is the greatest common divisor between $$ma$$ and $$mb$$.

My thoughts:

If $$(ma, mb) = d$$ , then $$d$$|$$ma$$ and $$d$$|$$mb$$$$d$$|$$max + mby$$$$d$$|$$m(ax+by)$$. This implies that $$d$$|$$m$$ or $$d$$|$$(ax+by)$$. This is the same as $$d$$|$$m$$ or $$d$$|$$a$$ and $$d$$|$$b$$, so $$d$$|$$m$$ or $$d$$|$$(a,b)$$. This is the same as $$d$$|$$m|$$ or $$d|(a,b)$$, so $$d$$|$$|m|(a,b)$$.

I don't know what to do.

Below are sketches of six proofs of the GCD Distributive Law $$\rm\:(ax,bx) = (a,b)x\:$$ by 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)$$

Readers familiar with ideals may 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 \approx gcd(a,b)$$. This proof fails in non-Bezout domains like $$\,\Bbb Z[x]\,$$ and $$\,\Bbb Q[x,y],\,$$ e.g. $$\,(x,2) = 1 = (x,y)\,$$ but the gcds cannot be written as linear combinations, else $$\, 1 = x\,f(x,y) + y\,g(x,y)\Rightarrow\,1=0\,$$ by evaluating at $$\,x=0=y.\,$$ But the next proof works fine there (or in any gcd domains).

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

Theorem $$\rm\ \ (a,b)\ \approx\ (ax,bx)/x\ \$$ if $$\rm\ (ax,bx)\$$ exists in $$\rm\:D\ \,$$ [$$c\approx d := c,d\,$$ associate: $$\,c\mid d\mid c$$]

Proof $$\rm\quad\! c\mid(a,b)\!\!\overset{\rm def\!\!}\iff c\ |\ a,b \iff cx\ |\ ax,bx \!\!\overset{\rm def\!\!}\iff cx\ |\ (ax,bx) \iff c\ |\ (ax,bx)/x$$

where $$\,\rm x\mid ax,bx\ \smash{\overset{\rm def}\Rightarrow}\ x\mid (ax,bx).\,$$ Thus $$\rm\,(a,b) \approx (ax,bx)/x,\,$$ since they divide each other by above. We used the GCD Universal Property (it often simplifies proofs, e.g. see this proof of the GCD * LCM law).

Or by this Remark it's case $$\,m = abc\,$$ in $$\,(m/a,m/b) = m/{\rm lcm}(a,b)\,$$ for $$\,m\,$$ being any common multiple of $$a,b;\,$$ or, expressed equivalently $$\,\gcd(a',b') = {\rm lcm}(a,b)'\,$$ by cofactor duality.

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

Or in any UFD we can induct on the number $$\,k\,$$ of prime factors of $$\,x.\,$$ If $$\,k=0\,$$ then $$\,x\,$$ is a unit thus $$\,(ax,bx)=(a,b)x\,$$ is clear. Else $$\,x = yp\,$$ for $$\,p\,$$ prime so by $$\,\color{#c00}{I =\rm induction}$$

\begin{align} {\rm if}\,\ p\nmid d\,\ &{\rm then}\,\ d\mid ayp,byp \iff\,\ d\mid ay,by \color{#c00}{\overset{ I\!\!\!}\iff}\ d\mid (a,b)y \iff d\mid (a,b)yp\\ {\rm if}\,\ p\mid d\,\ &{\rm then}\,\ d\mid ayp,byp \iff \frac{d}p\mid ay,by \color{#c00}{\overset{ I\!\!\!}\iff} \frac{d}p\mid (a,b)y \iff d\mid (a,b)yp\end{align}

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

Proof $$\$$ We induct on $$\color{#0a0}{{\rm size}:= a\!+b}.\,$$ If $$\,a=b\,$$ then it is true since both sides $$= ax.\,$$ 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] \approx [a,b]x$$

Proof $$\ \ \smash{[ax,bx]\mid c\!\!\overset{\rm def\!\!\!}\iff ax,bx\mid c\iff a,b\mid c/x\!\!\overset{\rm def\!\!\!}\iff [a,b]\mid c/x\iff [a,b]x\mid c}$$

Therefore $$\rm\, [ax,bx] \approx [a,b]x\,$$ are associate (divide each other) by above. In particular, they are equal if we are in $$\Bbb Z$$ and we normalize lcms to be positive. Similarly, more generally we have

Theorem' $$\,\ [a,b]\,$$ exists $$\!\iff\! (ac,bc)$$ exists for all $$\,c\in D,\,$$ for any $$\,a,b,c\,$$ in a domain $$D$$

Proof $$\ \ (\Rightarrow)\,\ \ d\mid ac,bc \!\iff\! a,b\mid abc/d \!\iff\! [a,b]\mid abc/d \!\iff\! d\mid abc/[a,b]$$

$$(\Leftarrow)\,\ \ a,b\mid c\iff ab\mid ac,bc\iff ab\mid (ac,bc)\iff abc/(ac,bc)\mid c$$

\begin{align} {\rm i.e.}\ \ \ \ \ [a,b]\ {\rm exists}\ &\Rightarrow (ac,bc) \approx abc/[a,b]\\[.3em] \forall c\!: (ac,bc)\ {\rm exists}\ &\Rightarrow\ \ \ \ \, [a,b] \approx abc/(ac,bc) \approx ab/(a,b)\end{align}\qquad\qquad

See here and its links for methods exploiting innate duality between gcd & lcm.

• In your first theorem, division by $x$ is not always possible since $D$ is merely an integral domain, not necessary a field. In addition, I fail to understand precisely what you mean. Greatest common divisors are not unique, so what do you mean by equality of $(a,b)$ and $(ax,bx)/x$? Commented Jul 5, 2018 at 22:52
• @xFioraMstr18 The first proof cancels $\,x\neq 0\,$ which is valid since we presume the ring is a domain. Greatest common divisors are unique up to associates (unit multiples). To be rigorous we should write that the gcds are associate, but is a common abuse of language to use "equal" vs. "associate" (i.e. to implicitly work in the quotient monoid modulo the unit group). Commented Nov 15, 2018 at 22:13

It's simpler, you don't need any identity, factorization, almost nothing apart from the fact the $\gcd$'s exist.

Let $c=\gcd(a,b)$ and $d=\gcd(ma,mb)$, then $$c\mid a, b\Longrightarrow mc\mid ma, mb\Longrightarrow mc\mid d$$ so $d=mcx$, then $$mcx\mid ma, mb\Longrightarrow cx\mid a,b\Longrightarrow cx\mid c\Longrightarrow x\mid1$$

therefore $\gcd(ma, mb)=|m|\gcd(a,b)$.

• This is essentially the second proof in my answer, except that I exploit the universal gcd property to do both directions simultaneously, making the proof more succinct - a one liner. Commented Mar 9, 2014 at 22:02
• @Bill Dubuque Well I'm not sure OP knows what universal property is (well I only know it's some abstract nonsense from category theory), so I really want to avoid that. Commented Mar 9, 2014 at 22:05
• The universal property of the gcd is simply $\ c\mid a,b\iff c\mid \gcd(a,b),\,$ analogous to $\,c\le a,b\iff c\le \min(a,b).\,$ No knowledge of category theory is needed to grok that. You use that implicitly above, but not as efficiently as can be done, since you do both directions separately. Commented Mar 9, 2014 at 22:08
• @Bill Dubuque: Oh I see, it's quite nice, but I wanted to avoid division (I know I'm in an integral domain too, but it looks like fractions). Commented Mar 9, 2014 at 22:14
• One can restructure to use cancellation vs. division if one prefers. Unfortunately these nice universal proofs are not as well known as they deserve to be, so I try to emphasize them whenever I get the chance. Commented Mar 9, 2014 at 22:17

Quite simply: Let $x=gcd(a,b).$ Then $a=xk$ and $b=xl$ for some coprime $k, l$ by definition of GCD.

Then $ma=mxk$ and $mb=mxl$.

Therefore, $gcd(ma,mb)=mx=mgcd(a,b)$ [because $gcd(k,l)=1$, so the greatest divisor of both $ma$, $mb$ must then be $mx$]. $\blacksquare$

Hint : Let $x = GCD(a,b)$: you have $$a=a_1\cdot x, b=b_1\cdot x$$ where $GCD(a_1,b_1) = 1$. Now $$GCD(ma,mb) = GCD(ma_1\cdot x,mb_1\cdot x) = mx$$ since $GCD(a_1,b_1) = 1$, so $$GCD(ma,mb) = m\cdot GCD(a,b)$$

• Far too many details are omitted to judge if this is correct. Commented Mar 9, 2014 at 21:53
• it was a kind of hint.. Commented Mar 10, 2014 at 13:08