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$$

Exercise (1.3).15

(i) Prove that

$$ \gcd (a, b) = \gcd (a, c) = 1 \iff \ gcd (a, bc) = 1 $$

(ii) Prove that if

$$ \gcd (a, n_1) = \gcd (a, n_2) = \ldots  = \gcd (a, n_k) = 1 $$

then

$$\gcd (a, n_1 × n_2 \ldots × n_k) = 1$$

(iii) Prove that if $\gcd (a, b) = 1$ then $\gcd (a^n, b^n) = 1$ where $n$ is a natural number.

(i) We need to prove both directions:

• $ \gcd (a, b) = \gcd (a, c) = 1 \implies \gcd (a, bc) = 1 $
• $ \gcd (a, b) = \gcd (a, c) = 1 \impliedby \gcd (a, bc) = 1 $

($\implies$)

We apply Bezout's Identity to $\gcd(a,b)=1$ and $\gcd(a,c)=1$. There exist integers $x,y, p,q$ such that

$$ ax + by = 1 $$

$$ ap + cq = 1 $$

Multiplying

$$ \begin{align} 1 &= a^2xp + axcq + byap + bycq \\ \\ & = a(axp + xcq + byp) + bc(yq) \end{align}$$

The $\gcd(a,bc)$ must also divide 1, which is only possible if

$$ \gcd(a, bc) = 1 $$

($\impliedby$)

We apply Bezout's Identity to $\gcd(a,bc)=1$. There exist integers $m,n$ such that

$$ am + bcn = 1 $$

We can read two facts from this. The $\gcd(a,b)$ divides 1, and $\gcd(a,c)$ divides 1. This is only possible if

$$\begin{align} \gcd(a,b) &= 1 \\ \\ \gcd(a,c) &= 1  \end{align}$$

By showing both ($\implies$) and ($\impliedby$), we have proven the original equivalence.

(ii) This doesn't really require a long proof because it is clear that if $a$ shares no common factors, except 1, with any of $n_1, n_2, \ldots, n_k$, then it doesn't share any common factors with the product $n_1 \times n_2 \times \ldots \times n_k$.

For practise, let's do a proof by induction.

Let's establish the statement $P(m)$ to mean

If $ \gcd (a, n_1) = \gcd (a, n_2) = \ldots  = \gcd (a, n_m) = 1 $ then $\gcd (a, n_1 × n_2 \ldots × n_m) = 1$.

We need to prove a base case and an induction step.

Base Case

The base case is $P(2)$

If $ \gcd (a, n_1) = \gcd (a, n_2)  = 1 $ then $\gcd (a, n_1 × n_2) = 1$

We've shown t his is true in part (i) of the exercise. So the base case is true.

Induction Step

We need to show $P(m) \implies P(m+1)$. The statement $P(m+1)$ is

If $ \gcd (a, n_1) = \gcd (a, n_2) = \ldots  = \gcd (a, n_m) = \gcd(a,n_{m+1}) = 1 $ then $\gcd (a, n_1 × n_2 \ldots × n_m \times n_{m+1}) = 1$

We assume $P(m)$ holds as the induction hypothesis. The assumption under $P(m)$ that $ \gcd (a, n_1) = \gcd (a, n_2) = \ldots  = \gcd (a, n_m) = 1 $ is covered by the assumption for $P(m+1)$. The conclusion of the assumption $P(m)$ is that $\gcd (a, n_1 × n_2 \ldots × n_m) = 1$.

If we rename, for clarity, $n_1 × n_2 \ldots × n_m$ as $b$ then we have two assumptions, $\gcd(a,b)=1$ and $\gcd(a, n_{m+1})=1$. Again by exercise (i), this gives us $\gcd(a, b \times n_{m+1})=1$. This is the conclusion of $P(m+1)$. We have shown $P(m+1)$ follows from $P(m)$.

Thus by induction we have shown that if $ \gcd (a, n_1) = \gcd (a, n_2) = \ldots  = \gcd (a, n_m) = 1 $ then $\gcd (a, n_1 × n_2 \ldots × n_m) = 1$

(iii) We'll use induction.

Let's establish the statement $P(n)$ to mean

If $\gcd (a, b) = 1$ then $\gcd (a^n, b^n) = 1$, for integers $a,b$ and natural number $n$.

We need to show the base case and inductive step are true.

Base Case

The base case is $P(0)$ which is

If $\gcd (a, b) = 1$ then $\gcd (a^0, b^0) = 1$, for integers $a,b$ and natural number $n$.

This is trivially true since $\gcd(a^0, b^0) = \gcd(1, 1) = 1$.

For practice, let's try $P(1)$ which is

If $\gcd (a, b) = 1$ then $\gcd (a^1, b^1) = 1$, for integers $a,b$ and natural number $n$.

Again, this is trivially true, effectively stating $A \implies A$.

Induction Step

We need to show $P(n) \implies P(n+1)$.  $P(n+1)$ is

If $\gcd (a, b) = 1$ then $\gcd (a^{n+1}, b^{n+1}) = 1$, for integers $a,b$ and natural number $n$.

We assume $P(n)$ is true as the induction hypothesis. The conclusion of $P(n)$ is that $\gcd (a^n, b^n) = 1$ is true.

In summary, we assume

• $\gcd (a, b) = 1$
• $\gcd (a^n, b^n) = 1$

From exercise (i) 

$$ \boxed {\gcd (a, b) = \gcd (a, c) = 1 \iff \gcd (a, bc) = 1} $$

Taking $c=b$, we have

$$ \gcd (a, b)  = 1 \iff \gcd (a, b^2) = 1 $$

So the assumption $\gcd(a,b)=1$ gives us $\gcd(a,b^2)=1$. We can then repeatedly apply the result from exercise (i) to reach $\gcd(a,b^{n+1})=1$.

By the symmetry of gcd, that is $\gcd(x,y)=\gcd(y,x)$, a corollary of the result from exercise (i) is

$$ \boxed {\gcd (a, b) = \gcd (c, b) = 1 \iff \gcd (ac, b) = 1} $$

Similarly, taking $a=c$, we have

$$ \gcd (a, b) = 1 \iff \gcd (a^2, b) = 1 $$

So the assumption $\gcd(a,b)=1$ gives us $\gcd(a^2,b)=1$. We can then repeatedly apply the corollary of exercise (i) to reach $\gcd(a^n,b)=1$.

Now, applying the result from exercise (i) to $\gcd(a^n, b^n)=1$ and $\gcd(a^n, b)=1$ we have

$$ \gcd (a^n, b^n) = \gcd (a^n, b) = 1 \iff  \colorbox{pink}{$\gcd (a^n, b^{n+1}) = 1$} $$

Again, applying the corollary of exercise (ii) to  $\gcd(a,b^{n+1})=1$ and $\gcd (a^n, b^{n+1}) = 1$ we finally have

$$ \gcd (a, b^{n+1}) = \gcd (a^n, b^{n+1}) = 1 \iff   \colorbox{pink}{$\gcd (a^{n+1}, b^{n+1}) = 1$} $$

So we have shown that $P(n+1)$ follows from $P(n)$.

By showing both the base case and the inductive step, we have proved that if $\gcd (a, b) = 1$ then $\gcd (a^n, b^n) = 1$ where $n$ is a natural number.

Exercise (1.3).14

Disprove the following:

$$a \mid b^2 \implies  a \mid b$$

We can disprove this with a counter example. 

Let's choose $a=4$ and $b=2$.This gives us

$$ 4 \mid 4 \implies 4 \mid 2 $$

which is false. So the given statement is not true for all integers $a,b$.

Exercise (1.3).13

Prove that if $\gcd (a, b) = 1$ then for any $d$ such that $d \mid a$ we have

$$\gcd (d, b) = 1$$

We're given $\gcd (a,b) = 1$. By Bezout's Identity this means there exist integers $x,y$ such that

$$ ax + by = 1 $$

We're also given $d \mid a$, which means there exists an integer $z$ such that

$$ a = zd $$

Putting these together, we have

$$ (zd)x + by = 1 $$

More explicitly,

$$ d(zx) + by = 1 $$

Here,  the $\gcd(d,b)$ must also divide 1, and that is only possible if $\gcd(d,b)=1$.

Exercise (1.3).12

(i) Prove that if $a \mid c$ and $b \mid c$ and $\gcd (a, b) = 1$ then $(a \times b) \mid c$.

(ii) Prove that if $a_1 \mid c, a_2 \mid c, \ldots , a_n \mid c$ and $\gcd (a_j, a_i) = 1$ where $i \neq j$ then

$$(a_1 \times a_2 \times  \ldots  \times  a_n) \mid  c$$

(i) We're given $a \mid c$ and $b \mid c$, which means for some integers $j,k$

$$\begin{align} c &= ja \\ \\ c &= kb \end{align}$$

We're also given $\gcd(a,b) = 1$. By Bezout's Indentity,  there are integers $x,y$ such that 

$$ ax + by = 1 $$

Multiplying by $c$, 

$$ ax(kb) + by(aj) = c $$

Factorising,

$$ab(xk + yj) = c$$

And so we conclude $(a \times b) \mid c$

(ii) We'll prove this by induction on $n$.

Let's take the statement $P(n)$ to mean:

If $a_1 \mid c, a_2 \mid c, \ldots , a_n \mid c$ and $\gcd (a_j, a_i) = 1$ where $i \neq j$ then $(a_1 \times a_2 \times  \ldots  \times  a_n) \mid  c$.

We need to prove a base case and an induction step.

Base Case

The base case $P(2)$ is

If $a_1 \mid c, a_2 \mid c$ and $\gcd (a_1, a_2) = 1$ where $1 \neq 2$ then $(a_1 \times a_2) \mid  c$.

We proved this base case in exercise (i) above.

Induction Step

We need to show $P(n) \implies P(n+1)$.

We assume $P(n)$ as the induction hypothesis.

The statement $P(n+1)$ means:

If $a_1 \mid c, a_2 \mid c, \ldots , a_n \mid c, a_{n+1}\mid c$ and $\gcd (a_j, a_i) = 1$ where $i \neq j$ then $(a_1 \times a_2 \times  \ldots  \times  a_n \times a_{n+1}) \mid  c$.

The assumption for $P(n+1)$ that $a_1 \mid c, a_2 \mid c, \ldots , a_n \mid c, a_{n+1}\mid c$ where all $a_j, a_{i \ne j}$ are coprime, includes the assumption for $P(n)$ that  $a_1 \mid c, a_2 \mid c, \ldots , a_n \mid c$ where all $a_j, a_{i \ne j}$ are coprime. That means we have $(a_1 \times a_2 \times  \ldots  \times  a_n) \mid  c$.

That is, there exists some integer $p$ such that

$$(a_1 \times a_2 \times  \ldots  \times  a_n) p=  c$$

The additional assumption of $P(n+1)$ is that $a_{n+1} \mid c$, so there exists some integer $q$ such that

$$ a_{n+1}q = c$$

Since $a_{n+1}$ is coprime to all $a_1, a_2, \ldots, a_n$, by Bezout's identity we have, for some integers $r,s$

$$ (a_1 \times a_2 \times  \ldots  \times  a_n) r + a_{n+1} s = 1 $$

Multiplying by $c$

$$ (a_1 \times a_2 \times  \ldots  \times  a_n) ra_{n+1}q + a_{n+1} s(a_1 \times a_2 \times  \ldots  \times  a_n)p = c $$

Factorising

$$ (a_1 \times a_2 \times  \ldots  \times  a_n \times a_{n+1}) (rq + sp) = c $$

So we have $(a_1 \times a_2 \times  \ldots  \times  a_n \times a_{n+1})  \mid c$.

We have shown $P(n) \implies P(n+1)$.

By showing the base case and the induction step, we have shown by induction that if $a_1 \mid c, a_2 \mid c$ and $\gcd (a_1, a_2) = 1$ where $1 \neq 2$ then $(a_1 \times a_2) \mid  c$.

Exercise (1.3).11

Prove that if integers $a ≠ 0$ and $b$ such that $a \mid b$ then $\gcd (a, b) = |a|$.

Since $a \mid b$, then for some integer $k$ we have

$$ b = ak $$

Substituting

$$ \begin{align} \gcd(a,b) & = \gcd(a, ak) \\ \\ &= \lvert a \rvert \gcd (\frac{a}{a},\frac{ak}{a}) \\ \\ &= \lvert a \rvert \end{align}$$

The penultimate line uses Proposition 1.5 that if $\gcd (a, b) = g$ then $\gcd (\frac{a}{g}, \frac{b}{g})=1$. We make use of $a \neq 0$ to ensure the division is valid.

The multiplier is $\lvert a \rvert$ because by definition a gcd is greater than zero.

Exercise (1.3).10

Prove that if there are integers $x$ and $y$ such that $ax + by= n$ then $g \mid n$ where $g= gcd (a, b)$.

If $g=\gcd(a,b)$ then we have $g \mid a$ and $g \mid b$. That is, for some integers $c,d$

$$\begin{align} a &= cg \\ \\ b &= dg \end{align}$$

Substituting for $a$ and $b$ in $ax + by = n$ gives us

$$\begin{align} (cg)x + (dg)y & = n \\ \\ g(cx + dy) & = n \end{align}$$

This tells us $g \mid n$.