Sum of unit fractions problem; conjecture about bijection between solutions to $\frac{1}{N}=\frac{1}{p}+\frac{1}{q}$ and divisors of $N^2$

Question

I read this problem in a newspaper last week:

Given a positive integer $N$, how many pairs of positive integers $(p,q)$ with $p\leq q$ exist such that $\frac{1}{N}=\frac{1}{p}+\frac{1}{q}$?

(... paraphrased from the original question, posed by Chris Maslanka in the Guardian).

I came to a solution to this problem fairly quickly (subsequently finding the relevant sequence A018892 on the OEIS). But I've noticed something else about it...

Define the sets:

\begin{align*} S(N) &=\left\{ (p,q):p\leq q, \frac{1}{N}=\frac{1}{p}+\frac{1}{q} \right\}\\ D(N) &=\left\{d:d\mid N^2, d\leq N \right\} \end{align*}

Also the function:

\begin{align*} f_N\colon S(N) & \longrightarrow \mathbb{Z}\\ (p,q) & \longmapsto p-N \end{align*}

I believe that $f_N$ is a bijection from $S(N)$ to $D(N)$.

For example: \begin{align*} S(6)&=\big\{(7,42),\,(8,24), \,(9,18), \,(10,15), \,(12,12)\big\}\\ f_6(S(6))&=\{1,2,3,4,6\}=D(6) \end{align*}

I have verified it up to $N=20$. It is fairly straightforward when $N$ is prime (when $S(N)$ contains just two elements). I have played around trying to prove it for any $N$, but can't quite get there. Might somebody be able to help?

Answer 1

Multiply both sides by $Npq$ gives $$pq=Np+Nq$$ $$pq-Np-Nq=0$$ $$pq-Np-Nq+N^2=N^2$$ $$(p-N)(q-N)=N^2$$. Hence, for any factor pair of $N^2$, $(d,\frac{N^2}{d})$, there exists an integer solution to $(p,q)=(d+N,\frac{N^2}{d}+N)$. However, this is not necessarily a positive integral solution that satisfies $p\leq q$.

For $p\leq q$, we require that $1\leq d\leq N$ or $-N^2\leq d\leq -N$.

However, in the case of the latter when $-N^2\leq d\leq -N$, we have $-N^2+N\leq p\leq 0$. Clearly this will not yield a positive solution for $p$. Hence, only when $1\leq d\leq N$ do we get a valid solution for $(p,q)$ that meets all the desired conditions. Hence your claim of the function being a bijection is true.

Answer 2

Suppose $\frac{1}{N} = \frac{1}{p} + \frac{1}{q}$ holds, with $p \leq q$. Then $p > N$, then set $p = N + k$, $k > 0$.

Writing $\frac{1}{N} = \frac{1}{N+k} + \frac{1}{q}$, it is clear for an integer $q$ to exist, that $\frac{1}{q} = \frac{1}{N} - \frac{1}{N+k} = \frac{k}{N(N+k)}$, in other words, $\gcd(k, N(N+k)) = k$

This clearly implies that $k | (N^2 + kN) $ which implies that if $k|N^2$, $k$ is a valid solution to the problem. Therefore given the set $\{d : d | N^2, d \leq N\}$, these values of $d$ will generate solutions to the problem with $p = N + d$

The constraint $d \leq N$ in the set insures the condition $p \leq q$, so you do indeed have a bijection.