Maths Olympiad Prep

Library / /5 of 18

Number theory Difficulty 7.8 National olympiad, round 2 Prove it Romania

Given a positive integer aa, prove that σ(am)<σ(am+1)\sigma(am) < \sigma(am + 1) for infinitely many positive integers mm. (Here σ(n)\sigma(n) is the sum of all positive divisors of the positive integer number nn.)
Vlad Matei

Solution

Given an integer N>aN > a, we claim that there exist an integer dd and a prime pp, both greater than NN, such that dd divides ap+1ap+1, dd and (ap+1)/d(ap+1)/d are coprime, and σ(d)/d>σ(a)\sigma(d)/d > \sigma(a). In this case,
σ(ap+1)=σ(ap+1dd)=σ(ap+1d)σ(d)>ap+1dσ(d)>(p+1)σ(a)=σ(p)σ(a)=σ(ap), \sigma(ap + 1) = \sigma\left(\frac{ap+1}{d} \cdot d\right) = \sigma\left(\frac{ap+1}{d}\right) \sigma(d) > \frac{ap+1}{d} \cdot \sigma(d) \\ > (p+1)\sigma(a) = \sigma(p)\sigma(a) = \sigma(ap),
and we are done. Back to the claim, let pip_i be the ii-th prime greater than NN, take kk large enough so that i=1k1/pi>σ(a)\sum_{i=1}^k 1/p_i > \sigma(a) – this is possible, for q prime1/q=\sum_{q \text{ prime}} 1/q = \infty – and set d=p1p2pkd = p_1p_2\cdots p_k. Then
σ(d)/d=i=1k(1+1pi)>1+i=1k1pi>σ(a). \sigma(d)/d = \prod_{i=1}^{k} \left(1 + \frac{1}{p_i}\right) > 1 + \sum_{i=1}^{k} \frac{1}{p_i} > \sigma(a).
Next, use the Chinese remainder theorem to produce an integer tt, which is unique modulo p12p2pk2p_1^2 p_2 \cdots p_k^2, such that at+1pi(modpi2)at + 1 \equiv p_i \pmod{p_i^2}, i=1,2,,ki = 1, 2, \dots, k; this is possible, for each pi>N>ap_i > N > a. Finally, use Dirichlet's theorem to pick up a prime p>Np > N from the arithmetic sequence
t+rp12p22pk2,r=0,1,2, t + rp_1^2 p_2^2 \cdots p_k^2, \quad r = 0, 1, 2, \dots
Clearly, such a pp satisfies the stated conditions.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.