Just a Conjecture

2 2 0 + 1 = 3 2 2 1 + 1 = 5 2 2 2 + 1 = 17 2 2 3 + 1 = 257 2 2 4 + 1 = 65537 \begin{aligned} 2^{2^0} +1&= & 3 \\ 2^{2^1} +1&= & 5 \\ 2^{2^2} +1&= & 17 \\ 2^{2^3} +1&= & 257 \\ 2^{2^4} +1&= & 65537 \\ \end{aligned}

Fact : The numbers above: 3 , 5 , 17 , 257 , 65537 3,5,17,257,65537 are all primes.

True or false?

" 2 2 5 + 1 2^{2^{5}} + 1 is a prime."

There is insufficient information True False This question is flawed

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

7 solutions

Discussions for this problem are now closed

Kishlaya Jaiswal
Apr 3, 2015

The numbers of the form F n = 2 2 n + 1 F_n = 2^{2^n}+1 are known as fermat primes.

And it's a well-known fact (conjecture) that only F 0 , F 1 , F 2 , F 3 , F 4 F_0,\ F_1,\ F_2,\ F_3,\ F_4 are the only primes.

Infact, it still remains a open problem to prove that -

Is F n F_n composite for all n > 4 n>4

Also, it has been verified that F k F_k is a composite number for 5 k 32 5 \leq k \leq 32

I believe this problem was featured in the famous paper, "The Strong Law of Small Numbers."

Caleb Townsend - 6 years, 2 months ago

Yes , I saw it on youtube, on Numberphile

Archit Boobna - 6 years, 2 months ago

woah, I didn't know that there was a conjecture that n 5 F n is composite n\ge 5\iff F_n\text{ is composite} :o

Daniel Liu - 6 years, 2 months ago

You can read more about the fermat primes here

This are the list of conjectures related to Fermat's Primes -

  • Is F n F_n composite for all n > 4 n > 4 ?
  • Are there infinitely many Fermat primes?
  • Are there infinitely many composite Fermat numbers?
  • Does a Fermat number exist that is not square-free?

Kishlaya Jaiswal - 6 years, 2 months ago

We can show that 641 divides 2 2 5 + 1 2^{2^5}+1 without doing a "brute force" calculation. Note that 641 = 2 4 + 5 4 = 5 × 2 7 + 1 641=2^4+5^4=5\times2^7+1 and consider the following congruences modulo 641:
2 2 5 + 1 = 1 + 2 4 × 2 28 1 5 4 × 2 28 = 1 ( 5 × 2 7 ) 4 1 ( 1 ) 4 = 0 2^{2^5}+1 =1+2^4\times2^{28}\equiv 1-5^4\times2^{28}=1-(5\times2^7)^4\equiv1-(-1)^4=0

That's one way of getting the answer, Kudos! +1

Now prove that 274177 274177 divides 2 2 6 + 1 2^{2^6} + 1 . Hehehehe..

Pi Han Goh - 6 years, 2 months ago

I will make that a project for my retirement ;)

Marilyn Bretscher - 6 years, 2 months ago
Barry Evans
Apr 9, 2015

I reasoned the question wouldn't have been asked if the answer was true, since that would have been trivial. Saved a lot of factorization!

Mathh Mathh
Apr 4, 2015

Kishlaya Jaiswal talked about the Fermat primes, and I'm going to add how the definition of Fermat primes can be strenghtened without making Fermat primes more difficult to handle and it is to show you that the definition of Fermat primes is not arbitrary -- the power of 2 2 in the exponent may at first make you think that the definition is very specific and not useful.

Instead of primes of the form 2 2 n + 1 2^{2^n}+1 Fermat primes can be called primes of the form 2 m + 1 , m Z + 2^m+1, m\in\mathbb Z^+ , since 2 m + 1 , m Z + 2^m+1, m\in\mathbb Z^+ can only ever be prime if m m has no odd prime divisor --

If m = p m=p ( p p odd prime), then 2 p + 1 = 3 ( 2 p 1 2 p 2 + + 1 ) 2^p+1=3(2^{p-1}-2^{p-2}+\cdots+1) , where ( 2 p 1 2 p 2 + + 1 ) (2^{p-1}-2^{p-2}+\cdots+1) is larger than 1 1 for all odd primes p p , since 2 p 1 2 p 2 = 2 p 2 > 1 2^{p-1}-2^{p-2}=2^{p-2}>1 .

If m = k p , k Z > 1 m=kp, k\in\mathbb Z_{>1} ( p p odd prime), then 2 k p + 1 = ( 2 p + 1 ) ( 2 k p p 2 k p p 1 + + 1 ) 2^{kp}+1=(2^p+1)(2^{kp-p}-2^{kp-p-1}+\cdots+1) , where ( 2 k p p 2 k p p 1 + + 1 ) (2^{kp-p}-2^{kp-p-1}+\cdots+1) is larger than 1 1 for all odd primes p p and k Z > 1 k\in\mathbb Z_{>1} , since 2 k p p 2 k p p 1 = 2 k p p 1 > 1 2^{kp-p}-2^{kp-p-1}=2^{kp-p-1}>1 .

Niall Stoddart
Apr 4, 2015

Much simpler answer: any number raised ^5 ends with the same digit as the original number.

2^2^5 must end in a 4. Thus this result +1 this will make an answer with 5 as a factor so it won't be prime.

Moderator note:

As Pi Han Goh has pointed out, you did your operation wrongly. Try this example that have a similar example.

You're using the exponents wrongly. It's not 2 2 5 = ( 2 2 ) 5 = 4 5 = 1024 2^{2^5} = (2^2)^5 = 4^5 = 1024 , but it should be 2 2 5 = 2 ( 2 5 ) = 2 32 = 4294967296 2^{2^5} = 2^{\left ( 2^5 \right ) } = 2^{32} = 4294967296

Pi Han Goh - 6 years, 2 months ago

2 2 5 + 1 = 4294967297 = 641 × 6700417 2^{2^5}+1=4294967297=641\times 6700417 so it is not a prime number.

What motivates you to factor out 641 641 ?

Pi Han Goh - 6 years, 2 months ago

It's a computer science problem so I used Python coding to factorization it.

Chew-Seong Cheong - 6 years, 2 months ago

Wolfram Alpha or a simple python program.

Pranjal Jain - 6 years, 2 months ago
Prateek Goyal
Apr 9, 2015

The number to be prime has to be in the form of 6k+1 or 6k-1 so that mean 2^2^5 has to be divisible by 6 which if u find is not.. so the number is not prime. :)

You have only shown that it cannot be in the form of 6 k + 1 6k + 1 , can you elaborate for 6 k 1 6k - 1 ?

Pi Han Goh - 6 years, 2 months ago

yep the remainder of 2^2^5 divided by 6 is 4. had it been 5 the number would have been in the form 6k-1.. i hope this answers it

Prateek Goyal - 6 years, 2 months ago

I don't understand you logic. You have shown that 2 2 5 m o d 6 = 4 2 2 5 + 1 m o d 6 = 5 2^{2^5} \bmod 6 = 4 \Rightarrow 2^{2^5} + 1 \bmod 6 = 5 . Which means that 2 2 5 + 1 2^{2^5} + 1 is in the form of 6 k 1 6k - 1 for some positive integer k k . So what conclusion are you making?

Pi Han Goh - 6 years, 2 months ago

@Pi Han Goh Ok sorry did a mistake here this number is in the form of 6k-1 so this can be a prime still according to this method.... Thanks mate for correcting me.

Prateek Goyal - 6 years, 2 months ago

@Prateek Goyal What I'm trying to say that it is a necessary condition for a prime to be of form 6 k + 1 6k + 1 or 6 k 1 6k - 1 but it is not a sufficient condition. Else, numbers like 25 , 35 , 49 , 55 , 65 , 77 , 25,35,49,55,65,77, \ldots would also be prime numbers.

Pi Han Goh - 6 years, 2 months ago

@Pi Han Goh It is a necessary condition for a number to be prime... all the prime numbers are in this form.. while inverse is not true.. all numbers in the form of 6k+-1 are not prime... so if we were able to prove that this number is neither of the form 6k+1 or 6k-1 then we could have proved its not prime... but alas it is indeed of the form 6k-1 so it might or might not be prime as per this trick. Was i able to explain the logic i was trying to implement?

Prateek Goyal - 6 years, 2 months ago

@Prateek Goyal If you managed to prove that it is not a form of 6 k ± 1 6k \pm 1 , then it would simply be divisible by 2 2 and/or 3 3 right? I assume you made an arithmetic error into assuming that it was neither 6 k + 1 6k + 1 nor 6 k 1 6k-1 and that's why you said it's a composite number, am I wrong?

Pi Han Goh - 6 years, 2 months ago

@Pi Han Goh second part of your statement is true but not the first part.... if its not the of form 6k+-1 it would be definite that its not a prime number ..apart from that we wont be able to say any thing about it without analysing it further.... Alas this trick did not work here.... But its quite handy in many tricky problems.. so better to remember it...

Prateek Goyal - 6 years, 2 months ago

@Prateek Goyal It's true. By Quotient Remainder Theorem, all whole numbers can be written as 6 k , 6 k + 1 , 6 k + 2 , 6 k + 3 , 6 k + 4 , 6k, 6k+1,6k+2,6k+3,6k+4, or 6 k + 5 6k+5 . Removing the two cases mentioned proves that the number is divisible by 2 2 and/or 3 3 .

Pi Han Goh - 6 years, 2 months ago

@Pi Han Goh Ok... I did not know this :) thanks for bringing this up!! cheers..

Prateek Goyal - 6 years, 2 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...