mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > carpetpool

Reply
 
Thread Tools
Old 2017-01-05, 00:57   #1
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

22·79 Posts
Post Composite integers n satisfying prime exponents of Mersennes

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?
carpetpool is offline   Reply With Quote
Old 2017-01-05, 02:05   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×3,041 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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.

Quote:
Originally Posted by carpetpool View Post
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 \ne 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.
Batalov is offline   Reply With Quote
Old 2017-01-05, 02:08   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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.
science_man_88 is offline   Reply With Quote
Old 2017-01-05, 02:14   #4
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

4748 Posts
Post

Quote:
Originally Posted by Batalov View Post
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 \ne 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?
carpetpool is offline   Reply With Quote
Old 2017-01-05, 02:30   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20B116 Posts
Default

Quote:
Originally Posted by carpetpool View Post

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.

Last fiddled with by science_man_88 on 2017-01-05 at 02:55
science_man_88 is offline   Reply With Quote
Old 2017-01-05, 03:56   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

912310 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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.)
Batalov is offline   Reply With Quote
Old 2017-01-05, 04:13   #7
axn
 
axn's Avatar
 
Jun 2003

22·11·107 Posts
Default

The primitive part of Mersenne numbers will obey the property
axn is online now   Reply With Quote
Old 2017-01-05, 04:36   #8
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

4748 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.

Last fiddled with by carpetpool on 2017-01-05 at 04:44
carpetpool is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Composite P-1 factors not showing up under recently cleared exponents? ixfd64 PrimeNet 2 2018-02-28 07:54
Composite being Prime kruoli FactorDB 5 2018-02-16 16:54
Satisfying numbers heliosh Lounge 1 2018-01-19 14:19
I take a known prime and prove it to be a composite (..or maybe need help?) storflyt32 storflyt32 112 2015-01-09 04:19
10 and strictly prime or composite.Comment. David John Hill Jr Miscellaneous Math 7 2010-06-06 12:33

All times are UTC. The time now is 10:41.

Wed Oct 21 10:41:35 UTC 2020 up 41 days, 7:52, 0 users, load averages: 1.92, 1.64, 1.58

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.