# Show that if $a^n\mid b^n$, then $a\mid b$.

I have a question from a sample exam I have difficulties to solve:

Show that if $a^n\mid b^n$, then $a\mid b$.

I don't have any idea how to start. I'd like to get helped. thanks!

• Assume $a\not\mid b$. Can you prove that $a^n\not\mid b^n$? – Ian Coley Sep 17 '13 at 20:34
• Sorry. How can i prove it? – MaxGaussian Sep 17 '13 at 20:45
• There are some good answers below. – Ian Coley Sep 17 '13 at 20:48
• You should give some background, at the very least. What theorems in arithmetics do you know, that you think that might be related with this problem? – Giuseppe Negro Sep 17 '13 at 20:57

## 4 Answers

Hint Write the prime factorizations of $a,b$. What does $a^n|b^n$ tell you?

Since someone is not happy with the answer, here are extra details.

Let $a=p_1^{a_1}..p_k^{a_k}$ and $b=p_1^{b_1}..p_k^{b_k}$. We can write the same primes since the powers can be $0$.

Then $a^n |b^n$ means

$$a=p_1^{na_1}..p_k^{na_k}| p_1^{nb_1}..p_k^{nb_k} \Rightarrow na_i \leq nb_i \Rightarrow a_i \leq b_i$$

@Downvoter, can you please explain what is wrong with this answer?

P.S. Here is a neat Algebraic solution, not appropriate for NT though.

There exists some integer $c$ so that $b^n=a^nc$. Let $x= \frac{b}a$. Then $x^n=c$, thus $x$ is an algebraic integer which is rational.

Outline of proof.

First we prove that if $\gcd(a,b)=1$ and $a^n\mid b^n$ then $a=1$.

Proof: We know that if $\gcd(a,b)=1$ then $\gcd(a^n,b^n)=1$. if $a^n\mid b^n$, that means that $a^n=\gcd(a^n,b^n)=1$.

General case: If $a^n\mid b^n$, let $d=\gcd(a,b)$, and let $a_0=a/d, b_0=b/d$. Then $a_0^n\mid b_0^n$ and $(a_0,b_0)=1$, so $a_0=1$ by the first proof. But that means that $a=d=(a,b)\mid b$.

The fact that $(a,b)=1\implies (a^n,b^n)=1$ can be proven without prime factorizations - it follows by solving $ax+by=1$ and raising that to the $(2n-1)^{\text{th}}$ power.

This is a more advanced solution.

Since $a^n\mid b^n$, there is an integer $c$ so that $a^nc=b^n$, so $c=(b/a)^n$. Let $x=b/a$. We have that $x$ satisfies the equation $t^n-c=0$ in $\mathbb{Z}[t]$, this is a monic equation, so we have that $x$ is integral over $\mathbb{Z}$ and lives in $\mathbb{Q}$. Since any UFD is integrally closed (and $\mathbb{Z}$ satisfies unique factorization), we have that $x\in \mathbb{Z}$ just as we wanted.

Or you can try to prove directly that if you have a rational such that a positive power lands you in $\mathbb{Z}$, then your starting rational was an integer.

Added:

Theorem: If $x\in \mathbb{Q}$ satisfies a monic (meaning the leading coefficient is $1$) polynomial in $\mathbb{Z}[t]$ (meaning that the coefficients will be integers), then $x\in \mathbb{Z}$

Proof: Let $x=b/a$ and assume that $x$ is a reduced fraction (meaning that $b$ and $a$ have no common factors). Let $f(t)=t^n+...+c_0$ be such that $f(x)=0$ then $$(b/a)^n+c_{n-1}(b/a)^{n-1}+...+c_0=0$$Multiplying by $a^n$ and moving terms we get $$b^n=-a(c_{n-1}b^{n-1}...+a^{n-1}c_0)$$, so we have that $a\mid b^n$. If there were any primes $p$ that divide $a$, then since $a\mid b^n$, then we would have that $p\mid b^n$ which implies that $p\mid b$, which is a contradiction because then $a$ and $b$ would have $p$ as a common factor. Hence, $a$ has no prime divisors, implying that $a$ is $\pm 1$, meaning $x$ is an integer.

• So you are assuming a much more general theorem to prove this special case? (And N.S. below already gave this answer.) At the very least, note to the poor OP, who almost certainly doesn't know what you are talking about, that this is an advanced proof. – Thomas Andrews Sep 17 '13 at 20:54
• @ThomasAndrews Oh I didn't see that NS gave this answer. I saw that he gave a hint about prime factorization. That must have been added later. I can expand on it :) – Daniel Montealegre Sep 17 '13 at 20:56
• @ThomasAndrews I added a little more. Hopefully the OP could benefit from it, and if not, maybe someone that randomly stumbles upon this post :) – Daniel Montealegre Sep 17 '13 at 21:10
• @ThomasAndrews Added. – Daniel Montealegre Sep 17 '13 at 21:13

Yet another proof: It $a \not\mid b$, then up to the gcd, you can suppose that $a$ and $b$ are relatively prime. Thus, by Bézout's theorem there exist $u \in \Bbb Z$ such that $bu \equiv 1 \pmod{a}$. Taking this to the power $n$ we get $b^nu^n \equiv 1 \pmod{a}$ which is obviously an obstruction to $a^n \mid b^n$.