Thursday, 16 October 2025

Exercise (1.1).22

Prove that $\gcd (−a, −b) = \gcd (a, b)$ where $a$ and $b$ are not both zero.


Suppose $g$ is $\gcd (−a, −b)$. Then, for some integers $m,n$

$$\begin{align} (-a) &= mg \\ \\  (-b) &= ng \end{align}$$

Multiplying these equations by (-1) gives us

$$\begin{align} a &= (-m)g \\ \\  b &= (-n)g \end{align}$$

So $g$, which is positive by definition, is divisor of both $a$ and $b$. 

It is also the largest common divisor of $a$ and $b$ because it is also the largest common divisor of $(-1)a$ and $(-1)b$. 


Put another way, if there were a larger common divisor $h$ of $a$ and $b$, then for some integers $p,q$

$$\begin{align} a &= ph \\ \\  b &= qh \end{align}$$

which gives us

$$\begin{align} (-a) &= (-p)h \\ \\  (-b) &= (-q)h \end{align}$$

then that $h$ and not $g$ would be the $\gcd (−a, −b)$.


And so 

$$\gcd (−a, −b) = \gcd (a, b)$$