# How to prove that for all positive integers $a,b$, if $a|b$ , then $\gcd(a,b) = a$?

I don't believe there are any counter examples that can be used for this (I think it is true). Could someone help me prove it?

I understand why it's true (if I was right about that), but the proof itself is a bit tricky.

On one hand, and since everything's positive here, $\;gcd(a,b)\le a,b\;$ , but on the other $\;a\mid a\;\;and\;\;a\mid b\;$ , so

$$a\le gcd(a,b)\le a\implies gcd(a,b)=a$$

• Could you go into more detail about this? I don't fully understand what you wrote. – bert Nov 12 '13 at 19:50
• since $\;gcd(a,b)\;$ is the largest divisor of both $\;a,b\;$ the first inequality in my answer follows, and since $\;a\;$ is one of those divisors according to the given info, the leftmost inequality in the last line follows, too...so we get equality! – DonAntonio Nov 12 '13 at 19:52

Suppose that $a,b>0$ and $a|b$.

1. $a$ is a common divisor of $a,b$.
2. If $c$ is also a common divisor of $a,b$, then $c|a$.

This is the usual definition of gcd.

• Sorry, but where did the c come from? – bert Nov 12 '13 at 19:52
• The definition I am using is that $gcd(a,b)$ is the greatest common divisor. That is, it is a common divisor, and it is greatest in the sense that all other common divisors divide it. – vadim123 Nov 12 '13 at 22:08

If $a|b$, then there is some integer $n$ such that $b = na$. Now the Euclidian algorithm says that $$\gcd(a, b) = \gcd(a, na) = \gcd(a, na - na) = \gcd(a, 0) = a$$

Hint: Use the fact that

$gcd(a,b)=d$ iff $gcd(\frac{a}{d},\frac{b}{d})=1$.

Note: This result can be proved using the theorem that states that gcd can be expressed as a linear combination of the numbers.