Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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?

share|cite|improve this question
up vote 7 down vote accepted

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.

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

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

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

share|cite|improve this answer

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.