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.

  • 2
    $\begingroup$ Looks good, nice proof! $\endgroup$ Sep 5, 2018 at 18:51
  • $\begingroup$ It's perfect. BTW if $p,q$ are both odd you can also let $a=b=1.$ $\endgroup$ Sep 6, 2018 at 2:06

1 Answer 1


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.

  • 1
    $\begingroup$ The magic values of $a$ and $b$ bothered me as well. Thank you!! $\endgroup$
    – green frog
    Sep 5, 2018 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.