2^2^n+2^2^{n-1}+1-Iran 3rd round-Number Theory 2007

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

2^2^n+2^2^{n-1}+1-Iran 3rd round-Number Theory 2007

G H J

Reveal topic tags

number theory unsolved

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5452 posts

#1 h Jul 28, 2010, 6:52 PM • 1 Y

Y by Adventure10

Prove that $2^{2^{n}}+2^{2^{{n-1}}}+1$ has at least $n$ distinct prime divisors.

This post has been edited 1 time. Last edited by Amir Hossein, Jul 28, 2010, 8:14 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1354 posts

#2 h Jul 28, 2010, 8:08 PM • 2 Y

Y by Adventure10, Mango247

Induction !

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5049 posts

Rust

#3 h Jul 29, 2010, 4:48 AM • 1 Y

Y by Adventure10

All prime divisors of $\Phi_{3*2^k}(2), \ k\le n$ (they are distinct) give prime divisors of $2^{2^n}+2^{2^{n-1}}+1.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1948 posts

#4 h Jul 29, 2010, 5:00 AM • 1 Y

Y by Adventure10

This is pretty similar to USAMO 2008, Problem 1.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1547 posts

#5 h Jul 31, 2010, 8:48 AM • 3 Y

Y by AlastorMoody, Adventure10, aidan0626

amparvardi wrote:

Prove that $2^{2^{n}}+2^{2^{{n-1}}}+1$ has at least $n$ distinct prime divisors.

Induction best works here.The proof is trivial now using the identity
$x^4+x^2+1=(x^2+x+1)(x^2-x+1)$
And this problem shows that "There exists infinitely many primes"

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SomeonecoolLovesMaths

3209 posts

SomeonecoolLovesMaths

#6 h Apr 8, 2025, 8:06 PM

Y by

We will proceed with induction.
Base Case: $n=0,1,2$
It works of course!
Inductive Step: Assume it works till $k=n-1$ and proof for $k = n$ .
Let $x = 2^{2^{n-2}}$ .
Thus $2^{2^{n}}+2^{2^{{n-1}}}+1 = x^4 + x^2 + 1 = \left(x^2 + x + 1\right)\left(x^2 - x + 1\right) = \left(2^{2^{n-1}} + 2^{2^{n-2}} + 1\right)\left(x^2 -x + 1\right)$ .
By induction, $2^{2^{n-1}} + 2^{2^{n-2}} + 1$ has at least $n-1$ distinct prime divisors.
$\gcd(x^2 + x +1, x^2 - x + 1) = \gcd(x^2 + x + 1 , 2x) = \gcd(x^2 + x + 1,x) = 1$ .
Thus, for $x > 1$ $\exists$ a prime $p$ such that $p \nmid x^2 + x + 1$ but $p \mid x^4 + x^2 + 1$ .
Hence $\exists$ $n$ distinct prime divisors of $2^{2^{n}}+2^{2^{{n-1}}}+1$ by induction. $\blacksquare$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a