# Use a particular method to prove if $a^n \mid b^n$ then $a\mid b$

A question in my tutorial asks to use the fact (can be used without proof) that

$(a,b)=(a,c)=1 \Rightarrow (a,bc)=1$

to prove:

if $a^n \mid b^n$ then $a\mid b$.

I did the following, but my tutor marked it as wrong. I have tried to find the error without success.

May I know where is the error? Sincere thanks.

Assume $a^n \mid b^n$.

$b^n=a^n\cdot k$ , $k\in \mathbb{Z}$

Let $d:=(a,b)$.

$(\frac{a}{d},\frac{b}{d})=1$

By the fact above, $(\frac{a}{d},(\frac{b}{d})^{n-1})=1$.

Note that since $(\frac{b}{d})^n=(\frac{a}{d})^n\cdot k$, so $\frac{a}{d}\mid(\frac{b}{d})(\frac{b}{d})^{n-1}$. This, in addition to $(\frac{a}{d},(\frac{b}{d})^{n-1})=1$, yields $\frac{a}{d}\mid\frac{b}{d}$. (Euclid's Lemma)

Hence $a\mid b$.

-
what do you mean by $(a,b)$? a representation of $a/b\in\mathbb{Q}$? or the gcd of $a$ and $b$? –  akkkk Aug 29 '12 at 12:27
The obvious person to ask is your tutor. But it looks OK to me. –  Gerry Myerson Aug 29 '12 at 13:05
@Auke $(a,b)$=gcd of a and b –  yoyostein Aug 29 '12 at 13:21

Your proof is correct, viz. by cancelling $\rm\:(a,b)\:$ one reduces to the case $\rm\:(a,b) = 1,\:$ which follows immediately by inductive application of Euclid's Lemma.

The proof is a special monic binomial case of the analogous proof of the Rational Root Test (RRT), since for $\rm\:c = b/a\:$ we have $\rm\:c^n = k\in \Bbb Z,\:$ so $\rm\:c\:$ is a root of $\rm\:x^n - k\:$ so RRT implies $\rm\:c\in \Bbb Z.\:$

In fact, more generally, the Freshman's Dream for gcds is true $\rm\:(a^n,b^n) = (a,b)^n$

-
In brief terms, any rational algebraic integer is a rational integer. –  awllower Aug 30 '12 at 4:09
Yes, that's the monic case of RRT; said equivalently $\Bbb Z$ is integrally-closed (in $\Bbb Q).$ –  Bill Dubuque Aug 30 '12 at 4:19

If $(a,bc)\neq 1$, then there is a prime number $p$ such that $p \mid a$ and $p \mid bc$. But $p \mid bc \Rightarrow p \mid b$ or $p \mid c$. Then we have $p \mid a$ and $p \mid b, \Leftrightarrow (a,b) \neq 1$ or $p\mid a$ and $p\mid c, \Leftrightarrow (a,c) \neq 1$, contradiction. Sorry I proved what we don't need.

If $a$ does not divide $b$. then there is $p$ prime such that $p \mid a$ but $p$ does not divide $b$. Then $p^n \mid a^n$ but $p^n$ does not divide $a^n$. Then $a^n$ does not divide $b^n$. Contradiction.

-
How does this answer OP's question (which was, where was OP's error?)? –  Gerry Myerson Aug 29 '12 at 13:53
If $a$ does not divide $b$ you can't conclude that there is a prime number $p$ such that $p \mid a$ but $p \not\mid b$. $8$ does not divide $4$ but $2$ divides both of them. –  some1.new4u Sep 11 '13 at 5:35