Given a positive integer $a$, prove that $\sigma(am) < \sigma(am + 1)$ for infinitely many positive integers $m$.

($\sigma(n)$ is the sum of all positive divisors of the positive integer number $n$.)

I have two problem when trying to use the hint.

  1. Let $p_1,p_2,...,$ be the primes which do not divide $a$. Let $k$ be the minimum integer such that $\dfrac{2\sigma(a)}{a} < \prod_{i=1}^k \left (1 + \dfrac{1}{p_i} \right )$. How can I prove $\prod_{i=1}^\infty \left (1 + \dfrac{1}{p_i}\right )$ diverges to show $k$ exist.
  2. By Dirichlet's Theorem there exists infinitely many primes $q$ such that $q \equiv -a^{-1} \pmod{p_i}$ for $1 \le i \le k$. Choose $m=q$, then $\sigma(aq+1) \ge (aq+1) \cdot \prod_{i=1}^k \left (1 + \dfrac{1}{p_i}\right ) > \dfrac{2(aq+1)\sigma(a)}{a} > 2q\sigma(a) > \sigma(aq)$.

The problem is done after that, but how can I prove $q$ exists without using Dirichlet's Theorem (which are too much for a High School Olympiad problem).

  • 1
    $\begingroup$ I've posted an idea - but it's only that and not an answer. $\endgroup$
    – user502266
    Jan 28, 2021 at 22:39

2 Answers 2


This is only an idea for how one might proceed without using Dirichlet

Let $p_1,p_2,...$ be the primes, in numerical order, which do not divide $a$. For some integer $N$, let $s$ be the multiplicative inverse of $p_1p_2... p_N$ modulo $a$, where $ 1\le s<a$. Then there is an integer $m$ such that $$am+1\equiv p_1p_2... p_Ns.$$ Then $m< p_1p_2... p_N$ and is only divisible by primes which either divide $a$ or are $p_i$ for $i>N$.

We have $\sigma(am)<am \prod_{q|a} \frac{q}{q-1}\prod_{p_i|m} \frac{p_i}{p_i-1} $ and $\sigma(am+1)>(am+1)\prod_{i=1}^{N}\frac{p_i+1}{p_i}, $ where $\prod_{p_i|m} {p_i}< p_1p_2... p_N$.

Now $\prod_{q|a} \frac{q}{q-1}$ is fixed. The $p_i$ which divide $m$ are larger and fewer than the $p_i,1\le i \le N$. Let $N$ tend to infinity ....?


First, it is known that $\prod\left(1+\frac{1}{p}\right)$ diverges, see e.g. Wikipedia. Alternatively, if you know that $\sum\frac{1}{p}$ diverges, then you can apply the result of this thread. In any case such a $k$ exists.

We claim that we can find solutions to the system $m\equiv-a^{-1}\pmod{p_i}$ for $1\leq i\leq k$ such that $\sigma(m)/m\to1$, which would clearly solve the problem.

Let $P=\prod_{i=1}^kp_i$, so by CRT we want solutions $m\equiv-a^{-1}\pmod P$. The key idea to avoiding Dirichlet is that we know there are residues $r_1,\dots,r_\ell$ mod $P$ that contain infinitely many primes, and we claim that we can choose $m$ so that its prime factors are all congruent to one of the $r_i\pmod P$. Indeed, by CRT we can find some $m\equiv-a^{-1}\pmod P$ that is coprime with all the primes that are not congruent to one of the $r_i\pmod P$.

Therefore, we can find a solution $m\equiv-a^{-1}\pmod P$ that is the product of $M$ distinct primes, each of which are congruent to some $r_i\pmod P$. Since there are infinitely many primes in each of these congruence classes, we can take the primes as large as we like, so that $\sigma(m)/m$ is arbitrarily close to $1$.

  • $\begingroup$ "Since there are infinitely many primes in each of these congruence classes" I believe this is precisely the point which OP is trying to avoid. $\endgroup$
    – zhoraster
    Jan 29, 2021 at 8:19
  • $\begingroup$ @jlammy, how can I prove $\dfrac{\sigma(m)}{m}\rightarrow 1$, since $m$ does not only has some divisor that goes to infinitely, it still has another divisor which I cant control, and I don't know the number of divisor of $m$ too. $\endgroup$
    – Zootopia
    Jan 29, 2021 at 10:08
  • $\begingroup$ @zhoraster I'm not using Dirichlet, just the fact that there are infinitely many primes -- if every congruence class contained only finitely many primes, then there would only be finitely many primes. $\endgroup$
    – jlammy
    Jan 29, 2021 at 13:56
  • $\begingroup$ @Zootopia I have found a solution $m$ such that it is expressible as $m=q_1\dots q_M$, where $q_1,\dots,q_M$ are distinct primes, each of which lie in some congruence class $r_j\pmod P$. Now just take each of these $q_i$ to be an arbitrarily large prime (in the same congruence class). The point is that your number $m$ will have a fixed number of prime factors $M$, so $\sigma(m)/m$ can be made close to $1$. $\endgroup$
    – jlammy
    Jan 29, 2021 at 13:59
  • $\begingroup$ @jlammy, the negation of "infinitely many primes in each of these congruence classes" is not "finitely many primes in each of these congruence classes" but "finitely many primes in some of these congruence classes". $\endgroup$
    – zhoraster
    Jan 29, 2021 at 14:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .