Isn't 100000 such a huge number (Part-5)?

Number Theory Level 4

Find the sum of all the primes of the form $(n^n + 1)$ which are less than 100000 where $n$ is a natural number.

The answer is 264.

3 solutions

Discussions for this problem are now closed

Trevor Arashiro
Dec 25, 2014

Plug in 1, it works=2

Plug in 2, it works=5

All odds besides 1 don't work

Plug in 4, seems legit to work=257

5 obviously won't work

$6^6+1$ is a sum of cubes $(6^2+1)(6^4-6^2+1)$ , therefore, it ain't prime

7 is too big

We can conclude the answer is either 7 or 264.

Since we're allowed 3 answers, we win #lifehackz

Moderator note:

Sometimes the K eep I t S imple, S tupid (KISS) method works the best. Though you should be able to prove that $257$ is prime quite easily.

This is the dumbest solution of all time.

Trevor Arashiro - 6 years, 5 months ago

This is the same as my solution. Not the worst solution I have seen by far.

A Former Brilliant Member - 6 years, 5 months ago

Mathh Mathh
Dec 23, 2014

It can be proved using Zsigmondy's theorem that $n=2^{m}$ for some $m\in\mathbb N$ with the exception of $n=1$ . It can further be shown using Zsigmondy's theorem that $m=2^k$ for some $k\in\mathbb N$ with the exception of $m=1$ .

Thus the number is $2^{2^{2^k+k}}+1$ and we know that $k\le 4$ , thus $2^k+k\le 20$ and it is known that the Fermat numbers $2^{2^{c}}+1$ , when $0\le c\le 32$ , are prime if and only if $0\le c\le 4$ and therefore $k=1$ is the only solution.

Therefore $n=1, n=2, n=4$ are the only solutions (by checking them, they work).

Zsigmondy's theorem is an overkill for this.

Hint: Show that if $n$ has an odd prime factor, then $n^n + 1$ is not prime.

Calvin Lin Staff - 6 years, 5 months ago

If $n$ is odd, then $n^n+1$ is always even. Here, $n=1$ is an exception since $2$ is the only even prime number. But we still have to check the largest $n$ such that $n<100000$ .

Marc Vince Casimiro - 6 years, 5 months ago

Yes, that deals with the case when $n$ is odd. However, this doesn't deal with the cases when $n$ is even as yet.

Note that I said "if $n$ has an odd prime factor". This would include values like 6, 10, etc.

The complement of "n has an odd prime factor" is that "the only prime factors of n are 2" hence that "n is a power of 2".

Calvin Lin Staff - 6 years, 5 months ago

@Calvin Lin – Can you please explain why if n has an odd factor then n^n+1 is composite?

Tanishq kancharla - 6 years, 5 months ago

@Tanishq Kancharla – Recall the algebraic identity $x^ p + y^p = (x+y)( x^{p-1} - x^{p-2} y + \ldots - x y^{p-2} y^ {p-1} )$ for $p$ odd.

Hence, if $n = ab$ where $a \geq 3$ is odd (not necessarily prime), then

$n^n + 1 = n^{ab} + 1= (n^b) ^ a + 1 = ( n^b + 1 ) ( n^{ b (a-1) } - n^{ b (a-2) } + \ldots - n^{ba} + n^ 0 )$

Thus, $n^b + 1$ is a factor of $n^n + 1$ , so it is not composite.

Calvin Lin Staff - 6 years, 5 months ago

Yes, this can easily be solved without using Zsigmondy's theorem and factoring a sum of two odd powers instead.

However, using Zsigmondy's theorem easily generalizes the problem - the only solutions to $n^n+1=p^l, n,l\in\mathbb N, p\in\mathbb P, n\le 10^5$ are still $n=1, n=2, n=4$ , since we can use Zsigmondy's theorem for the 3rd time with $2^{2^{2^k+k}}=p^l-1^l$ .

(when $l\ge 2$ and the size of $n$ is not restricted, there are no solutions).

mathh mathh - 6 years, 5 months ago

Bill Bell
Dec 23, 2014

Mr Mathh's approach is really nice. However, there are not many numbers to check.

Isn't 100000 such a huge number (Part-5)?

The answer is 264.

3 solutions

Discussions for this problem are now closed

Moderator note:

0 pending reports