Prove that there exists infinetly many natural number $n$ such that at least one of the numbers $2^{2^n}+1$ and $2018^{2^n}+1$ is not a prime.
Problem
Source: Serbia TST 2018 P1
Tags: number theory
26.05.2018 16:40
The same spirit from this should work?
08.09.2018 18:00
Assume that $\exists \ M \in \mathbb{N}$ such that both $P_n=2^{2^n}+1$ and $Q_n=2018^{2^n}+1$ are primes for all $n \ge M$. Consider a prime $P_k=2^{2^k}+1$ such that $P_k > 2018^{2^M}-1=Q_M$. Clearly $P_k \nmid Q_x, \ \forall \ x$ and $P_k \mid 2018^{P_k-1}-1$. Note that $P_k \mid 2018^{P_k-1}-1$ and $P_k \nmid Q_{2^k-1}=2018^{\frac{P_k-1}{2}}+1 \implies P_k \mid 2018^{\frac{P_k-1}{2}}-1$. But $P_k \nmid Q_{2^k-2}=2018^{\frac{P_k-1}{4}}+1$, then analogously $P_k \mid 2018^{\frac{P_k-1}{4}}-1$. With the same idea applied $2^{2^k}-M$ times, we obtain $P_k \mid 2018^{\frac{P_k-1}{2^{2^k-M}}}-1 = 2018^{2^M}-1$, but $P_k > 2018^{2^M}-1$, a contradiction.
30.12.2019 23:46
Assume to the contrary. Suppose $M \in \mathbb{N}$ such that for all $n \ge M$, we have both of these numbers as primes. Fix a large $n$, and let $p=2^{2^n}+1$. Let $d=\text{ord}_p(2018)$. Then $d \mid p-1$ so $d=2^j$ for some $j \ge 2$. So, $p \nmid 2018^{2^{j-1}}-1$ hence $p \mid 2018^{2^{j-1}+1}$. So, $2018^{2^{j-1}}+1$ is not a prime (it cannot be equal to $p$ as $1009$ is a factor of $2018$), forcing $j \le M+1$. By choosing $n$ large, we get a contradiction.
11.04.2021 01:07
I think this solution is correct: Suppose otherwise, so for all $n\geq n_{0}$ we have that both of $p_{n}=2^{2^n}+1$ and $q_{n}=2018^{2^n}+1$ are primes. Let $m$ be some number larger or equal than $n_{0}$ and let $M\geq 2^m\geq n_{0}$ and both of $p_{m}=2^{2^m}+1$ and $q_{M}=2018^{2^M}+1$ are primes. Since $p_{m}-1=2^{2^m}\mid 2^M$ we have by Fermat's Little Theorem that $q_{M}\equiv 2$ $(mod$ $p_{m})$ so $p_{m}\mid 2018^{2^M}-1$ $=2017q_{0}\cdots q_{M-1}$ but since all $q_{i}$ for $i\geq n_{0}$ are prime and can't be equal to $p_{m}$ therefore $p_{m}\mid 2017 q_{0}\cdots q_{n_{0}-1}$ but obviously $p_{m}$ can be arbitrarily large and right side is fixed, we have a desired contradiction.
22.10.2024 16:49
Say for every $n \geq M$ we have both $2^{2^n} + 1$ and $2018^{2^n} + 1$ is a prime. Then we let for large $m$, $p_m = 2^{2^m} + 1$ and $q_m = 2018^{2^m} + 1$ where both are primes. Then, we know that $2018^{p_m - 1} \equiv 1 \pmod {p_m}.$ Therefore if we let $ord{p_m}(2018) = l$ then $l$ is a power of 2. Hence, we let $l = 2^k$ then we know that $2018^{2^{k-1}} \equiv -1 \pmod {p_m}.$ Therefore, $2018^{2^{k-1}} + 1$ is not a prime, but taking a large $m$ contradicts it.