3
$\begingroup$

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.

Thanks

$\endgroup$
9
$\begingroup$

Below are sketches of four 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) $

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)\ \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\ |\ a,b \iff cx\ |\ ax,bx \iff cx\ |\ (ax,bx) \iff c\ |\ (ax,bx)/x$

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 $\ $ We induct on $\color{#0a0}{{\rm size}:= a\!+b}.\,$ If $\,a=b,\,$ $\,(ax,bx) = (ax,ax) = (a)x = (a,b)x\,$ so 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$.

$\endgroup$
  • 1
    $\begingroup$ 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$? $\endgroup$ – xFioraMstr18 Jul 5 '18 at 22:52
  • $\begingroup$ @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). $\endgroup$ – Bill Dubuque Nov 15 '18 at 22:13
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Mar 9 '14 at 22:02
  • $\begingroup$ @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. $\endgroup$ – user2345215 Mar 9 '14 at 22:05
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Mar 9 '14 at 22:08
  • $\begingroup$ @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). $\endgroup$ – user2345215 Mar 9 '14 at 22:14
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Mar 9 '14 at 22:17
0
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Far too many details are omitted to judge if this is correct. $\endgroup$ – Bill Dubuque Mar 9 '14 at 21:53
  • $\begingroup$ it was a kind of hint.. $\endgroup$ – sirfoga Mar 10 '14 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.