I need to prove that $z\gcd(a,b)=\gcd(za,zb)$.

I tried a lot, for example, looking at set of common divisors of the two sides, but I can't conclude anything from that. Can you please give me some advice how I can handle this problem? And $a,b,z \in \mathbb{Z}$.

  • 3
    $\begingroup$ Try proving that each side of the equation divides the other. $\endgroup$ – hmakholm left over Monica Sep 25 '12 at 19:55
  • $\begingroup$ Ah, and since divisibility is anti-symmetric, we can then conclude that they are equal :)? Thanks! $\endgroup$ – www.data-blogger.com Sep 25 '12 at 19:57
  • $\begingroup$ While looking at the sets of divisors might give you some intuition, your next reflex would be to use the definition of gcd. This is generally the case for mathematics exercises. $\endgroup$ – rschwieb Sep 25 '12 at 20:00
  • $\begingroup$ @rschwieb: ... except for those where it isn't, for example exercises that are constructed to train familiarity with a derived property of the concept instead of its definition. $\endgroup$ – hmakholm left over Monica Sep 25 '12 at 20:20
  • $\begingroup$ @HenningMakholm (This is probably all just a misunderstanding. "I should have said "this is generally good practice when doing math exercises", instead of what I said.) Maybe you have an example? I'm not sure how you can divorce a question from the meaning of the terms used in it. $\endgroup$ – rschwieb Sep 25 '12 at 20:59

Below are a few proofs of the gcd distributive law $\rm\:(ax,bx) = (a,b)x\:$ using Bezout's identity, universal gcd laws, and unique factorization. In each proof the first line serves as a hint.

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 may employ the universal definitions of GCD, LCM to generalize the above proof.

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

Such universal definitions often serve 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 $$ \min(a+c,\,b+c)\ =\ \min(a,b) + c$$

The proof is precisely the same as the prior proof, replacing gcd by min, and divides by $\le$, and

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

| cite | improve this answer | |
  • $\begingroup$ I didn't expect you to answer a question involving gcds. $\endgroup$ – GeoffDS Sep 25 '12 at 20:13
  • $\begingroup$ Thanks for this large response :)! This answered my question completely :)! $\endgroup$ – www.data-blogger.com Sep 25 '12 at 20:18
  • $\begingroup$ Actually, if there were a gcd tag, you would be the top user, but you wouldn't care about that distinction. $\endgroup$ – GeoffDS Sep 25 '12 at 20:25
  • $\begingroup$ I'm having trouble understanding the first proof because of the following. Can someone please explain to help me understand? $gcd(a,b)$ is the smallest positive $(na+kb)$ for all n, k. So, $\endgroup$ – leontp587 Nov 19 '17 at 21:38
  • $\begingroup$ I'm having trouble understanding the first proof because of the following. Can someone please explain to help me understand? $gcd(a,b)$ is the smallest positive $(na+kb)$ for all integers $n, k$. So,$gcd(x*a,x*b)$ is smallest positive of $(nax+kbx)$ for all $n, k$. The first proof above simply stated that $cx=nax+kbx$, and thus $cx=x*gcd(a,b)$. How can you be sure that it's the same n and k? $\endgroup$ – leontp587 Nov 19 '17 at 21:43

Write $a=da'$, $b=db'$ with $\gcd(a',b')=1$. Then $za=(zd)a'$, $zb=(zd)b'$ with $\gcd(a',b')=1$. This means that $zd=\gcd(za,zb)$.

I'm using here the following characterization of $\gcd(a,b)$:

$d=\gcd(a,b)$ iff $a=da'$, $b=db'$ with $\gcd(a',b')=1$.

Here's a proof.

If $d=\gcd(a,b)$ then $d$ is a common divisor of $a$ and $b$ and you can write $a=da'$, $b=db'$. If $d'=\gcd(a',b')$, then $dd'$ is also a common divisor of $a$ and $b$. Since $d$ is the greatest common divisor, we have $d=dd'$, which implies $d'=1$.

Conversely, if $a=da'$, $b=db'$ with $\gcd(a',b')=1$ then $d$ is a common divisor of $a$ and $b$. Moreover, every prime common divisor of $a$ and $b$ must divide $d$ and so every common divisor of $a$ and $b$ divides $d$, which implies $d=\gcd(a,b)$.

| cite | improve this answer | |
  • $\begingroup$ Without the precise details of the argument supporting "This means", I cannot exclude the proof from possibly being circular. What proof do you have in mind? $\endgroup$ – Bill Dubuque Sep 26 '12 at 3:11
  • $\begingroup$ @BillDubuque, I've added the details. $\endgroup$ – lhf Sep 26 '12 at 6:34
  • $\begingroup$ Thanks. One step still is not clear. In the lemma's proof, for direction $(\Leftarrow)$, precisely which argument do you intend in order to lift from from every prime common divisor to every common divisor. Perhaps induction: cancel $p\,$ then induct on $|c|\,$? $\endgroup$ – Bill Dubuque Sep 26 '12 at 17:48

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.