2 2 0 + 1 2 2 1 + 1 2 2 2 + 1 2 2 3 + 1 2 2 4 + 1 = = = = = 3 5 1 7 2 5 7 6 5 5 3 7
Fact : The numbers above: 3 , 5 , 1 7 , 2 5 7 , 6 5 5 3 7 are all primes.
True or false?
" 2 2 5 + 1 is a prime."
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.
I believe this problem was featured in the famous paper, "The Strong Law of Small Numbers."
Yes , I saw it on youtube, on Numberphile
woah, I didn't know that there was a conjecture that n ≥ 5 ⟺ F n is composite :o
You can read more about the fermat primes here
This are the list of conjectures related to Fermat's Primes -
We can show that 641 divides
2
2
5
+
1
without doing a "brute force" calculation. Note that
6
4
1
=
2
4
+
5
4
=
5
×
2
7
+
1
and consider the following congruences modulo 641:
2
2
5
+
1
=
1
+
2
4
×
2
2
8
≡
1
−
5
4
×
2
2
8
=
1
−
(
5
×
2
7
)
4
≡
1
−
(
−
1
)
4
=
0
That's one way of getting the answer, Kudos! +1
Now prove that 2 7 4 1 7 7 divides 2 2 6 + 1 . Hehehehe..
I will make that a project for my retirement ;)
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!
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 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 Fermat primes can be called primes of the form 2 m + 1 , m ∈ Z + , since 2 m + 1 , m ∈ Z + can only ever be prime if m has no odd prime divisor --
If m = p ( p odd prime), then 2 p + 1 = 3 ( 2 p − 1 − 2 p − 2 + ⋯ + 1 ) , where ( 2 p − 1 − 2 p − 2 + ⋯ + 1 ) is larger than 1 for all odd primes p , since 2 p − 1 − 2 p − 2 = 2 p − 2 > 1 .
If m = k p , k ∈ Z > 1 ( p odd prime), then 2 k p + 1 = ( 2 p + 1 ) ( 2 k p − p − 2 k p − p − 1 + ⋯ + 1 ) , where ( 2 k p − p − 2 k p − p − 1 + ⋯ + 1 ) is larger than 1 for all odd primes p and k ∈ Z > 1 , since 2 k p − p − 2 k p − p − 1 = 2 k p − p − 1 > 1 .
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.
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 = 1 0 2 4 , but it should be 2 2 5 = 2 ( 2 5 ) = 2 3 2 = 4 2 9 4 9 6 7 2 9 6
2 2 5 + 1 = 4 2 9 4 9 6 7 2 9 7 = 6 4 1 × 6 7 0 0 4 1 7 so it is not a prime number.
What motivates you to factor out 6 4 1 ?
It's a computer science problem so I used Python coding to factorization it.
Wolfram Alpha or a simple python program.
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 , can you elaborate for 6 k − 1 ?
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
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 . Which means that 2 2 5 + 1 is in the form of 6 k − 1 for some positive integer k . So what conclusion are you making?
@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 – What I'm trying to say that it is a necessary condition for a prime to be of form 6 k + 1 or 6 k − 1 but it is not a sufficient condition. Else, numbers like 2 5 , 3 5 , 4 9 , 5 5 , 6 5 , 7 7 , … would also be prime numbers.
@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 – If you managed to prove that it is not a form of 6 k ± 1 , then it would simply be divisible by 2 and/or 3 right? I assume you made an arithmetic error into assuming that it was neither 6 k + 1 nor 6 k − 1 and that's why you said it's a composite number, am I wrong?
@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 – 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 , or 6 k + 5 . Removing the two cases mentioned proves that the number is divisible by 2 and/or 3 .
@Pi Han Goh – Ok... I did not know this :) thanks for bringing this up!! cheers..
Problem Loading...
Note Loading...
Set Loading...
The numbers of the form 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 are the only primes.
Infact, it still remains a open problem to prove that -
Is F n composite for all n > 4
Also, it has been verified that F k is a composite number for 5 ≤ k ≤ 3 2