Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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

share|cite|improve this question
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
up vote 3 down vote accepted

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$

share|cite|improve this answer
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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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