Library / Korean Mathematical Olympiad /1 of 6

Korean Mathematical Olympiad

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