Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I need to prove that $z \cdot \text{gcd}(a,b)=\text{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}$.

share|improve this question
3  
Try proving that each side of the equation divides the other. –  Henning Makholm Sep 25 '12 at 19:55
    
Ah, and since divisibility is anti-symmetric, we can then conclude that they are equal :)? Thanks! –  Kevin Sep 25 '12 at 19:57
    
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. –  rschwieb Sep 25 '12 at 20:00
    
@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. –  Henning Makholm Sep 25 '12 at 20:20
    
@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. –  rschwieb Sep 25 '12 at 20:59
show 2 more comments

3 Answers

up vote 6 down vote accepted

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

share|improve this answer
    
I didn't expect you to answer a question involving gcds. –  Graphth Sep 25 '12 at 20:13
    
Thanks for this large response :)! This answered my question completely :)! –  Kevin Sep 25 '12 at 20:18
    
Actually, if there were a gcd tag, you would be the top user, but you wouldn't care about that distinction. –  Graphth Sep 25 '12 at 20:25
add comment

Use this characterisation: $d=\gcd(a,b) \iff [(s|a,\ s|b ) \Rightarrow d|s]$.

share|improve this answer
    
Thanks! :) I think that property will solve my problem :)! –  Kevin Sep 25 '12 at 20:17
    
I am stuck. I found $d|za, d|zb \Rightarrow d|z(a+b)$.. But I don't know what to do next. –  Kevin Sep 25 '12 at 20:42
    
@Berci That's not a correct characterization of gcd, but the following is (see my answer and its links) $$\rm c\:|\:a,b\iff c\:|\:gcd(a,b)$$ –  Bill Dubuque Sep 26 '12 at 3:17
add comment

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

share|improve this answer
    
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? –  Bill Dubuque Sep 26 '12 at 3:11
    
@BillDubuque, I've added the details. –  lhf Sep 26 '12 at 6:34
    
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|\,$? –  Bill Dubuque Sep 26 '12 at 17:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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