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

– bert
Nov 12, 2013 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! Nov 12, 2013 at 19:52
• More generally if $\,a\mid b\,$ then $\,d\mid a,b\iff d\mid a,\,$ so $\,a,b,$ and $\,a\,$ have the same set $S$ of common divisors $\,d,\,$ hence the same greatest common divisor (= max $S$), i.e. apply the universal property characterizing the gcd. Nov 30, 2021 at 0:45

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.

• i.e. apply the gcd distributive law to factor out $\,a\,$ from the gcd. Nov 30, 2021 at 0:47

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, 2013 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. Nov 12, 2013 at 22:08