## If an integer divides the greadest common divisor of two integers, then it divides any linear combination of the two integers

Let $a,b,k$ be integers. Prove that if $k$ divides $a$ and $b$, then $k$ divides $as + bt$ for all integers $s$ and $t$.

Suppose $k$ divides $a$ and $b$; then there exist integers $n$ and $m$ such that $a = kn$ and $b = km$. Now we have $as + bt = kns + kmt = k(ns + mt)$ for all $s,t$, so $k$ divides $as + bt$.