20201003, 23:11  #1 
"James Short"
Mar 2019
Canada
17 Posts 
Question about number of the form 2^n + 1
Let be the nth Highly Composite Integer* and . If , will always be equal to either 1 or a prime number?
*https://en.wikipedia.org/wiki/Highly...n%20the%20OEIS). 
20201004, 16:43  #2  
Feb 2017
Nowhere
3×7×199 Posts 
Quote:
We have b_{5} = lcm([3,5,17,65,4097]) = 3*5*13*17*241, and 2^{24} + 1 = 16777217 = 97*257*673. Thus c_{6} = (2^{24} + 1)/gcd(3*5*13*17*241,97*257*673) = (2^{24} + 1)/1 = 97*257*673 

20201006, 18:20  #3  
"James Short"
Mar 2019
Canada
10001_{2} Posts 
Quote:
I didn't think a counter example could be found for such small . My mistake was in assuming that the nonprimitive part of must contain many factors from smaller where is another highly composite integer. However just because is highly composite, doesn't mean that . In this case, even considering only the primitive part of which is we still get a composite integer, which is kind of surprising because we can also prove that any prime factor of the primitive part of must be of the form , which greatly restricts the possible number of "eligible" prime factors to nearly 1% of all primes that the are in the range from . However when , we get which is a factor lol! 

20201007, 11:51  #4 
Feb 2017
Nowhere
10123_{8} Posts 
I considered the algebraic factorization of 2^m + 1. Write m = k*2^t where k is odd. Then we have (2^(2^t))^k + 1. If k > 1 this has 2^(2^t) + 1 as a proper factor. So I looked at
2^1 + 1 = 3, 2^2 + 1 = 5, 2^4 + 1 = 17, 2^6 + 1 (algebraic factor 2^2 + 1, cofactor 13 is prime), 2^12 + 1 (algebraic factor 2^4 + 1 which appears earlier on list; cofactor 241 is prime). Then 2^24 + 1 = (2^8)^3 + 1. Hmm. Algebraic factor, 2^8 + 1 = 257, prime, not a factor of any preceding 2^m + 1. I was pretty sure the cofactor would not divide the lcm, so I had a counterexample. It was then just a matter of working out the details. 
20201014, 12:14  #5 
Aug 2020
2×19 Posts 
Not really related to this specific question, but also a question about 2^n + 1:
Why aren't they researched in regard to being prime? It is basically a Proth number with k = 1. I just checked for n <= 200 and got primes only for n = 1, 2, 4, 8, 16  or F(0) to F(4). Is this sequence similar to Fermat and there are no known primes for 2^n + 1 other than those I mentioned above? If so, is it proven? Googling didn't yield any results surprisingly, but looking up formulas can be hard. 
20201014, 12:37  #7  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
5·19·61 Posts 
Quote:


20201014, 13:02  #8 
Aug 2020
2×19 Posts 
Ok, thanks. So 2^n+1 is proven to only be prime if it is a Fermat number.

20201014, 15:02  #9  
Dec 2012
The Netherlands
62D_{16} Posts 
Quote:


20201014, 17:20  #10 
Aug 2020
2×19 Posts 
Having looked at the proof, what I don't get is, why is ?
Wolfram expressed it differently as . For that proof, I don't understand why if n = a*b with b being an odd integer. That it's equivalent to the product, I also don't get. Last fiddled with by bur on 20201014 at 17:24 
20201014, 17:49  #11 
Dec 2012
The Netherlands
3055_{8} Posts 
It's an example of what's called a telescopic sum: if you multiply out the brackets on the right hand side, then all terms cancel except for the first and the last.
If it's not clear, try writing it out with a small example such as r=3. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A question about primes of a particular form  enzocreti  enzocreti  55  20190427 11:10 
Special Form of Mersenne and Fermat Number Factors  michael  Math  31  20150904 05:57 
Lucasnumber prime factor form proofs  Raman  Math  1  20120912 13:21 
Statics Question, in the form of a storey  jinydu  Lounge  14  20120713 06:23 
Closed form solution of x^2 = 2 mod Fermat number  mpenguin  Factoring  10  20050929 07:46 