For postive integers $k,n$, let $$f_k(n)=\sum_{m\mid n,m>0}m^k$$Find all pairs of positive integer $(a,b)$ such that $f_a(n)\mid f_b(n)$ for every positive integer $n$.
Problem
Source: 2017 Taiwan TST Round 1
Tags: number theory
13.04.2018 18:04
I'm doing and writing this while I'm a bit drunk/sleepy, so my apology if it's wrong. Please let me know if it is so. It's enough to find such $(a,b)$ that satisfies the condition when $n$ is a prime power, say $n=p^k$ for prime $p$ and positive integer $k$. Choosing $k=1$ gives $p^a+1\mid p^b+1\implies b=ta$ for some odd number $t$. Now, we have $f_a(p^k)=\frac{p^{(k+1)a}-1}{p^a-1}$ and $f_b(p^k)=\frac{p^{(k+1)ta}-1}{p^{ta}-1}$. For any odd prime $r$ that $r\mid f_a(p^k)$, let $\ell =\mathrm{ord}_r (p)$. Note that $\ell \mid (k+1)a$. We get that $$\nu_r(f_a(p^k)) =\begin{cases} (\nu_r(p^{\ell} -1)+\nu_r(\frac{(k+1)a}{\ell}))-(\nu_r(p^{\ell} -1)+\nu_r(\frac{a}{\ell}))=\nu_r(k+1), & \text{ if }r\mid p^a-1 \\ \nu_r(p^{\ell} -1)+\nu_r(\frac{(k+1)a}{\ell}), & \text{ if }r\nmid p^a-1 \end{cases}.$$The similar relation holds when $a$ is replaced by $b$. If $t\geqslant 3$, i.e., $b>a$. Consider $p=5$ and let $r$ be a prime number that divides $p^b-1$ but doesn't divide $p^t-1$ for any $1\leqslant t<b$. Also, choose $k+1=b$. We get that $$r\nmid p^a-1\implies \nu_r (f_a(p^k)) =\nu_r(p^{\ell} -1)+\nu_r\left( \frac{(k+1)a}{\ell}\right)=\nu_r (p^b-1)+\nu_r (a),$$while $r\mid p^{ta}-1\implies \nu_r(f_b(p^k))=\nu_r (k+1)=\nu_r (b)$. But since $r\mid p^{r-1}-1$, we get that $b\leqslant r-1\implies \nu_r(a)=\nu_r (b)=0$. So, $\nu_r (f_a(p^k)) <\nu_r (f_b(p^k))$. Contradiction. Hence, the only answer is $(a,b)=(c,c)$ for every positive integer $c$.
13.04.2018 18:07
ThE-dArK-lOrD wrote: I'm doing and writing this while I'm a bit drunk... That's dangerous; never drink and derive.
13.04.2018 20:03
If $t>1$ you can set $k=t-1$ and get a contradiction through LTE.
13.04.2018 20:59
Lamp909 wrote: If $t>1$ you can set $k=t-1$ and get a contradiction through LTE. Elaborate please.
14.04.2018 14:24
ThE-dArK-lOrD wrote: I'm doing and writing this while I'm a bit drunk/sleepy, so my apologize if it's wrong. Please let me know if it's wrong. Total bro,someone wants to fight when they're drunk,someone wants to sleep,you wanna solve problems,now that's dedication!
15.04.2018 23:02
Wait is below wrong if not it is quite short solution . It is clear that $b=ak $ where k is odd integer. If $k\neq 1$ then take $n=p^{q-1} $ where $q|k $ .This easily gives contradiction. So $b=a $ Note:I apologize if this is wrong or same with ThE-dArK-lOrD's (I didnot read his solution)
16.04.2018 08:34
tenplusten wrote: Wait is below wrong if not it is quite short solution . It is clear that $b=ak $ where k is odd integer. If $k\neq 1$ then take $n=p^{q-1} $ where $q|k $ .This easily gives contradiction. So $b=a $ Note:I apologize if this is wrong or same with ThE-dArK-lOrD's (I didnot read his solution) Your solution is absolutely correct and concise,my friend(coincides with my solution).It seems people can find easy solutions when they are not drowsy!
17.06.2020 11:22
tenplusten wrote: If $k\neq 1$ then take $n=p^{q-1} $ where $q|k $ .This easily gives contradiction. So $b=a $ Can someone please explain why we get a contradiction?
07.03.2024 06:58
aq th roots are contained in ak th roots