If $a$ and $b$ are relatively prime then so are $a$ and $b^n$ for every positive integer $n$

Question

I have been asked to prove the following via induction (as the textbook as suggested):

If $a$ and $b$ are relatively prime then so are $a$ and $b^n$ for every positive integer $n$

So, I did the following but I'm stuck at the induction step.

Base Case $n=1$

$(a,b^1) =(a,b)= 1$. This is true via the definition provided in the problem.

Inductive Hypothesis

Suppose, this is true for all $n$. $$(a,b^n) = 1$$

Inductive Step for $n+1$

\begin{align} &(a,b^{n+1}) = 1 \\ &(a,b^nb) = 1 \\ \end{align}

Now, I am stuck from here. Quite honestly, I think have done the entire induction wrong. what I would have done next is convert the $\gcd$ into the algebraic form of $ka + lb^nb = 1$ but I'm not too sure.

Please provide only hints.

Thanks a lot!

Answer 1

Since you only want hints:

Try to prove the following identity: $$\gcd(a,b\cdot c) = \gcd(a,b)\cdot\gcd(a,c)$$ This identity basically finishes your proof, given your induction hypothesis.

Also, regarding your induction hypothesis, you should change "true for all $n$" to "true for all $n\leq k$". Otherwise, you are assuming what you want to prove. After that little change, the inductive step is then to prove this is true for $n = k+1$.

Answer 2

Hope to provide a valuable new proof. The other one is very nice (+1) !

Inductive step: by hypothesis $(a, b^i)=1 $ for every $ i \leq k $ .

Suppose $(a, b^{k+1})> 1$. Let $ p $ be a prime such that $ p \mid a $ and $ p \mid b^{k+1} $. So $ p\mid b $ (definition of prime) so $ p \mid (a, b)=1 $. Absurd, so it must be $(a, b^n)=1 $ for every $ n $ natural.

Another way (not inductive) is to write down the unique factorization of $ a $, $ b $ and $ b^n $ and trying to continue from here.

The first proof is a "very very light " induction, in other words induction is not so necessary here (in the sense we can prove the results easily without this technique). Anyway its better to know other approaches:)

Answer 3

Inductive Step:

If $\gcd(a, b^n) = 1$ then $\forall \alpha, \beta\in \mathbb{I}: \alpha\beta = a \rightarrow \left(\gcd(\alpha, b^n) = 1 \wedge \gcd(\beta, b^n) = 1\right)$. Now let's try to attempt to prove that given the above and that $\gcd(a, b) = 1$, that $\forall \alpha, \beta \in \mathbb{I}: \alpha\beta = a \rightarrow \left(\gcd(\alpha, b^{n + 1}) = 1 \wedge \gcd(\beta, b^{n + 1}) = 1\right)$.

This seems like a candidate for proof by contradiction. Let's assume the following: $\exists \alpha,\beta \in \mathbb{I}: \alpha\beta = a \rightarrow \left(\gcd(\alpha, b^{n + 1}) \neq 1 \vee \gcd(\beta, b^{n + 1}) \neq 1\right)$. Right away this assumes we can find at least one value $\alpha \neq 1$ such that:

$$ a = \alpha\beta \wedge b^{n + 1} = \alpha\lambda b^n $$

Where $\alpha\lambda = b$ and let's assume we have found such a value such that $\gcd(a, b^{n + 1}) = \alpha \neq 1$ (which would force that $\gcd(\beta, \lambda b^n) = 1$). $\gcd(a, b^n) = 1$ is a given, therefore $\gcd(a, b^{n + 1}) = \gcd(\alpha\beta, \alpha\lambda) = \alpha$. However, we assumed that $\gcd(\alpha\beta, \alpha\gamma) = \gcd(a, b) = 1$. This contradicts the assumption that $\alpha \neq 1$, therefore if $\gcd(a, b^n) = 1$ and $\gcd(a, b) = 1$ then $\gcd(a, b^{n + 1}) = 1$.