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?
 A: 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. 
A: It's simple: $\rm\ a^3\mid b^3\ \Rightarrow\ \color{#0a0}{(b/a)^3 = n}\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 $\color{#c00}1$), then $\rm\:r\:$ is necessarily an integer (since the test implies that the least terms denomintor of $\,\rm r\,$ divides $\color{#c00}{1}).\,$ Hence above, since $\rm\ r = b/a\ $ is a root of the monic polynomial $\rm\, \color{#0a0}{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$
A: 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$.
A: 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$.
