For a positive integer $N$, let $f(N)$ be the number of ordered pairs of positive integers $(a,b)$ such that the number $$\frac{ab}{a+b}$$is a divisor of $N$. Prove that $f(N)$ is always a perfect square.
Problem
Source: 2019 Baltic Way P16
Tags: number theory
MarkBcc168
18.11.2019 14:03
By Simon's Favorite Factoring Trick, the number of solutions of $\tfrac{ab}{a+b}=d$ $\iff (a-d)(b-d)=d^2$ is equal to $\tau(d^2)$ where $\tau$ is the number-of-divisor function. Thus
$$f(n) = \sum_{d\mid n}\tau(d^2).$$Thus $f$ is multiplicative therefore it suffices to check the result for prime power $n$. Let $n=p^t$. Then
$$f(n) = \tau(1) + \tau(p^2) + \tau(p^4) + \hdots + \tau(p^{2t}) = 1+3+5+\hdots+(2t+1) = (t+1)^2$$hence the result follows. In fact, the above gives $f(n) = \tau(n)^2$.
Loppukilpailija
22.12.2019 18:10
Instead of using SFFT as in the above solution, another natural idea is to directly look at the divisibility condition $\frac{ab}{a+b} \mid N$. This solution, however, is more difficult than the one above.
Let $a$ and $b$ be integers such that $\frac{ab}{a+b}$ is an integer dividing $N$. Let $d = \gcd(a, b)$, and write $a = dx$ and $b = dy$. We thus have $\frac{dxy}{x+y} \mid N$. Since $x$ and $y$ are coprime, $\gcd(xy, x+y) = 1$, and thus $x+y \mid d$. Write $d = k(x+y)$. Our condition turns into
\begin{align*}
kxy \mid N.
\end{align*}Therefore, our problem may be stated as follows: for an integer $N$, let $f(N)$ be the number of triplets $(k, x, y)$ of integers such that $kxy \mid N$ with $x$ and $y$ coprime. Prove that $f(N)$ is a square. (It is easy to see that no two triplets $(k, x, y)$ lead to the same solution $(a, b)$ of the original problem.)
Let $g$ be a divisor of $N$, and inspect those triplets $(k, x, y)$ satisfying $xy = g$. Now there are $d(N/g)$ choices for $k$, where $d(n)$ denotes the number of divisors of $n$. Furthermore, there are $2^{\omega(g)}$ choices for $(x, y)$, where $\omega(g)$ denotes the number of distinct prime divisors of $g$. (Look at the relation $xy = g$ one prime power at a time to see this.)
Thus,
\begin{align*}
f(N) = \sum_{g \mid N} 2^{\omega(g)}d(N/g).
\end{align*}Note that both $n \to d(n)$ and $d \to 2^{\omega(d)}$ are multiplicative functions, so $f(N)$ is the Dirichlet convolution of two multiplicative functions and thus multiplicative. Furthermore, an easy calculation gives $f(p^t) = (t+1)^2$ for a prime $p$. This proves $f(N)$ is always a square.
mashina
22.12.2019 21:24
Nice problem! Dirichlet convolution immediately kills it