 mersenneforum.org Composite integers n satisfying prime exponents of Mersennes
 Register FAQ Search Today's Posts Mark Forums Read 2017-01-05, 00:57 #1 carpetpool   "Sam" Nov 2016 22·79 Posts 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?   2017-01-05, 02:05   #2
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×3,041 Posts Quote:
 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.

Quote:
 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?"
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.   2017-01-05, 02:08   #3
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts Quote:
 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.   2017-01-05, 02:14   #4
carpetpool

"Sam"
Nov 2016

4748 Posts Quote:
 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?   2017-01-05, 02:30   #5
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20B116 Posts Quote:
 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.

Last fiddled with by science_man_88 on 2017-01-05 at 02:55   2017-01-05, 03:56   #6
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

912310 Posts Quote:
 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.)   2017-01-05, 04:13 #7 axn   Jun 2003 22·11·107 Posts The primitive part of Mersenne numbers will obey the property   2017-01-05, 04:36   #8
carpetpool

"Sam"
Nov 2016

4748 Posts Quote:
 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.

Last fiddled with by carpetpool on 2017-01-05 at 04:44  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post ixfd64 PrimeNet 2 2018-02-28 07:54 kruoli FactorDB 5 2018-02-16 16:54 heliosh Lounge 1 2018-01-19 14:19 storflyt32 storflyt32 112 2015-01-09 04:19 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