Competition problem — Number theory

Library / /2 of 19

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,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.