Maths Olympiad Prep

Library / /2 of 8

Number theory Difficulty 5.3 AIME, harder Prove it Romania

Determine the positive integers nn that satisfy the following property: for every positive divisor dd of nn, d+1d + 1 is a divisor of n+1n + 1.

Solution

We prove that the numbers that have the given property are 11 and the odd prime numbers. It is clear that all these numbers do indeed have the desired property and also that 22 does not have it.

Conversely, let us consider a composite number nn and prove that it does not have the given property. If nn is composite, then n=abn = ab such that 1<ab<n1 < a \le b < n. It follows that b+1b + 1 divides n+1n + 1, i.e. there exists cZc \in \mathbb{Z} such that c(b+1)=n+1=ab+1c(b + 1) = n + 1 = ab + 1. We obtain that bb divides c1c - 1. Obviously, c>1c > 1. We deduce that c1bc - 1 \ge b, i.e. cb+1c \ge b + 1. Then ab+1=c(b+1)(b+1)2ab + 1 = c(b + 1) \ge (b + 1)^2, which means that ab+1b2+2b+1ab + 1 \ge b^2 + 2b + 1, leading to ab+2a \ge b + 2, which contradicts aba \le b.

In conclusion, no composite number does satisfy the requirements.

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.