# Divisibility and the gcd

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

Thanks.

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

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

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.

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

Hopefully this makes it obvious.

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

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

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

-

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

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

-