Number theoryDifficulty 5.2Prove itUkrainian National Mathematical Olympiad · Ukraine
Find all positive integers n such that nn+1 is divisible by n+1.
This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.
For odd integer n it is enough to decompose: nn+1=(n+1)(nn−1−nn−2+nn−3−⋯+1). Let's assume that there exists an even number n=2k such that K=(2k)2k+1 is divisible by 2k+1. Then 2k+1 is also a divisor of 2kK=(2k)2k+1+2k=((2k)2k+1+1)+(2k−1). Since (2k)2k+1+1=(2k+1)((2k)2k−(2k)2k−1+(2k)2k−2−⋯+1), then 2k−1 must also be divisible by 2k+1. This is impossible and therefore no even number n satisfies the condition.
Source: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.