Given a positive integer $a$, prove that $\sigma(am) < \sigma(am + 1)$ for infinitely many positive integers $m$. (Here $\sigma(n)$ is the sum of all positive divisors of the positive integer number $n$.) Vlad Matei
Problem
Source: Romania TST 3 2010, Problem 3
Tags: modular arithmetic, arithmetic sequence, number theory proposed, number theory
25.08.2012 22:40
Just choose $m$ to be a prime such that $am + 1$ has a lot of prime divisors. To be rigorous, let $p_1,p_2,...,$ be the primes which do not divide $a$. Let $k$ be the minimum integer such that $\frac{2\sigma(a)}{a} < \prod_{i=1}^k \left (1 + \frac{1}{p_i} \right )$. Clearly this $k$ exists as $\prod_{i=1}^\infty \left (1 + \frac{1}{p_i}\right )$ diverges. Now, 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) = \sigma(a) \cdot \sigma(q) = (q+1)\sigma(a)$ $\sigma(aq+1) \ge (aq+1) \cdot \prod_{i=1}^k \left (1 + \frac{1}{p_i}\right ) > \frac{2(aq+1)\sigma(a)}{a} > 2q\sigma(a) > \sigma(aq)$ Thus we are done.
26.08.2012 08:01
How do you know there exists a prime number that is $q$ such that $q \equiv -a^{-1} \bmod{p_i}$ for all $p_i$. Sorry, if this is a bad dumb question?
26.08.2012 13:33
Denote $P=\prod_{k=1}^n p_k$. Just take $q \equiv -a^{-1} \pmod{P}$, so $P \mid aq+1$. If we denote $b \equiv -a^{-1} \pmod{P}$, then this means taking primes $q$ in the arithmetic progression $\{b + nP \mid n\in \mathbb{N}\}$, and we can apply Dirichlet's here.
30.10.2018 21:30
My solution is the same you can even generalize to $\sigma(am)k < \sigma(am + 1)$ with similar method.I was wndering if there exist a solution avoiding Dirichlet's theorem.Can anyone help?(This seems however impossible since we have to control both prime divisors of two consecutive numbers)
31.10.2018 16:45
Here is a solution without Dirichlet. As in dinoboy's solution, let $p_i$ be primes such that $\prod_{i=1}^{k} (1 + \frac{1}{p_i}) > \frac{2 \sigma(a)}{a}$. Our aim is then to solve the congruencs $m \equiv -a^{-1} \pmod {p_i}$ such that $\frac{\sigma(m)}{m}$ is bounded (in fact, we will show we can let it go to $1$). Let $b \equiv a^{-1} \pmod {\prod_{i=1}^{n} p_i}$ and let $c= \prod_{i=1}^{n} p_i$. Then we wish to solve $m \equiv b \pmod c$. Let $r_1,r_2,\ldots,r_k$ be the residues mod $c$ that are attained by primes infinitely often. We claim that these residues can generate $b \pmod c$ as a product. Indeed as $b$ and $c$ are coprime, we can find some $x$ that is $\equiv b \pmod c$ but coprime to all the other primes whose residue mod $c$ are attained finitely often. Then $x$ is a product of primes whose residues mod $c$ are attained infinitely often as wanted. Hence the congruences $m \equiv a^{-1} \pmod {p_i}$ is solvable by $m$ as a product of say $N$ primes and furthermore, we can let these primes be as large as we want (since the residues are attained by primes infinitely often). Since $N$ was fixed, we can let $\frac{\sigma(m)}{m} \to 1$ and also $m$ coprime to $a$ and the rest follows similarly to dinoboy's solution.