# Proof by induction; $a^n$ divides $b^n$ implies $a$ divides $b$

I want to prove by induction that $a^n \mid b^n$ implies that $a \mid b$ holds for all integers $n\geq 1$.

Clearly for $n=1$ this is true, since if $a \mid b$, then $a \mid b$.

Suppose this is true for some $n = k$. Then $a^k \mid b^k$, so $a|b$.

$a^k \mid b^k$ means there exists some integer $m$ such that $b^k = ma^k$, and $a \mid b$ means there exists an integer $r$ such that $b=ra$.

Then we can multiply both sides of the above equality by any constant, namely $b$.

Then $b \cdot b^k = bma^k$

so $b^{k+1} = (ra)ma^k = rma^{k+1}$

which means that $a^{k+1} \mid b^{k+1}$ completing the induction step, and thus proving that for all integers $n \geq1$ the original statement holds.

Are there any logical holes in the proof?

Let $a,b$ be integers and let $P(k)$ be the statement "$a^k \mid b^k$ implies $a \mid b$." You are trying to prove by induction that $P(k)$ is true for all $k\in \mathbb{N}$.

You start out by proving the base case $P(1)$, which is fine. Then you say "suppose this is true for some $k$," by which I mean you are supposing that $P(k)$ is true. But then you say, "then $a^k \mid b^k$." This does not follow from $P(k)$, since $P(k)$ says nothing about whether $a^k$ divides $b^k$ or not, just about what happens if it does.

What you need to do is show that if $P(k)$ is true, then $P(k+1)$ is also true. Others have already talked about how to approach this, I just wanted to clarify a bit more what goes wrong with your attempt.

• Nice explanation, Tara. +1 – mrs Mar 30 '13 at 7:01

That doesn't quite work. What you need to do is assume that for some $k\geq 1$ we have $a^k\mid b^k$ implies $a\mid b$ for all integers $a,b$. Now, suppose that $a^{k+1}\mid b^{k+1}$ for some $a,b$, and show that $a\mid b$. Given the inductive hypothesis, it will be enough for you to show that $a^k\mid b^k$.

Hint $\$ We may assume $\rm\:(a,b)=1\:$ by canceling any common factor. Then it suffices to show that $\rm\:a\mid b^n\:\Rightarrow\:a\mid 1\:$ (so $\rm\:a\mid b).\:$ By Euclid's Lemma $\rm\ a\mid b(b^k)\:\Rightarrow\:a\mid b^k,\:$ so $\rm\: a\mid 1\:$ by induction.

Remark $\$ Alternatively if $\rm\:(a,b)=1,\:$ and $\rm\:b^n/a^n = m\in\Bbb Z\:$ then $\rm\rm\: b/a\:$ is a rational root of $\rm\:x^n - m,\:$ so, by RRT = Rational Root Test, $\rm\:b/a\in \Bbb Z,\:$ i.e. $\rm\:a\mid b.$

The first proof essentially uses an inductive extension of Euclid's Lemma:  if $\rm\ a\$ is coprime to all $\rm\:b_i\:$ then it is coprime to their product. This is the key lemma at the core of the proof of RRT, so it too may be considered an inductive proof, since it invokes said inductive extension of Euclid's Lemma. If that doesn't satisfy the whatever fuzzy notion of "true inductive proof" one employs, then this proof certainly will. It is a little-known proof of monic RRT by induction on degree. As a particular case, one can prove cube-roots irrational by using irrationality proofs of square-roots!

As already pointed out by Cameron Buie, it does not work. I would recommend you some other approach: let $M_a$ be the multiset of prime factors of $a$, that is, for any prime number $p$, $M_a(p) = \max\{k \in \mathbb{N} : p^k \mid a\}$. Now, $a \mid b \iff M_a \subset M_b$, however, $M_{a^k}(p) = k\cdot M_a(p)$, hence $M_{a^k} \subset M_{b^k}$ implies $M_a \subset M_b$.

Good luck!

• This is a good approach, but doesn't very naturally lead to a proof by induction. – Tara B Mar 29 '13 at 23:52