NMO Selection Tests for the Balkan and International Mathematical Olympiads

Given an integer $N>a$, we claim that there exist an integer $d$ and a prime $p$, both greater than $N$, such that $d$ divides $ap+1$, $d$ and $(ap+1)/d$ are coprime, and $\sigma (d)/d>\sigma (a)$. In this case, $$\begin{gathered} \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), \end{gathered}$$ and we are done. Back to the claim, let $p_i$ be the $i$-th prime greater than $N$, take $k$ large enough so that ${\sum }_{i=1}^{k}1/p_i>\sigma (a)$ – this is possible, for ${\sum }_{q\text{ prime}}1/q=\infty$ – and set $d=p_1{p}_2\cdots p_k$. Then $$\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 $t$, which is unique modulo $p_1^2{p}_2\cdots p_k^2$, such that $at+1\equiv p_i(\mathrm{mod}{p}_i^2)$, $i=1,2,\dots ,k$; this is possible, for each $p_i>N>a$. Finally, use Dirichlet's theorem to pick up a prime $p>N$ from the arithmetic sequence $$t+r{p}_1^2{p}_2^2\cdots p_k^2,r=0,1,2,\dots$$ Clearly, such a $p$ satisfies the stated conditions.