Maths Olympiad Prep

Library / /15 of 152

Number theory Difficulty 5.2 AIME, harder Prove it Russia

A positive integer nn is good if every its positive divisor increased by 11 is a divisor of n+1n+1. Find all good positive integers.

Solution

11 and all odd prime numbers.

Clearly, n=1n = 1 satisfies the condition. All odd primes also satisfy it: if n=pn = p, then its divisors, increased by 11, are 22 and p+1p+1; both divide p+1p+1.

On the other hand, any number nn satisfying the condition has 11 as a divisor; thus, n+1n+1 is divisible by 1+11+1, i.e., nn is odd.

Suppose now that some composite nn satisfies the condition. We have n=abn = ab, where ab2a \geq b \geq 2. Then n+1n+1 is divisible by a+1a+1; moreover, n+b=(a+1)bn+b = (a+1)b is also divisible by a+1a+1. Therefore, b1=(n+b)(n+1)b-1 = (n+b)-(n+1) is also divisible by a+1a+1. Since b1>0b-1 > 0, we get b1a+1b-1 \geq a+1. But this contradicts the inequality bab \leq a.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.