Question

Use induction to show that if $\left(a,b^n\right)=1$, then for all $n\ge 1$.

Short answer

It is proved that $\left(a,b^n\right)=1,\forall n\ge 1$.

Step-by-step solution

Linear Combination:

Let $d$ be the largest integer that divides the integers $aandb$. Then there exist integers$uandv$such that:

$d=au+bv$

Where, $a,b\ne 0$.

Proof using Theorem 1.2:

Let recursively, we have: $b^1=b$,

Then,$b^{n+1}=b·b^n,\forall n\ge 1$.

Now, using hypothesis for all $k\ge 1$, we have:

$\begin{array}{rcl}\left(a,b^k\right)& =& 1\\ \left(a,b·b^k\right)& =& 1\\ \left(a,b^{k+1}\right)& =& 1\end{array}$

Hence, it is proved that $\left(a,b^n\right)=1,\forall n\ge 1$.