Composite integers n satisfying prime exponents of Mersennes

[carpetpool]

I think this is the right sub-forum to post in for my question.

Given the following

Theorem 1:

If n is an odd prime, each divisor p of 2^n-1 has the form 2nk+1 and 8r+-1.

Correction: If n is an odd number, each divisor p of 2^n-1 has the form 8r+-1.

Proofs can be found on this page.

Are there any composite integers n following Theorem 1? Is there a proof that there do or do not exist composite integers n with this property and also if infinitely exist? Are there any known examples? Thanks for answering.

One case scenario is a prime n in https://oeis.org/A000043 being a Wieferich Prime. The composite number n^2 follows theorem 1. No known examples.

The other part I know of is n not being a multiple of 2, 3, 5, 7, 11, 13, etc. Any other thoughts/improvements?

[Batalov]

Originally Posted by carpetpool

Correction: If n is an odd number, each divisor p of 2^n-1 has the form 8r+-1.

That's obviously true but what does it help?
We already know that for 2^p-1 to be prime, p must prime.
So we are not interested in non-prime odd n values in the GIMPS process.

Originally Posted by carpetpool

Are there any composite integers n following Theorem 1? Is there a proof that there do or do not exist composite integers n with this property and also if infinitely exist? Are there any known examples? Thanks for answering.

How can a composite n follow the Theorem 1?
n is an odd prime in Theorem 1.

Theorem 1's backbone is the "if S1, then S2" structure.
What you are trying to ask is
"if not S1, then 1) is S2 always false? 2) is S2 always true? 3) is S2 sometimes true and sometimes false?"
...and the answer is "3".
Counterexamples to both 1 and 2: take n=15, then 2^n-1 has factors 7, 31, 151 and 31 is = 2nk+1, but 7 2nk+1

So your new Theorem 1-like proposition comes down to this
"If n is an odd composite, then anything can happen."

That's not much of a statement, right?

P.S. You choice of the subforum was exactly right! Thanks for getting into the right forum.

[science_man_88]

Originally Posted by carpetpool

I think this is the right sub-forum to post in for my question.

Given the following

Theorem 1:

If n is an odd prime, each divisor p of 2^n-1 has the form 2nk+1 and 8r+-1.

Correction: If n is an odd number, each divisor p of 2^n-1 has the form 8r+-1.

Proofs can be found on this page.

Are there any composite integers n following Theorem 1? Is there a proof that there do or do not exist composite integers n with this property and also if infinitely exist? Are there any known examples? Thanks for answering.

One case scenario is a prime n in https://oeis.org/A000043 being a Wieferich Prime. The composite number n^2 follows theorem 1. No known examples.

The other part I know of is n not being a multiple of 2, 3, 5, 7, 11, 13, etc. Any other thoughts/improvements?

let M(n) =2^n-1 then we know that M(2n) :

1. is divisible by M(n) in fact it's 2^n*M(n)+M(n)
2. is of form 8r+7 if n>1

etc.

[carpetpool]

Originally Posted by Batalov

That's obviously true but what does it help?
We already know that for 2^p-1 to be prime, p must prime.
So we are not interested in non-prime odd n values in the GIMPS process.


How can a composite n follow the Theorem 1?
n is an odd prime in Theorem 1.

Theorem 1's backbone is the "if S1, then S2" structure.
What you are trying to ask is
"if not S1, then 1) is S2 always false? 2) is S2 always true? 3) is S2 sometimes true and sometimes false?"
...and the answer is "3".
Counterexamples to both 1 and 2: take n=15, then 2^n-1 has factors 7, 31, 151 and 31 is = 2nk+1, but 7 2nk+1

So your new Theorem 1-like proposition comes down to this
"If n is an odd composite, then anything can happen."

That's not much of a statement, right?

P.S. You choice of the subforum was exactly right! Thanks for getting into the right forum.

Yes, thanks for the grammatical/wording improvements. A better way to put it:

Property 1:

Integers n such that all divisors p of 2^n-1 is of the form 2kn+1 and 8r+-1.

Are there any integers n following property 1 that are composite?

[science_man_88]

Originally Posted by carpetpool

Property 1:

Integers n such that all divisors p of 2^n-1 is of the form 2kn+1 and 8r+-1.

Are there any integers n following property 1 that are composite?

case 1:
if 2kn+1 = 8r+1 then 2kn=8r so kn=4r so there would have to be a factor of 4 in there

case 2:

if 2kn+1 = 8r-1 then 2kn+2 = 8r which when you factor out a 2 you get kn+1 = 4r so kn must be an odd number of form 4j+3 for j=r-1.


edit: and following the links at the bottom of the page you linked to earlier we get that n can't have any sophie germain factors as the mersennes of prime exponents dividing such a case would need the original k to have all the factors of n for it to be of form 2kn+1 for the new value n.

[Batalov]

Originally Posted by carpetpool

Yes, thanks for the grammatical/wording improvements. A better way to put it:

Property 1:

Integers n such that all divisors p of 2^n-1 is of the form 2kn+1 and 8r+-1.

Are there any integers n following property 1 that are composite?

No, there are not. Prove it!

But don't even think about suggesting that this is a primality test for n.
Because in order to prove that a tiny n is prime, you will have to factor 2^n-1 completely, then prove primality of prime factors ...which are much larger than n. (I.e. sell a car to buy a loaf of bread. Only you don't have a car, so you sell the house to buy a car, and so on.)

[axn]

The primitive part of Mersenne numbers will obey the property

[carpetpool]

Originally Posted by Batalov

No, there are not. Prove it!

But don't even think about suggesting that this is a primality test for n.
Because in order to prove that a tiny n is prime, you will have to factor 2^n-1 completely, then prove primality of prime factors ...which are much larger than n. (I.e. sell a car to buy a loaf of bread. Only you don't have a car, so you sell the house to buy a car, and so on.)

I am not sure how to prove that there exist no composite integers n following Property 1 above, but it is extremely easy to show that composite n, if any won't be a multiple of (prime) k. Yes, it would require a complete factorization of 2^k-1 as you said. Take the gcd of (s-1, s_2-1..., s_n-1) for each divisor s_n dividing 2^k-1. If the result is of the form 2^x*k, then there exist no composite n such that k | n (again satisfying p. 1). Proof done.

To show that at least 1 composite k | n:

If some other odd prime factor y which is not k divides all s_n-1, and for all divisors v_n-1 of 2^y-1 the gcd of (v-1, v_2-1..., v_3-1) is of the form 2^x*y*k*z, then 2^(ky)-1 follows property 1 and ky is obviously composite so we are done with this case. Of course there are many more scenarios/case of a composite n occurring. These are a few basic ones.