If $a^a$ divides $b^b$, then $a$ divides $b$?

Question

Consider $a$ and $b$, both positive integers. Is it true that $a^a$ divides $b^b$ implies $a$ divides $b$?

I can't seem to figure out this proof. My intuition is to use the fundamental theorem of arithmetic to break each number into its prime components, however I haven't been able to come up with a solution. Any help would be appreciated.

Answer 1

This is not true in general. The fact that $4^4$ divides $10^{10}$ would be the smallest counterexample, I think.

So why does the proposition fail to hold? For any integer $n$, $\operatorname{rad}(n)$ (for "radical") is the number with the same primes in its prime factorisation as $n$, but all powers are $1$. For instance, $\operatorname{rad}(12) = 6$ and $\operatorname{rad}(98) = 14$. Then we do have "$a^a$ divides $b^b$ implies that $\operatorname{rad}(a)$ divides $\operatorname{rad}(b)$", i.e. every prime that appears in the prime factorisation of $a$ appears in the prime factorisation of $b$. However, we have no way of controlling, for any given of those primes, that the power of that prime is smaller in $a$ than in $b$. We just know that for any given of those primes, $a$ times its exponent in $a$ is less than $b$ times its exponent in $b$. Thus, if $b$ is large enough, and just contains the right primes, we get $a^a$ divides $b^b$, no matter how many times those primes divide $b$.

Answer 2

Exceptions will be of the following form:

Suppose the prime factorisation of $a$ is $a=p_1^{e_{a_1}}p_2^{e_{a_2}}\cdots p_n^{e_{a_n}}$ with all the $p_i$ distinct primes and with all the $e_{a_i}\ge 1$ and at least one $e_{a_i}\ge 2$. Then

• $b$ is divisible by $p_1p_2\cdots p_n$ and can be written as $b=c p_1^{e_{b_1}}p_2^{e_{b_2}}\cdots p_n^{e_{b_n}}$ with $c$ coprime to $a$ and all the $e_{b_i}\ge 1$
• for at least one $i$ there is $e_{b_i}\lt e_{a_i}$ so $a$ does not divide $b$
• for all $i$ there is $ae_{a_i}\le be_{b_i}$ so $a^a$ divides $b^b$

So reversing this to generate all possible exceptions

• choose a positive number $n$ of distinct primes $p_1,p_2,\ldots,p_n$
• choose the same number $n$ of positive integers $e_{a_1},e_{a_2},\ldots,e_{a_n}$ not all $1$
• choose the same number $n$ of positive integers $e_{b_1},e_{b_2},\ldots,e_{b_n}$ where for at least one $i$ you have $1 \le e_{b_i}\lt e_{a_i}$
• find a number $c$ coprime to $p_1p_2\cdots p_n$ and at least $p_1^{e_{a_1}-e_{b_1}}p_2^{e_{a_2}-e_{b_2}}\cdots p_n^{e_{a_n}-e_{b_n}} \displaystyle \max_i\left(\frac{e_{a_i}}{e_{b_i}}\right)$
• take $a=p_1^{e_{a_1}}p_2^{e_{a_2}}\cdots p_n^{e_{a_n}}$ and $b=c p_1^{e_{b_1}}p_2^{e_{b_2}}\cdots p_n^{e_{b_n}}$

Answer 3

If $ a^a\mid b^b $, then for every prime $ p$ such that $ p\mid a$ we must have $ p\mid b $ because $ p\mid b^b $ implies $ p\mid b $. Thus we can write the prime factorizations of $ a$ and $ b$ as $a=p_1^{\alpha_1}\cdots p_r^{\alpha_r} $ and $ b=p_1^{\beta_1}\cdots p_r^{\beta_r}\cdots $. Therefore $$ a^a=p_1^{a\alpha_1}\cdots p_r^{a\alpha_r} ,$$ $$ b^b=p_1^{b\beta_1}\cdots p_r ^{b\beta_r}\cdots $$

So if $ a^a\mid b^b $ we must have $ a\alpha_i\le b\beta_i $, for every $1\le i\le r$, but this doesn't mean that $\alpha_i\le \beta_i $ for every $ i $. It could happen that for some $ i$, $ \alpha_i> \beta_i $ , which would imply that $ a \not\mid b $.

As a example we have the counterexample given in the first answer: $4^4\mid 10^{10} $, but $4\not\mid 10$. In this case $ r=1, p_1=2, \alpha_1=2$ and $\beta_1=1$. So we have $4\cdot 2\le 10\cdot 1$, but $2> 1$.