 mersenneforum.org > Math Number of Factors for a Mersenne Number
 Register FAQ Search Today's Posts Mark Forums Read  2010-05-03, 11:04 #1 kurtulmehtap   Sep 2009 22·32 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, 11:29   #2
R.D. Silverman

Nov 2003

25×233 Posts 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.

Last fiddled with by R.D. Silverman on 2010-05-03 at 11:29 Reason: typo   2010-05-03, 11:45   #3
kurtulmehtap

Sep 2009

2416 Posts 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...   2010-05-03, 12:25   #4
kurtulmehtap

Sep 2009

22·32 Posts 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...
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.   2010-05-03, 12:39   #5
R.D. Silverman

Nov 2003

25×233 Posts 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.   2010-05-03, 12:42   #6
kurtulmehtap

Sep 2009

22×32 Posts 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?   2010-05-03, 12:54   #7
R.D. Silverman

Nov 2003

25·233 Posts 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?   2010-05-03, 12:58 #8 Mini-Geek Account Deleted   "Tim Sorbera" Aug 2006 San Antonio, TX USA 10000101010112 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   2010-05-03, 13:23   #9
kurtulmehtap

Sep 2009

22×32 Posts 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?   2010-05-03, 13:33   #10
ATH
Einyen

Dec 2003
Denmark

2,857 Posts 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   2010-05-03, 13:36   #11
kurtulmehtap

Sep 2009

22·32 Posts 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...   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post michael Math 31 2015-09-04 05:57 aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16 henryzz Math 7 2012-05-23 01:13 princeps Miscellaneous Math 18 2011-11-30 00:16 JohnFullspeed Math 2 2011-07-19 15:03

All times are UTC. The time now is 11:34.

Mon Jul 13 11:34:18 UTC 2020 up 110 days, 9:07, 0 users, load averages: 1.49, 1.44, 1.45