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

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.

Thanks a lot!

• In fact you can do better: $(a,b)=1$ implies that $(a^m,b^n)=1$ for all $m,n\in N$. – Rodney Coleman Apr 7 '14 at 9:22

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

• So basically, once I prove what you have given - I do that for $k+1$ or in other words $\gcd(a,b^{k+1})$ right? – Jeel Shah Apr 6 '14 at 5:10
• Exactly. And all you must do, once you have $\gcd(a,b^{k+1})$ is note this is exactly (by that statement) $\gcd(a,b)\gcd(a,b^k)$. Now, use the induction hypothesis. – Nicholas Stull Apr 6 '14 at 15:54

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:)

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

• And just for the record, it's far easier to prove this directly (as has been stated). We can simply assume $a = \prod p_i^{n_i}$ and $b = \prod p_i^{n_i}$. This gives $b^m = \prod p_i^{n_im}$ (where $p_i$ are prime numbers $\neq 1$). Then if $\gcd(a, b) = \alpha\neq 1$ then it's true that $a$ contains at least one of the prime factors of $b$. If not, then $b^m = \prod p_i^{n_im}$ also contains no prime factors of $a$ and thus is also relatively prime to $a$. – Jared Apr 6 '14 at 6:48
• I should also state that it should be possible to show that if $\gcd(a, b^n) = 1$ (for $n > 0$) then $\gcd(a, b) = 1$. I used both both assumptions to prove $\gcd(a, b^{n + 1}) = 1$ but, like I say, it should follow that if $\gcd(a, b^n) = 1$ then $\gcd(a, b) = 1$. – Jared Apr 6 '14 at 7:06