Wednesday, 22 October 2025

Exercise (1.3).16

Prove that if $\gcd (a, b) = 1$ then $\gcd (a + b, ab) = 1$.


Let's practice proof by contradiction, something the textbook author uses a lot in his solutions. 


Let's remind ourselves that $A \implies B$ is the same as $\neg B \implies \neg A$. So we'll assume the conclusion $\gcd(a+b,ab)=1$ is false, and aim to show the premise is also false

Since a gcd is only ever more than or equal to 1, the negation of the conclusion is

$$  g = \gcd(a+b, ab) > 1$$

By definition of gcd, this means $g \mid (a + b)$ and $g \mid ab$. Furthermore $g$ is a factor of linear combinations of $(a+b)$ and $ab$, from the Linear Combination Theorem 1.3. 

In particular

$$ g \mid a(a+b) - (ab) \implies g \mid a^2$$

$$ g \mid b(a+b) - (ab) \implies g \mid b^2$$

If $g \mid a^2$ then $g\mid a$, and similarly, if $g \mid b^2$ then $g \mid b$. That is, there exists some integer $k>0$ such that

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

Since we assumed, $g>1$, then this tells us $\gcd(a,b)>1$. This contradicts the premise that $\gcd(a,b)=1$. 

We have shown that

$$\neg \Big ( \gcd(a+b, ab)=1 \Big ) \quad  \implies \quad \neg \Big ( \gcd(a,b) = 1 \Big )$$

That is

$$ \gcd (a, b) = 1 \quad  \implies  \quad \gcd (a + b, ab) = 1$$