(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.