Question about number of the form 2^n + 1
 

Let [TEX]a_{n}[/TEX] be the nth Highly Composite Integer* and [TEX]b_{n} = lcm(2^{a_{1}} + 1, 2^{a_{2}} + 1, ...,2^{a_{n}} + 1)[/TEX]. If [TEX]c_{n} = \frac{2^{a_{n}} + 1}{gcd(2^{a_{n}} + 1,b_{n-1})}[/TEX], will [TEX]c_{n}[/TEX] always be equal to either 1 or a prime number?

*[url]https://en.wikipedia.org/wiki/Highly_composite_number#:~:text=Highly%20composite%20numbers%20whose%20number,sequence%20A189394%20in%20the%20OEIS[/url]).

[QUOTE=jshort;558808]Let [TEX]a_{n}[/TEX] be the nth Highly Composite Integer* and [TEX]b_{n} = lcm(2^{a_{1}} + 1, 2^{a_{2}} + 1, ...,2^{a_{n}} + 1)[/TEX]. If [TEX]c_{n} = \frac{2^{a_{n}} + 1}{gcd(2^{a_{n}} + 1,b_{n-1})}[/TEX], will [TEX]c_{n}[/TEX] always be equal to either 1 or a prime number?

*[url]https://en.wikipedia.org/wiki/Highly_composite_number#:~:text=Highly%20composite%20numbers%20whose%20number,sequence%20A189394%20in%20the%20OEIS[/url]).[/QUOTE]No. The first six highly composite numbers are 1, 2, 4, 6, 12, and 24.

We have b[sub]5[/sub] = lcm([3,5,17,65,4097]) = 3*5*13*17*241, and

2[sup]24[/sup] + 1 = 16777217 = 97*257*673. Thus

c[sub]6[/sub] = (2[sup]24[/sup] + 1)/gcd(3*5*13*17*241,97*257*673) = (2[sup]24[/sup] + 1)/1 = 97*257*673

[QUOTE=Dr Sardonicus;558862]No. The first six highly composite numbers are 1, 2, 4, 6, 12, and 24.

We have b[sub]5[/sub] = lcm([3,5,17,65,4097]) = 3*5*13*17*241, and

2[sup]24[/sup] + 1 = 16777217 = 97*257*673. Thus

c[sub]6[/sub] = (2[sup]24[/sup] + 1)/gcd(3*5*13*17*241,97*257*673) = (2[sup]24[/sup] + 1)/1 = 97*257*673[/QUOTE]

Thanks Dr Sardonicus.

I didn't think a counter example could be found for such small [TEX]n[/TEX]. My mistake was in assuming that the non-primitive part of [TEX]2^{n} + 1[/TEX] must contain many factors from smaller [TEX]2^{m} + 1[/TEX] where [TEX]m < n[/TEX] is another highly composite integer. However just because [TEX]m[/TEX] is highly composite, doesn't mean that [TEX]m | n[/TEX].

In this case, even considering only the primitive part of [TEX]2^{24} + 1[/TEX] which is [TEX]65281 = 97 \cdot 673[/TEX] 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 [TEX]2^{24} + 1[/TEX] must be of the form [TEX]1 + 4 \cdot 24k = 1 + 96k[/TEX], which greatly restricts the possible number of "eligible" prime factors to nearly 1% of all primes that the are in the range from [TEX](2, \sqrt{65281})[/TEX]. However when [TEX]k=1[/TEX], we get [TEX]97[/TEX] which is a factor lol!

I considered the algebraic factorization of 2^m + 1. Write m = k*2^t where k is [i]odd[/i]. 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.

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.

[QUOTE="A[OEIS]019434[/OEIS]"]It is conjectured that there are only 5 terms.[/QUOTE]
:smile:

[QUOTE=bur;559847]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.[/QUOTE]

For 2^n+1 to be prime n must be a power of 2 [url]https://mathworld.wolfram.com/FermatNumber.html[/url] has a proof of this.

Ok, thanks. So 2^n+1 is proven to only be prime if it is a Fermat number.

[QUOTE=henryzz;559850]For 2^n+1 to be prime n must be a power of 2 [URL]https://mathworld.wolfram.com/FermatNumber.html[/URL] has a proof of this.[/QUOTE]
So do we!: proposition 16 [URL="https://www.mersenneforum.org/showthread.php?t=21658"]here[/URL]

Having looked at the proof, what I don't get is, why is [TEX]2^{(2r+1)s}=(2^s + 1)(...)[/TEX]?

Wolfram expressed it differently as [TEX](2^a)^b = (2^a + 1)(2^{a(b-1)}-2^{a(b-2)}+...)[/TEX]. For that proof, I don't understand why [TEX]2^n = (2^a)^b[/TEX] if n = a*b with b being an odd integer. That it's equivalent to the product, I also don't get.

[QUOTE=bur;559892]Having looked at the proof, what I don't get is, why is [TEX]2^{(2r+1)s}=(2^s + 1)(...)[/TEX]?[/QUOTE]
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.

Or look for decomposition of \(a^n\pm b^n\) for \(n\) odd or even.

For why \(x^{ab}=(x^a)^b\) think about definition of powers, as a repeated multiplication. To get \(x^n\) you multiply \(x\) by itself \(n\) times. Write down \(x\) \(n\) times, and group it in \(b\) groups of \(a\) items each. Now you have \(x^a\), written \(b\) times.

[QUOTE=bur;559892]<snip>
For that proof, I don't understand why [TEX]2^n = (2^a)^b[/TEX] if n = a*b with b being an odd integer. That it's equivalent to the product, I also don't get.[/QUOTE]You don't know the laws of exponents?

x[sup]a[/sup] * x[sup]b[/sup] = x[sup]a+b[/sup]

(x[sup]a[/sup])[sup]b[/sup] = x[sup]a*b[/sup]

The first law is initially proven for positive integers a and b; repeated application gives the second law.

Both laws can then be extended to all integer exponents by demanding that these laws continue to hold. In particular, x[sup]0[/sup] is 1.

The fact that x - y is an algebraic factor of x[sup]n[/sup] - y[sup]n[/sup] may be proved by mathematical induction, as indicated in [url=https://www.mersenneforum.org/showpost.php?p=515513&postcount=19]this post[/url], with a simplified argument in [url=https://www.mersenneforum.org/showpost.php?p=515627&postcount=25]this post[/url].

Substituting x[sup]a[/sup] for x and -y[sup]a[/sup] for y, and using the second law of exponents above, then tells you that

if b is [i]odd[/i], x[sup]a[/sup] + y[sup]a[/sup] is an algebraic factor of x[sup]ab[/sup] + y[sup]ab[/sup]