Exercise 456Number theory › Divisibility and gcdHigh schoolAdded 3 Nov 2026

GCD and divisibility

#gcd#divisibility#equivalence

Statement

Show that $\gcd(a,b)=a$ iff $a\mid b$ .

Hint

$\gcd(a,b)$ divides $a$ , and equals $a$ iff $a$ also divides $b$ .

Show solutionHide solution

If $\gcd(a,b)=a$ . By definition of gcd, $a=\gcd(a,b)\mid b$ .

If $a\mid b$ . Then $a$ is a common divisor of $a$ and $b$ , and any common divisor divides $a$ , so $\gcd(a,b)=a$ .

Conclusion. $\gcd(a,b)=a\iff a\mid b$ .