Number theoryDifficulty 5.0AIME, harderProve itMongolia
For a positive integer n, let σ(n) be the sum of all divisors of n. Show that there exist infinitely many positive integers n such that n divides 2σ(n)−1.
Solution
Let k be a positive integer. We choose a prime divisor pj of 22j+1 for each 0≤j<k. Then the product nk=p0p1…pk−1 is a divisor of 22k−1=∏j=0k−1(22j+1).
Since nk is odd, σ(nk)=(p0+1)…(pk−1+1) is divisible by 2k. Hence 22k−1 divides 2σ(nk)−1. It follows that 2σ(nk)≡1(modnk).
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.