Prove that $\sigma(am) < \sigma(am + 1)$ for infinitely many positive integers $m$

Question

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).

Answer 1

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 ....?

Answer 2

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$.