Number of Factors for a Mersenne Number

kurtulmehtap · 2010-05-03, 11:04

Dear All,
Sometimes I see this expression:
Let Mq=u*v = (2aq+1)(2bq+1) where u and v are primes and Mq a mersenne number. (Like in Sascha Pfallers Mersenne conjecture).
This is true if there are only 2 prime factors of Mq.
If we have more than 2 factors then (2bq+1) is not a prime but a product of primes. then (2bq+1)= (2cq+1) (2dq+1) (2eq+1) (2fq+1) ....
Am I right or am I missing something?

Is there a way to detect if Mq has only 2 factors without trial factoring or any other method?

R.D. Silverman · 2010-05-03, 11:29

Quote:

Originally Posted by kurtulmehtap

Dear All,
Sometimes I see this expression:
Let Mq=u*v = (2aq+1)(2bq+1) where u and v are primes and Mq a mersenne number. (Like in Sascha Pfallers Mersenne conjecture).
This is true if there are only 2 prime factors of Mq.
If we have more than 2 factors then (2bq+1) is not a prime but a product of primes. then (2bq+1)= (2cq+1) (2dq+1) (2eq+1) (2fq+1) ....
Am I right or am I missing something?

You are correct.

Quote:

Is there a way to detect if Mq has only 2 factors without trial factoring or any other method?

What do you mean by "any other method"? The only way to determine
the number of prime factors is to factor the number.

kurtulmehtap · 2010-05-03, 11:45

Quote:

Originally Posted by R.D. Silverman

You are correct.

What do you mean by "any other method"? The only way to determine
the number of prime factors is to factor the number.

Maybe elliptic curve...I'm not sure.

I assume that there is no way to know if Mq has more than 2 factors besides factoring...

kurtulmehtap · 2010-05-03, 12:25

Quote:

Originally Posted by kurtulmehtap

Maybe elliptic curve...I'm not sure.

I assume that there is no way to know if Mq has more than 2 factors besides factoring...

In addition,
Is there a known rule for (2bq+1) as
(2bq+1)= (2cq+1) (2dq+1) (2eq+1) (2fq+1) .... is not a prime and all the prime divisors are congruent to +- 1 mod 8.

R.D. Silverman · 2010-05-03, 12:39

Quote:

Originally Posted by kurtulmehtap

In addition,
Is there a known rule for (2bq+1) as
(2bq+1)= (2cq+1) (2dq+1) (2eq+1) (2fq+1) .... is not a prime and all the prime divisors are congruent to +- 1 mod 8.

Known rule for WHAT??? I can't make sense of your question.

kurtulmehtap · 2010-05-03, 12:42

Quote:

Originally Posted by R.D. Silverman

Known rule for WHAT??? I can't make sense of your question.

Like 2bq +1 is also congruent to +-1mod 8.

(2bq+1)= (2cq+1) (2dq+1) (2eq+1) (2fq+1) .... is not a prime and all the prime divisors are congruent to +- 1 mod 8.

Should I replace the word rule with property?

R.D. Silverman · 2010-05-03, 12:54

Quote:

Originally Posted by kurtulmehtap

Like 2bq +1 is also congruent to +-1mod 8.

(2bq+1)= (2cq+1) (2dq+1) (2eq+1) (2fq+1) .... is not a prime and all the prime divisors are congruent to +- 1 mod 8.

Should I replace the word rule with property?

May I suggest that you study some basic facts about modular
arithmetic? Trivially if a = b = 1 mod 8, then ab = 1 mod 8 as well.
If a = 1 mod 8 and b = -1 mod 8 then ab = -1 mod 8........

Why is this a mystery?

Mini-Geek · 2010-05-03, 12:58

It's already known that any and all factors q (whether prime, as proven here, or composite, as trivially proven at the end of this post given the previous proof concerning prime factors) of a Mersenne number (2^p-1 with p prime) must be of the form q=2kp+1 and q=+-1 mod 8.
This is quite useful for trial factoring, but I don't see how what you're doing is helpful...

Proof that all composite factors also follow the rules for prime factors:
(where 2ap+1 and 2bp+1 are prime factors, show that their product can be expressed as 2kp+1 by determining k)
(2ap+1)*(2bp+1)=2kp+1
4abp^2+2bp+2ap+1=2kp+1
4abp^2+2bp+2ap=2kp
2abp^2+bp+ap=kp
2abp+b+a=k

And, two numbers p and q that are +- 1 mod 8 will always multiply to +- 1 mod 8. (e.g. when p and q are both equal to -1 mod 8, their product is equal to (-1)(-1) mod 8, which is 1 mod 8)

kurtulmehtap · 2010-05-03, 13:23

Quote:

Originally Posted by R.D. Silverman

Known rule for WHAT??? I can't make sense of your question.

Quote:

Originally Posted by Mini-Geek

It's already known that any and all factors q (whether prime, as proven here, or composite, as trivially proven at the end of this post given the previous proof concerning prime factors) of a Mersenne number (2^p-1 with p prime) must be of the form q=2kp+1 and q=+-1 mod 8.
This is quite useful for trial factoring, but I don't see how what you're doing is helpful...

Proof that all composite factors also follow the rules for prime factors:
(where 2ap+1 and 2bp+1 are prime factors, show that their product can be expressed as 2kp+1 by determining k)
(2ap+1)*(2bp+1)=2kp+1
4abp^2+2bp+2ap+1=2kp+1
4abp^2+2bp+2ap=2kp
2abp^2+bp+ap=kp
2abp+b+a=k

And, two numbers p and q that are +- 1 mod 8 will always multiply to +- 1 mod 8. (e.g. when p and q are both equal to -1 mod 8, their product is equal to (-1)(-1) mod 8, which is 1 mod 8)

You are absolutely right,
2kp+1 in your example is equal to +- 1 mod 8. Is it equal to a value modulus other than 8?

ATH · 2010-05-03, 13:33

Quote:

Originally Posted by kurtulmehtap

You are absolutely right,
2kp+1 in your example is equal to +- 1 mod 8. Is it equal to a value modulus other than 8?

I assume you mean if there are other properties of factors of mersenne numbers?

Yes, they are equal to one of these 16 numbers mod 120:
+-1, +-7, +-17, +-23, +-31, +-41, +-47, +-49

kurtulmehtap · 2010-05-03, 13:36

Quote:

Originally Posted by ATH

I assume you mean if there are other properties of factors of mersenne numbers?

Yes, they are equal to one of these 16 numbers mod 120:
+-1, +-7, +-17, +-23, +-31, +-41, +-47, +-49

Thats right...
Can I ask how you have calculated these values? Forgive my ignorance...

2010-05-03, 11:04	#1
kurtulmehtap Sep 2009 2²×3² Posts	Number of Factors for a Mersenne Number Dear All, Sometimes I see this expression: Let Mq=u*v = (2aq+1)(2bq+1) where u and v are primes and Mq a mersenne number. (Like in Sascha Pfallers Mersenne conjecture). This is true if there are only 2 prime factors of Mq. If we have more than 2 factors then (2bq+1) is not a prime but a product of primes. then (2bq+1)= (2cq+1) (2dq+1) (2eq+1) (2fq+1) .... Am I right or am I missing something? Is there a way to detect if Mq has only 2 factors without trial factoring or any other method?

2010-05-03, 12:58	#8
Mini-Geek Account Deleted "Tim Sorbera" Aug 2006 San Antonio, TX USA 2·3·23·31 Posts	It's already known that any and all factors q (whether prime, as proven here, or composite, as trivially proven at the end of this post given the previous proof concerning prime factors) of a Mersenne number (2^p-1 with p prime) must be of the form q=2kp+1 and q=+-1 mod 8. This is quite useful for trial factoring, but I don't see how what you're doing is helpful... Proof that all composite factors also follow the rules for prime factors: (where 2ap+1 and 2bp+1 are prime factors, show that their product can be expressed as 2kp+1 by determining k) (2ap+1)(2bp+1)=2kp+1 4abp^2+2bp+2ap+1=2kp+1 4abp^2+2bp+2ap=2kp 2abp^2+bp+ap=kp 2abp+b+a=k And, two numbers p and q that are +- 1 mod 8 will always multiply to +- 1 mod 8. (e.g. when p and q are both equal to -1 mod 8, their product is equal to (-1)(-1) mod 8, which is 1 mod 8) Last fiddled with by Mini-Geek on 2010-05-03 at 13:05*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Special Form of Mersenne and Fermat Number Factors	michael	Math	31	2015-09-04 05:57
Number of distinct prime factors of a Double Mersenne number	aketilander	Operazione Doppi Mersennes	1	2012-11-09 21:16
Estimating the number of prime factors a number has	henryzz	Math	7	2012-05-23 01:13
Some Properties of Mersenne Number Factors	princeps	Miscellaneous Math	18	2011-11-30 00:16
Number of factors	JohnFullspeed	Math	2	2011-07-19 15:03