Wednesday, 22 October 2025

Exercise (1.3).17

Prove Proposition (1.11).


Proposition (1.11) is

Let $\gcd (a, b) = g$. For any positive integer $m$ we have $\gcd (ma, mb) = mg$.


We're given $\gcd (a, b) = g$ which means there exist integers $x,y$ such that

$$ a = xg $$

$$ b = yg $$

Multiplying through by $m$ we have

$$ ma = x(mg) $$

$$ mb = y(mg) $$

So $mg \mid ma$ and $mg \mid mb$. This means there exists some integer $k>0$ such that

$$ \gcd(ma, mb) = k(mg) $$

If we assume, for the purpose of contradiction, that $k>1$, then

$$ \gcd(ma, mb) > mg $$

If we take the particular case of $m=1$, this gives us

$$ \gcd(a, b) > g $$

This contradicts the premise $\gcd(a,b)=g$, and so the assumption $k>1$ is false, meaning $k=1$. That is,

$$ \gcd(ma, mb) = mg $$


So we have shown Proposition 1.11 is true.


Alternative Solution

The alternative solution given by the author is worth exploring.

The $\gcd(ma, mb)$ is the least positive value of $ max + mby = m(ax + by) $ for integers $x,y$.

Since $m>0$, this is $m$ times the least positive value of $(ax + by)$ which is the $m\gcd(a,b) = mg$.