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.

Let $a,b$ be integers with $a|b$ (a divides b) and let $a>0$. Show that $(a,b)=a$. I know this is very basic, and that I'm complicating it unnecessarily, but for some reason I seem to be stuck...

Any help please?

Thanks.

Edit: $(a,b)$ means greatest common divisor of $a$ and $b$

share|improve this question
2  
What do you mean by $(a, b)$? Do you mean the greatest common divisor? The least common divisor? The cartesian coordinate? None of these interpretations make the equation true though. –  Calvin Lin Jan 8 '13 at 5:42
    
@CalvinLin Oops, sorry forgot to include that. I fixed my question. –  Alti Jan 8 '13 at 5:44
1  
In order for this to be true, we must know that $a$ divides $b$. Otherwise $a=2$ and $b=3$ provide a counterexample. –  anon271828 Jan 8 '13 at 5:45
    
@anon271828 Yes, I edited my original question. Thanks. –  Alti Jan 8 '13 at 5:46

6 Answers 6

up vote 1 down vote accepted

Well, recall the definition of $(a,b)$: it's the integer that divides both $a$ and $b$, and furthermore is the biggest integer that does so.

So how about asking:

  1. Does $a$ divide $a$ and $b$?
  2. Is $a$ the biggest integer that does so?

Hopefully this makes it obvious.

share|improve this answer
    
Thanks, I knew I was unnecessarily complicating it, it's obvious now. –  Alti Jan 8 '13 at 6:08

Let $p_i$ be the set of distinct primes that divide either $a$ or $b$.

Let $a = \prod p_i ^{a_i}, b = \prod p_i ^{b_i}$, where $a_i, b_i$ are non-negative integers.

The condition that $a \mid b$ implies that $a_i \leq b_i \, \forall i$.

To calculate the GCD, recall that $\gcd(a, b) = \prod p_i ^{\min (a_i, b_i)}$. Hence, this is equal to $\prod p_i ^{a_i} = a$

share|improve this answer
    
That wasn't how I'd do it,but that's actually pretty clever. –  Mathemagician1234 Jan 8 '13 at 5:50
    
Holy $p^2f$ THat's a bit much, maybe –  Chris Dugale Jan 8 '13 at 6:20
    
that's killing mosquitoes with canons –  mathemagician Jan 8 '13 at 13:29

if gcd were greater than a then it cannot divide a. a is by construction a common divisor, hence the greatest common divisor. :)

share|improve this answer
    
Hey,you stole my proof! lol –  Mathemagician1234 Jan 8 '13 at 5:51
    
and you stole my nickname lol –  mathemagician Jan 8 '13 at 5:54
1  
I had it before you did,check the record.....lol –  Mathemagician1234 Jan 8 '13 at 5:57

Given $a,b \in \mathbb{Z}$, there exists $x,y \in \mathbb{Z}$ such that$$ax+by = (a,b) \,\,\,\,\,\,\,\,\,\, (\star)$$We are given that $a \vert b$. Hence, we have $b=ka$. Hence, from $(\star)$, we get that $$a(x+ky) = (a,b)$$ This means $a \vert (a,b)$. However, we also know that $(a,b) \vert a$. Now recall that if $c \vert d$ and $d \vert c$, then $c=\pm d$. Hence, we get that $$(a,b) = \vert a \vert$$

share|improve this answer

Another definition of gcd that is more extensible to other groups is "a common divisor of $a$ and $b$ that is divisible by all other common divisors". Clearly, $a$ is a divisor of $a$, and by your assumption, it divides $b$. So it is a common divisor. Let $d$ be an arbitrary divisor of $a$ and $b$. Since $d$ divides $a$ and $b$, it divides $a$. Thus, $a$ is a gcd of $a$ and $b$.

share|improve this answer
1  
Isn't your last sentence just assuming what we are wanting to show? Shouldn't you say that if $d$ is another common divisor of $a$ and $b$, then $d \le a$, hence $a$ is the gcd? –  Josh Chen Jan 8 '13 at 6:11
1  
With this particular definition of gcd, you don't need > to be defined. It's just (a, b) = g iff g|a and g|b and for all d, (d|a and d|b) => d|g –  Henry Swanson Jan 8 '13 at 6:16
    
Ah I see what you are saying. It was the final phrase "...$a$ (which is the gcd)" in your last sentence that confused me; I thought you were assuming you already knew that $a$ was the gcd. You might want to edit it to say "...$a$, hence $a$ is the gcd" or something like that. –  Josh Chen Jan 9 '13 at 3:43

The statement should be (a,b)=|a| not a. Also a does not equal 0.

share|improve this answer

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.