Maths Olympiad Prep

Library / /54 of 97

Number theory Difficulty 8.0 Shortlist Find the answer

Does there exist 2002 2002 distinct positive integers k1,k2,k2002 k_1, k_2, \cdots k_{2002} such that for any positive integer n2001 n \geq 2001, one of k12n\plus1,k22n\plus1,,k20022n\plus1 k_12^n \plus{} 1, k_22^n \plus{} 1, \cdots, k_{2002}2^n \plus{} 1 is prime?

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

Solution

We need to determine whether there exist 2002 2002 distinct positive integers k1,k2,,k2002 k_1, k_2, \ldots, k_{2002} such that for any positive integer n2001 n \geq 2001 , at least one of k12n+1,k22n+1,,k20022n+1 k_1 2^n + 1, k_2 2^n + 1, \ldots, k_{2002} 2^n + 1 is prime.

To address this, we generalize the problem for F>2002 F > 2002 . Consider choosing X=FFi=1FF(pi1) X = F^F \prod_{i=1}^{F^F} (p_i - 1) , where pi p_i are distinct primes. This choice ensures that X X is extremely large.

By Fermat's Little Theorem, for any prime pi p_i dividing kx+1 k_x + 1 , we have:
2Xki+1kx+10(modpi). 2^X k_i + 1 \equiv k_x + 1 \equiv 0 \pmod{p_i}.

Given the size of 2Xki+1 2^X k_i + 1 being greater than pi p_i , it follows that 2Xki+1 2^X k_i + 1 is not prime. Thus, no such integers k1,k2,,k2002 k_1, k_2, \ldots, k_{2002} exist.

Therefore, the answer is: \boxed{\text{No}}.

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