Maths Olympiad Prep

Library / /2 of 12

Number theory Difficulty 5.0 AIME, harder Prove it Mongolia

For a positive integer nn, let σ(n)\sigma(n) be the sum of all divisors of nn. Show that there exist infinitely many positive integers nn such that nn divides 2σ(n)12^{\sigma(n)}-1.

Solution

Let kk be a positive integer. We choose a prime divisor pjp_j of 22j+12^{2^j} + 1 for each 0j<k0 \le j < k. Then the product nk=p0p1pk1n_k = p_0p_1\dots p_{k-1} is a divisor of 22k1=j=0k1(22j+1)2^{2^k} - 1 = \prod_{j=0}^{k-1}(2^{2^j} + 1).

Since nkn_k is odd, σ(nk)=(p0+1)(pk1+1)\sigma(n_k) = (p_0+1)\dots(p_{k-1}+1) is divisible by 2k2^k. Hence 22k12^{2^k}-1 divides 2σ(nk)12^{\sigma(n_k)}-1. It follows that 2σ(nk)1(modnk)2^{\sigma(n_k)} \equiv 1 \pmod{n_k}.

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.