# Verify Elementary Number Theory Proof (Romanian Olympiad)

Can you check that there are no errors in this proof I wrote?

Here's the problem (from the 2002 Romanian Olympiad):

Let $p, q$ be two distinct primes. Prove that there are positive integers $a, b$ so that the arithmetic mean of all the divisors of the number $n = p^a q^b$ is also an integer.

Here's my attempt:

Since $p$ and $q$ are distinct, either $p \neq 2$ or $q \neq 2$. Assume WLOG that $q \neq 2$.

Choose $$a = (q+1)/2 - 1$$ $$b=1.$$

Note that $a$ is a positive integer because $q$ is odd and $q \geq 3$.

It now follows that $p^a q^b = p^a q$ and has divisors $$p^0, p^1, \dots, p^a,$$ $$p^0 q, p^1 q, \dots, p^a q.$$

There are $2(a+1)$ of them, so their arithmetic mean is $$\frac{1}{2(a+1)}\left[ \left( p^0 + p^1 + \dots + p^a \right) + \left( p^0 q + p^1 q + \dots + p^a q \right) \right]\\ = \frac{1}{2\left(\frac{q+1}{2}\right)}\left[ \left( p^0 + p^1 + \dots + p^a \right) + q \left( p^0 + p^1 + \dots + p^a \right) \right]\\ = \frac{1}{q+1}\left[ (q+1) \left( p^0 + p^1 + \dots + p^a \right) \right]\\ = p^0 + p^1 + \dots + p^a.$$

This is an integer as desired.

• Looks good, nice proof! – A. Pongrácz Sep 5 '18 at 18:51
• It's perfect. BTW if $p,q$ are both odd you can also let $a=b=1.$ – DanielWainfleet Sep 6 '18 at 2:06

Your proof is fine, but the magic values of $a$ and $b$ bother me. So, I'm going to try to find all solutions.

Spoiler: I don't, but do give some conditions.

The sum of the divisors of $p^aq^b$ is $\sigma(p^aq^b) =\dfrac{(p^{a+1}-1)(q^{b+1}-1)}{(p-1)(q-1)}$ and the number of divisors is $d(p^aq^b) =(a+1)(b+1)$. So the average is $r(p^aq^b) =\dfrac{\sigma(p^aq^b)}{d(p^aq^b)} =\dfrac{(p^{a+1}-1)(q^{b+1}-1)}{(p-1)(q-1)(a+1)(b+1)}$.

In your case, this is $a=(q-1)/2, b=1$, so $a+1 = (q+1)/2$ and

$\begin{array}\\ r(p^aq^b) &=\dfrac{(p^{a+1}-1)(q^{b+1}-1)}{(p-1)(q-1)(a+1)(b+1)}\\ &=\dfrac{(p^{(q+1)/2}-1)(q^{2}-1)}{(p-1)(q-1)((q+1)/2))2}\\ &=\dfrac{(p^{(q+1)/2}-1)(q^{2}-1)}{(p-1)(q-1)(q+1)}\\ &=\dfrac{(p^{(q+1)/2}-1)}{(p-1)}\\ \end{array}$

and this is an integer.

If $b=1$,

$\begin{array}\\ r(p^aq^b) &=\dfrac{(p^{a+1}-1)(q^{b+1}-1)}{(p-1)(q-1)(a+1)(b+1)}\\ &=\dfrac{(p^{a+1}-1)(q^{2}-1)}{(p-1)(q-1)(a+1)2}\\ &=\dfrac{(p^{a+1}-1)(q+1)}{2(a+1)(p-1)}\\ \end{array}$

For this to be an integer it is sufficient that $2(a+1) | (q+1)$, so $2(a+1) = q+1$ works if $q$ is odd. In general, if $q+1 = 2m(a+1)$, $a = \dfrac{q+1}{2m}-1$. If $q = 2^uv-1$ where $u \ge 1$ and $v$ is odd, then $a = \dfrac{2^uv}{2m}-1 = \dfrac{2^{u-1}v}{m}-1$. In particular, choosing $m=v$ gives $a = 2^{u-1}-1$ and $m = 1$ gives OP's solution.

Another possibility is having $a+1 = 2m$ so that $\dfrac{(p^{a+1}-1)(q+1)}{2(a+1)(p-1)} =\dfrac{(p^{2m}-1)(q+1)}{2(a+1)(p-1)} =\dfrac{(p^{m}-1)(p^{m}+1)(q+1)}{4m(p-1)}$ so that $4m | (p^m+1)$ would work. For $m=1$, this requires that $p \equiv 3 \bmod 4$; for $m=2$, this requires that $p^2 \equiv 7 \bmod 8$ which can't happen since $p^2 \equiv 1 \bmod 8$.

If $a+1=2m$ and $b+1 = 2n$ then

$\begin{array}\\ r(p^aq^b) &=\dfrac{(p^{a+1}-1)(q^{b+1}-1)}{(p-1)(q-1)(a+1)(b+1)}\\ &=\dfrac{(p^{2m}-1)(q^{2n}-1)}{(p-1)(q-1)4mn}\\ &=\dfrac{(p^{m}-1)(q^{n}-1)(p^{m}+1)(q^{n}+1)}{(p-1)(q-1)4mn}\\ \end{array}$

so it is enough if $4mn | (p^{m}+1)(q^{n}+1)$.

At this point, I don't see any easy solutions, so I'll stop here.

• The magic values of $a$ and $b$ bothered me as well. Thank you!! – 伽罗瓦 Sep 5 '18 at 21:10