# For any positive integers $a,b$, one has $a^4|b^3$ implies $a|b$?

This is an old exam problem I found online. For any positive integers $a,b$, one has $a^4|b^3$ implies $a|b$. Clearly if $a^4|b^3$, then $a|b^3$. It seemed simple on first reading, but I can't figure out how to show that $a|b$ follows, since $a$ is not necessarily prime. Is there some observation I'm missing?

-

This may be a situation where it is enlightening to ask (and answer) a more general question.

Problem: let $m$ and $n$ be positive integers. Show that the following are equivalent:
(i) For all positive integers $a,b,$ $a^m \ | \ b^n$ implies $a \ | \ b$.
(ii) $m \geq n$.

All of the other answers given should generalize to this situation. As people who are familiar with my number theory notes probably know, I like arguments using the functions $\operatorname{ord}_p(n)$, defined to be the largest number $a$ such that $p^a \ | \ n$. The "local to global principle" for divisibility in the integers is: for $x,y \in \mathbb{Z}^+$, $x \ | \ y$ iff for all primes $p$, $\operatorname{ord}_p(x) \leq \operatorname{ord}_p(y)$. [More generally, this is true in any unique factorization domain. Added: in fact, with appropriate modifications it is true in any Krull domain. This actually came up in my own research recently...]

In the present situation, $a^m \ | \ b^n$ implies that for all prime numbers $p$,

$m \cdot \operatorname{ord}_p(a) = \operatorname{ord}_p(a^m) \leq \operatorname{ord}_p(b^n) = n \cdot \operatorname{ord}_p(b)$.

So if $m \geq n$, we have

$n \cdot \operatorname{ord}_p(a) \leq m \cdot \operatorname{ord}_p(a) \leq n \cdot \operatorname{ord}_p(b)$, so

$\operatorname{ord}_p(a) \leq \operatorname{ord}_p(b)$.

This shows that (ii) implies (i). I'll leave the other direction to the reader as a simple exercise in understanding what's going on here, with the hint that one should prove the contrapositive: assume $m < n$ and take $a$ and $b$ to be powers of the same prime number.

-
Thanks for this generalization of the problem. – yunone Oct 4 '10 at 0:37

It's simple: $\rm\ a^3|b^3\ \Rightarrow\ (b/a)^3\in\mathbb Z\ \Rightarrow\ b/a\in \mathbb Z\ \$ by the Rational Root Test.

To elaborate, the Rational Root Test implies, as a special case, that if $\rm\ r\$ is a rational root of an integer coefficient polynomial that is monic (i.e. has leading coefficient equal to 1), then $\rm\:r\:$ is necessarily an integer. Hence, in the case above, since $\rm\ r = b/a\$ is a root of the monic polynomial $\rm\ x^3 - n\$ for some $\rm n\in \mathbb Z\:$, we deduce that $\rm\ r = b/a\$ is an integer.

This is merely a special case of results equivalent to the irrationality of $\rm\:n\:$'th roots. Namely, any domain $\rm Z$ satisfying the following equivalent conditions is called root-closed. This is a weaker condition than being integrally-closed, i.e. satisfying the monic Rational Root Test.

THEOREM $\:$ TFAE for $\rm\: a,b\:$ in domain $\rm\:Z\:,\ \: r \in Q \:=\:$ fraction field of $\rm\: Z\:,\ n\in \mathbb N$

(1) $\rm\ \ r = \sqrt[n]a \ \Rightarrow\ r \in Z$

(2) $\rm\ \ r^n \in \:Z \:\ \Rightarrow\ r \in Z$

(3) $\rm\ \ \ a^n\:|\:b^n \:\ \Rightarrow\:\ a\:|\:b$

(4) $\rm\ \ (a^n) = (b^n,\: c^n) \ \Rightarrow\ (a) = (b,c)\$ as ideals in $\rm\:Z$

-
Thanks Bill, this was not an approach I would have thought of. – yunone Oct 4 '10 at 0:36

Suppose $p$ is prime and $p^k$ divides $a$ (and no higher power of $p$ divides $a$). Then $p^{4k}$ divides $a^4$ and hence $p^{4k}$ divides $b^3$. It follows that $p^{4k/3}$ divides $b$. In particular, $p^k$ must divide $b$ since $4k/3 \geq k$. Doing this for all $p$ shows that $a|b$.

-
What about when $4k/3$ is not an integer? For example, let $a=2$, $b=2^2$. Then $2^4|2^6$, but $2^{4/3}$ does not divide $4$, so in general from $p^{4k}|b^3$ it doesn't necessarily follow that $p^{4k/3}|b$, unless I'm missing something. – yunone Oct 1 '10 at 3:58
@xdfm, I took it to mean integer division, meaning the largest integer not greater than 4k/3. – Jonas Meyer Oct 1 '10 at 5:50
@xdfm: You are correct (and I should have been more careful in my writing), but if you interpret 4k/3 as Jonas suggested, this problem will evaporate. (This is one of the reasons I wrote "4k/3 $geq$ k", instead of "4k/3 > k". – Jason DeVito Oct 1 '10 at 13:08

As you said, $a\vert b$. Hence every prime factor of $a$ is a prime factor of $b$. So we have

$$a = p_1^{m_1} \dots p_r^{m_r} \qquad \text{and} \qquad b = p_1^{n_1} \dots p_r^{n_r} q_1$$

where $q_1$ is a positive integer number such that none of the $p_i$ divides it. So in order to see that $a\vert b$ it's enough to prove that

$$n_i \geq m_i \qquad \text{for all} \ i = 1, \dots , r \ .$$

Assume $n_i < m_i$ for some $i$. Now,

$$a^4 \vert b^3 \qquad \Longleftrightarrow \qquad b^3 = a^4q_2$$

for some positive integer $q_2$. Thus

$$p_1^{3n_1} \dots p_r^{3n_r} q_1^3 = p_1^{4m_1} \dots p_r^{4m_r}q_2 \ .$$

Now, $q_2$ may have, or may have not, some of the $p_i$ as prime factors (but $q_1$ hasn't). In any case, we must have

$$3n_i = 4m_i + t_i \qquad \text{for all} \ i= 1, \dots , r \ ,$$

where $t_i \geq 0$ for all $i$. But we have assumed that there is some $i$ such that $n_i < m_i$. So, for this $i$, we would have

$$4m_i + t_i = 3n_i < 3m_i \qquad \Longleftrightarrow \qquad m_i + t_i < 0 \ .$$

But this is impossible, since both $m_i, t_i \geq 0$. A contradiction. Hence $n_i \geq m_i$ for all $i$ and so $a\vert b$.

-