Find all primes of the form n^n + 1 less than 10^{19}

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

Find all primes of the form n^n + 1 less than 10^{19}

G H J

Reveal topic tags

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.

1167 posts

#1 h Oct 15, 2019, 3:43 PM • 1 Y

Y by Adventure10

Find all primes of the form $n^n + 1$ less than $10^{19}$

The first two primes are obvious: $n = 1, 2$ yields the primes $2, 5$ . After that, it is clear that $n$ has to be even to yield an odd number.

So, $n = 2k \implies p = (2k)^{2k} + 1 \implies p-1 = (2k)^{k^2} = 2^{k^2}k^{k^2}$ . All of these transformations don't seem to help. Is there any theorem I can use? Or is there something I'm missing?

Z K Y

The post below has been deleted. Click to close.

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

9038 posts

#2 h Oct 15, 2019, 8:13 PM • 3 Y

Y by Math5000, Adventure10, Mango247

How can you factorize $x^k+1$ ? Well you can do that if $k$ is odd.
So we can factorize $n^n+1$ if $n$ has an odd prime factor, in other words if $n$ is not a power of $2$ .
More precisely, if $n=dk$ with $k>1$ odd we see that $n^n+1=(n^d)^k+1$ is divisible by $n^d+1$ and hence not a prime.
So we are left to check the cases where $n=2^k$ .
If $n=1,2$ you already checked.
If $n=4$ we have $4^4+1=257$ is a prime.
If $n=8$ we have $8^8+1=2^{24}+1$ is divisible by $2^8+1$ as above.
And then one checks that $16^{16}+1$ is already larger than $10^{19}$ .
One way to see this is to note that
$16^{16}=2^{64}=16 \cdot 1024^6>10 \cdot 1000^6=10^{19}.$

Z K Y

The post below has been deleted. Click to close.

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

SomeonecoolLovesMaths

3202 posts

SomeonecoolLovesMaths

#3 h Apr 8, 2025, 8:20 PM • 1 Y

Y by ehuseyinyigit

If $n$ has a positive odd divisor greater than $1$ , say $2k+1$ (let $n = c(2k+1)$ ) then $n^n + 1 = \left( n^c \right) ^{2k+1} + 1^{2k+1} = (n^c + 1) ( \text{ something} )$ which means that it is not a prime.
Let's check for $n$ as perfect powers of $2$ .
$n=1 \Longrightarrow 1^1 + 1 = 2$ a prime.
$n = 2 \Longrightarrow 2^2 + 1 = 5$ a prime.
$n = 4 \Longrightarrow 4^4 + 1 = 257$ a prime.
$n = 8 \Longrightarrow 8^8 + 1= 2^{24} + 1 = (2^8 + 1) ( \text{ something })$ not a prime.
$n = 16 \Longrightarrow 16^{16} + 1 = 2^{64} + 1 > 2^{64}$ . Now, $\log_{10} 2^{64} > 64 \times 0.301 > 19$ . Thus, $16^{16} + 1 > 10^{19}$ .
Thus, $\boxed{n \in \{ 1,2,4 \}}$ . $\blacksquare$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a