Competition problem — Number theory

Number theory Difficulty 5.4 AIME, harder Prove it South Korea

For a positive integer $a$ , let $S_a$ be the set of primes satisfying the following condition:
(condition) For any $p \in S_a$ , there exists an odd integer $b$ such that $(2^{2^a})^b - 1$ is divisible by $p$ .
For any positive integer $a$ , prove that there exist infinitely many primes that are not contained in $S_a$ .

Solution

For any positive integer $n$ , define $a_n := 2^{2^n} + 1$ . Since
$a_1 a_2 \cdots a_{n-1} = a_n - 2,$
$\gcd(a_n, a_m) = 1$ for any $n \neq m$ . Now, for any positive integer $n$ such that $n \ge a$ , let $p_n$ be any prime dividing $a_n$ . Note that $p_n$ is different from $p_m$ for any $m \ne n$ .

Suppose that $2^{2^n}b - 1$ is divisible by $p_n$ for some odd integer $b$ . Since
$2^{2^{2n}} \equiv 1 \pmod{p_n}, \quad 2^{2^{2n+1}} \equiv 1 \pmod{p_n},$
$2^{2^n} \equiv 1 \pmod{p_n}$ . This is a contradiction to the fact that $2^{2^n} \equiv -1 \pmod{p_n}$ . Therefore, $p_n \notin S_a$ for any integer $n$ such that $n \ge a$ . $\square$

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.