Library / NMO Selection Tests for the Junior Balkan Mathematical Olympiad /7 of 62

NMO Selection Tests for the Junior Balkan Mathematical Olympiad

Number theory Difficulty 4.7 AIME Prove it Romania

Let $n$ and $k$ be two positive integers such that $1 \le n \le k$ . Prove that, if $d^k + k$ is a prime number for each positive divisor $d$ of $n$ , then $n + k$ is a prime number.

Solution

For $d=1$ it follows that $1+k$ is a prime.

For $d=n$ it follows that $n^k + k$ is a prime. As $k+1$ does not divide $n$ (being larger than $n$ ), from Fermat's Theorem we get $n^k \equiv 1 \pmod{k+1}$ , hence $n^k + k \equiv 0 \pmod{k+1}$ . It follows that $n^k + k = k+1$ , hence $n=1$ . We have seen at the beginning that $1+k$ is a prime.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.