$n$ is a positive integer, $F_n=2^{2^{n}}+1$. Prove that for $n \geq 3$, there exists a prime factor of $F_n$ which is larger than $2^{n+2}(n+1)$.
Problem
Source: China TST 2005
Tags: modular arithmetic, logarithms, number theory unsolved, number theory
ehsan2004
30.06.2006 10:41
I think it will help: all of the divisor$>1$ of $2^{2^n}+1$ are in the form $2^{n+2}k+1$ where $k\in \mathbb{N}$
mahanmath
10.06.2010 18:51
KDS wrote: ehsan2004 wrote: I think it will help: all of the divisor$>1$ of $2^{2^n}+1$ are in the form $2^{n+2}k+1$ where $k\in \mathbb{N}$ I know this , but anyone give more detailed solution please? It`s really hard ! It was ChinaTST . Hint : Assume $F_n = \prod_{i=1}^{m} {p_i}^{\alpha _i}$ , Find an upper and a lower bound for $\sum_{i=1}^{m} \alpha _i$.
Zhero
07.01.2011 03:04
For $n \geq 4$, the largest prime factor is larger than $2^{n+4} (n+2)$.
Lemma: If $n \geq 2$, $p$ is a prime, and $p | 2^{2^n} + 1$, then $2^{n+2} | p - 1$.
Proof: Let $k$ be the order of 2 modulo $p$. Since $2^{2^n} \equiv -1 \pmod{p}$, $2^{2^{n+1}} \equiv 1 \pmod{p}$, so $k$ must be a power of 2 less than or equal to $2^{n+1}$. But if $k < 2^{n+1}$, we may square the congreunce $2^k \equiv 1 \pmod{p}$ a total of $n - \log_2 k$ times to get $2^{2^n} \equiv 1 \pmod{p}$. But $2^{2^n} \equiv -1 \pmod{p}$ and $p \neq 2$, so we must have $k = 2^{n+1}$. Because $n \geq 3$, $8 \, | \, 2^{n+1} \, | \, p - 1$, whence $\left( \frac{2}{p} \right) = 1$. Hence, $a^2 \equiv 2 \pmod{p}$ for some integer $a$. The order of $a$ must therefore be $2k$, so $2^{n+2} = 2k \, | \, p - 1$, as desired.
The problem is clearly true when $n = 3$, so we may suppose that $n \geq 4$. Let $p_1 \leq p_2 \leq \ldots \leq p_m$ be primes such that $2^{2^n} + 1 = p_1 p_2 \ldots p_m$. By the lemma, there exist integers $a_1, a_2, \ldots, a_m$ such that $p_i = 2^{n+2} a_i + 1$ for each $i$. Hence, we have
\begin{align*} 2^{2^n} + 1 = (2^{n+2} a_1 + 1)(2^{n+2} a_2 + 1) \ldots (2^{n+2} a_m + 1) . \tag{1} \end{align*}
It follows that $2^{2^n} \geq (2^{n+2} + 1)^m > 2^{m(n+2)}$, whence
\[ m < \frac{2^n}{n+2}. \]
Since $n \geq 4$, $2n + 4 \leq 2^n$. Taking (1) modulo $2^{2n+4}$ yields
\begin{align*}
1
&\equiv 2^{2^n} + 1 \\
&= (2^{n+2} a_1 + 1)(2^{n+2} a_2 + 1) \ldots (2^{n+2} a_m + 1) \\
&= 2^{2n+4}(\mbox{some terms}) + 2^{n+2}(a_1 + a_2 + \ldots + a_m) + 1 \\
&\equiv 2^{n+2}(a_1 + a_2 + \ldots + a_m) + 1 \pmod{2^{2n+4}},
\end{align*}
whence
\[ 2^{n+2} | a_1 + a_2 + \ldots + a_m. \]
Since $a_m \geq a_{m-1} \geq \ldots \geq a_1$, we have $a_m \geq \frac{2^{n+2}}{m}$. Hence,
\begin{align*}
p_m
&= 2^{n+2} a_m + 1 \\
&\geq 2^{n+2} \cdot \frac{2^{n+2}}{m} + 1 \\
&> 2^{n+2} \cdot \frac{2^{n+2}}{\frac{2^n}{n+2}} \\
&= 2^{n+4} (n+2),
\end{align*}
as desired.
chuyentoan wrote: It is really false!all of the divisor$>1$ of $2^{2^n}+1$ are in the form $2^{n+1}k+1$ but not $2^{n+2}$ where $k\in \mathbb{N}$ No, it is true; see my my first lemma.
lfetahu
23.06.2014 01:11
Let 2^(2^n) = m^2. Now, try to find the smallest k, such that p is a prime divisor of m^2 + 1, and p > 2m + sqrt(2m), for every m >= k. (This problem is similar to IMO 2008 - Problem 3.)
rkm0959
24.07.2015 11:00
It is well-known that all prime divisor of $F_n$ are $1 \pmod {2^{n+1}}$. Let the prime divisors of $F_n$ be $2^{n+1}p_1+1, 2^{n+1}p_2+1 \cdots, 2^{n+1}p_t+1$. We have $2^{2^n}+1 = \prod_{i=1}^t (2^{n+1}p_i+1)^{e_i} \equiv \prod_{i=1}^t (2^{n+1}p_ie_i+1) \equiv 1 \pmod {2^{2n+2}}$ Therefore, we have that $\sum_{i=1}^t p_ie_i \equiv 0 \pmod {2^{n+1}} \implies \sum_{i=1}^t p_ie_i \ge 2^{n+1}$ Let $max[p_i]=p$. We have $p>\frac{2^{n+1}}{\sum_{i=1}^t e_i}$. It suffices to show that $\frac{2^{n+1}}{\sum_{i=1}^t e_i} \ge 2(n+1)$ This follows from $2^{2^n}+1 = \prod_{i=1}^t (2^{n+1}p_i+1)^{e_i} \ge \prod_{i=1}^t (2^{n+1}p_i)^{e_i} +1 \ge 2^{(n+1)\sum_{i=1}^t e_i}+1$. $\blacksquare$
62861
30.08.2019 11:31
The case $n = 3$ is clear, so assume $n \ge 4$. It is well-known that every prime factor of $F_n$ is congruent to 1 modulo $2^{n+2}$. Assuming the conclusion is false, write \[2^{2^n} + 1 = (1 \cdot 2^{n+2} + 1)^{e_1} \cdots ((n+1) \cdot 2^{n+2} + 1)^{e_{n+1}}\]and take modulo $2^{2n+4}$: after simplifying we obtain \[e_1 + 2e_2 + \dots + (n+1) e_{n+1} \equiv 0 \pmod{2^{n+2}}.\]In particular, $e_1 + \dots + e_{n+1} \ge \tfrac{1}{n+1} \cdot 2^{n+2}$, so \begin{align*} 2^{2^n} + 1 & = (1 \cdot 2^{n+2} + 1)^{e_1} \cdots ((n+1) \cdot 2^{n+2} + 1)^{e_{n+1}}\\ & \ge (2^{n+2} + 1)^{e_1 + \dots + e_{n+1}}\\ & \ge (2^{n+2} + 1)^{2^{n+2}/(n+1)}\\ & > 2^{2^{n+2}(n+2)/(n+1)}\\ & > 2^{2^{n+1}} > 2^{2^n} + 1, \end{align*}contradiction.
Ali3085
28.02.2020 19:47
here's a very different solution claim(1): Let P a prime number and $p=k.2^{n+1} +1$ such that $k <2n$ then there's $m <2^n$ such that $p | 2^m +1$ proof: suppose the contrary $2^{p-1} \equiv $ $1$ $mod p$ $2^{2^{n+1}.k} \equiv $ $1$ $mod p$ $2^{2^{n}.k} \equiv $ $1$ $mod p$ ......... $2^{k} \equiv $ $1$ $mod k.2^{n+1} +1$ but $2^k <2p \implies 2^k=p+1= k.2^{n+1} +2$ a contradiction (there's a typo in this proof ) let $p | 2^{2^n} + 1 \implies p | 2^{2^{n+1}} - 1 \implies ord_p(2)=2^{n+1} \implies 2^{n+1}|p-1$ thus $p=2^{n+1}.k+1$ now by zsigmondi we have a prime divisor $q$ for $2^{2^n} + 1$ that doesn't divide any $2^m +1 : m<2^n$ from the claim above we have $q \ge 2^{n+1}.(2n)+1=2^{n+n}.n+1$ and we are done
Ereb15
28.02.2020 19:59
Can you use Zsigmondi at school olympiads?
Ali3085
28.02.2020 20:03
Ereb15 wrote: Can you use Zsigmondi at school olympiads? why not ?
Dennis1208
20.11.2022 10:50
Zhero wrote:
For $n \geq 4$, the largest prime factor is larger than $2^{n+4} (n+2)$.
Lemma: If $n \geq 2$, $p$ is a prime, and $p | 2^{2^n} + 1$, then $2^{n+2} | p - 1$.
Proof: Let $k$ be the order of 2 modulo $p$. Since $2^{2^n} \equiv -1 \pmod{p}$, $2^{2^{n+1}} \equiv 1 \pmod{p}$, so $k$ must be a power of 2 less than or equal to $2^{n+1}$. But if $k < 2^{n+1}$, we may square the congreunce $2^k \equiv 1 \pmod{p}$ a total of $n - \log_2 k$ times to get $2^{2^n} \equiv 1 \pmod{p}$. But $2^{2^n} \equiv -1 \pmod{p}$ and $p \neq 2$, so we must have $k = 2^{n+1}$. Because $n \geq 3$, $8 \, | \, 2^{n+1} \, | \, p - 1$, whence $\left( \frac{2}{p} \right) = 1$. Hence, $a^2 \equiv 2 \pmod{p}$ for some integer $a$. The order of $a$ must therefore be $2k$, so $2^{n+2} = 2k \, | \, p - 1$, as desired.
The problem is clearly true when $n = 3$, so we may suppose that $n \geq 4$. Let $p_1 \leq p_2 \leq \ldots \leq p_m$ be primes such that $2^{2^n} + 1 = p_1 p_2 \ldots p_m$. By the lemma, there exist integers $a_1, a_2, \ldots, a_m$ such that $p_i = 2^{n+2} a_i + 1$ for each $i$. Hence, we have
\begin{align*} 2^{2^n} + 1 = (2^{n+2} a_1 + 1)(2^{n+2} a_2 + 1) \ldots (2^{n+2} a_m + 1) . \tag{1} \end{align*}It follows that $2^{2^n} \geq (2^{n+2} + 1)^m > 2^{m(n+2)}$, whence
\[ m < \frac{2^n}{n+2}. \]
Since $n \geq 4$, $2n + 4 \leq 2^n$. Taking (1) modulo $2^{2n+4}$ yields
\begin{align*}
1
&\equiv 2^{2^n} + 1 \\
&= (2^{n+2} a_1 + 1)(2^{n+2} a_2 + 1) \ldots (2^{n+2} a_m + 1) \\
&= 2^{2n+4}(\mbox{some terms}) + 2^{n+2}(a_1 + a_2 + \ldots + a_m) + 1 \\
&\equiv 2^{n+2}(a_1 + a_2 + \ldots + a_m) + 1 \pmod{2^{2n+4}},
\end{align*}whence
\[ 2^{n+2} | a_1 + a_2 + \ldots + a_m. \]Since $a_m \geq a_{m-1} \geq \ldots \geq a_1$, we have $a_m \geq \frac{2^{n+2}}{m}$. Hence,
\begin{align*}
p_m
&= 2^{n+2} a_m + 1 \\
&\geq 2^{n+2} \cdot \frac{2^{n+2}}{m} + 1 \\
&> 2^{n+2} \cdot \frac{2^{n+2}}{\frac{2^n}{n+2}} \\
&= 2^{n+4} (n+2),
\end{align*}as desired.
chuyentoan wrote: It is really false!all of the divisor$>1$ of $2^{2^n}+1$ are in the form $2^{n+1}k+1$ but not $2^{n+2}$ where $k\in \mathbb{N}$ No, it is true; see my my first lemma. How to prove that there exists such $p_1 \leq p_2 \leq \ldots \leq p_m$? I don't understand what you mean by writing $2^{2^n}+1$ in that form? It looks like prime factorization but where are the exponents of primes?
a22886
02.12.2022 16:00
Note that the consecutive primes can be equal, so it's just spliting the exponent
Anshu_Singh_Anahu
25.09.2024 08:43
How does it works for n=3