# 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

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

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.

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