5
$\begingroup$

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

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
8
  • $\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 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 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 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 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 at 14:50

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.