Maths Olympiad Prep

Library / /169 of 520

Number theory Difficulty 5.8 AIME, harder Find the answer

Find all primes of the form nn+1n^{n}+1 that do not exceed 101910^{19}, where nn is a positive integer.

A number or a short expression. Spacing and $ signs are ignored.

Solution

7. When n=1n=1, nn+1=2n^{n}+1=2 satisfies the condition. When n>1n>1, let n=2kqn=2^{k} q, where qq is an odd number. If q>1q>1, as shown in the previous problem, nn+1n^{n}+1 is not a prime number, so n=2kn=2^{k}, where kk is a positive integer. At this point,
nn+1=2k2k+1=(22k)k+1n^{n}+1=2^{k \cdot 2^{k}}+1=\left(2^{2^{k}}\right)^{k}+1

Further analysis shows that there exists a non-negative integer mm such that k=2mk=2^{m}, hence
nn+1=222m+m+1n^{n}+1=2^{2^{2^{m}+m}}+1

When m2m \geqslant 2, 2m+m62^{m}+m \geqslant 6, so 22m+m262^{2^{m}+m} \geqslant 2^{6}, thus
nn+1226+1=264+1=16×(1024)6+1>16×(103)6+1>1019\begin{aligned} n^{n}+1 & \geqslant 2^{2^{6}}+1=2^{64}+1 \\ & =16 \times(1024)^{6}+1 \\ & >16 \times\left(10^{3}\right)^{6}+1 \\ & >10^{19} \end{aligned}

Therefore, by nn+11019n^{n}+1 \leqslant 10^{19}, we know m1m \leqslant 1. By setting m=0,1m=0,1, we find nn+1=5,257n^{n}+1=5,257, both of which are prime numbers.

In summary, the required prime numbers are 2, 5, and 257.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.