Find all positive integers $b$ for which there exists a positive integer $a$ with the following properties: - $a$ is not a divisor of $b$. - $a^a$ is a divisor of $b^b$
Problem
Source: TST egmo 2021 p2
Tags: number theory
30.03.2022 07:43
The answer is: All composite numbers expect the form $pq$ such that $p<q<2p $ $p, q$ are primes Hint:Take minimal prime and add one to exponent.
30.03.2022 14:24
The answer is all positive integers expect prime powers and numbers in the form $pq$ where $2p>q>p$ and $p,q$ are prime numbers. If $b=p^{\alpha}$, then clearly $a$ in the form $p^x$. If $x\ge \alpha$, then $a^a>b^b$, contradiction. And if $x<\alpha$, then $a|b$, contradiction again. Now, assume that $b$ has at least $2$ prime divisors. Let $b=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ where $k\ge 2$ and $p_1$ be the smallest prime divisor of $b$. See that if $k\ge 3$ or $\alpha_2\ge 2$ or $p_2\ge \frac{(\alpha_1+1)p_1}{\alpha_1}$, then $a= p_1^{\alpha_1+1}$ works as $p_2^{\alpha_2}\cdots p_k^{\alpha_k}\ge \frac{(\alpha_1+1)p_1}{\alpha_1}$. The only case left is $b=p_1^{\alpha_1}\cdot p_2$ where $\frac{(\alpha_1+1)p_1}{\alpha_1}>p_2$. See that if $p_1^{\alpha_1}\ge 2p_2$, then $a=p_2^2$ works. Assume that, $p_1^{\alpha_1}<2p_2$. If $\alpha_1\ge 2$, then, $3p_1\ge \frac{2(\alpha_1+1)p_1}{\alpha_1}>2p_2> p_1^{\alpha_1} $. Hence, $3>p_1^{\alpha_1-1}$. This is true only if $\alpha_1=2$ and $p_1=2$. But, then $p_2<\frac{(\alpha_1+1)p_1}{\alpha_1}=3\Rightarrow p_2=2$. But $p_2>p_1$ so we get a contradiction. Hence, $\alpha_1=1$. Then, $2p_1>p_2$. If there exist such $a$, then $p_1^2|a$ or $p_2^2|a$ but for these values $a^a\not |b^b$. Therefore, for these values of $b$, such $a$ does not exist, done.