Does there exist $ 2002$ distinct positive integers $ k_1, k_2, \cdots k_{2002}$ such that for any positive integer $ n \geq 2001$, one of $ k_12^n + 1, k_22^n + 1, \cdots, k_{2002}2^n + 1$ is prime?
Problem
Source: China TST 2002 Quiz
Tags: LaTeX, number theory unsolved, number theory
03.04.2011 16:22
No. I'll prove inductively the following statement: For $n\in \mathbb{N}$ and $k_1,k_2,...,k_n, a\in \mathbb{N}$ there exist arbitrarily large $m\in \mathbb{N}$ such that all numbers $k_ia^m+1$, $i=1,...,n$ are composite. For $n=1$ let $p$ be a prime divisor of $k_1a^t+1$ for some big positive integer $t$. Then $k_1a^{pt}+1\equiv k_1a^t+1\equiv 0 (p)$ and $k_1a^{pt}+1>p$, so it is composite. Now assume, that this is true for $n<l$. Let $p|k_la^t+1$ for some $p$ prime and some positive integer $t$. Then $k_la^{t+r(p-1)}+1\equiv k_la^t+1\equiv 0 (p)$, so $k_la^n+1$ is composite for $n=t+r(p-1)$, $r=1,2,...$. Now it's enough to consider numbers $(k_i*a^t)\cdot (a^{p-1})^r+1$, $i=1,2,...,l-1$ and find $r$ large enough for which they are all composite (inductive hypothesis).
15.01.2013 04:25
I have non-inductive solution. Sorry for not typing in LATEX Remark that k.2^m + 1 = k.2. [2^(m-1) -1] + (2.k +1) For each i = 1,n, we could find an odd prime number p_i divides 2.k_i + 1 ( p_1, p_2,..., p_n are not necessarily pairwise distinct) Let m take the value M. (p_1 -1 ). (p_2 -1). (p_3 -1 )...(p_n -1) + 1 then for each i=1,n we have 2^(p_i - 1) - 1 divides 2^(m-1) - 1. Using Fermat theorem we get 2^(m-1) -1 is divisible by p_i, that yields p_i divides k_i.2^m + 1 So all the number k_i. 2^m + 1 are composite for large enough M
22.08.2021 20:52
shobber wrote: Does there exist $ 2002$ distinct positive integers $ k_1, k_2, \cdots k_{2002}$ such that for any positive integer $ n \geq 2001$, one of $ k_12^n + 1, k_22^n + 1, \cdots, k_{2002}2^n + 1$ is prime?
14.04.2023 01:10
The answer is no. The problem is very easy once you realize $2002$ doesn't matter and you can deal with each $k_i$ separately. Simply pick some prime divisor $p_i \mid 2k_i+1$ for each $k_i$, and set $$n=N(p_1-1)(p_2-1)\cdots(p_{2002} - 1) + 1.$$By Fermat's little theorem this implies that $$k_i \cdot 2^n + 1 \equiv 2k_i + 1 \equiv 0 \pmod p,$$so all of the terms can be composite.
22.08.2024 17:45
Let us denote $p_i $ a prime factor of $2^{2001}k_i+1$. Then consider $n=(p_1-1)\cdots(p_{2002}-1)+2001$. That means $2^nk_i+1 \equiv 2^{2001}k_i+1 \equiv 0 \mod{p_i}$, but $2^nk_i+1>p_i$, so $2^nk_i+1$ is composite. Thus, every element of the sequence is composite.