1
$\begingroup$

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!

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

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Jeel Shah Apr 6 '14 at 5:10
  • $\begingroup$ 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. $\endgroup$ – Nicholas Stull Apr 6 '14 at 15:54
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Jared Apr 6 '14 at 6:48
  • $\begingroup$ 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$. $\endgroup$ – Jared Apr 6 '14 at 7:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.