mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2010-05-03, 11:04   #1
kurtulmehtap
 
Sep 2009

22·32 Posts
Default 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?
kurtulmehtap is offline   Reply With Quote
Old 2010-05-03, 11:29   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

25×233 Posts
Default

Quote:
Originally Posted by kurtulmehtap View Post
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
R.D. Silverman is offline   Reply With Quote
Old 2010-05-03, 11:45   #3
kurtulmehtap
 
Sep 2009

2416 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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 is offline   Reply With Quote
Old 2010-05-03, 12:25   #4
kurtulmehtap
 
Sep 2009

22·32 Posts
Default

Quote:
Originally Posted by kurtulmehtap View Post
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.
kurtulmehtap is offline   Reply With Quote
Old 2010-05-03, 12:39   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

25×233 Posts
Default

Quote:
Originally Posted by kurtulmehtap View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2010-05-03, 12:42   #6
kurtulmehtap
 
Sep 2009

22×32 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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?
kurtulmehtap is offline   Reply With Quote
Old 2010-05-03, 12:54   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

25·233 Posts
Default

Quote:
Originally Posted by kurtulmehtap View Post
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?
R.D. Silverman is offline   Reply With Quote
Old 2010-05-03, 12:58   #8
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10000101010112 Posts
Default

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
Mini-Geek is offline   Reply With Quote
Old 2010-05-03, 13:23   #9
kurtulmehtap
 
Sep 2009

22×32 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Known rule for WHAT??? I can't make sense of your question.
Quote:
Originally Posted by Mini-Geek View Post
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?
kurtulmehtap is offline   Reply With Quote
Old 2010-05-03, 13:33   #10
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2,857 Posts
Default

Quote:
Originally Posted by kurtulmehtap View Post
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
ATH is offline   Reply With Quote
Old 2010-05-03, 13:36   #11
kurtulmehtap
 
Sep 2009

22·32 Posts
Default

Quote:
Originally Posted by ATH View Post
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...
kurtulmehtap is offline   Reply With Quote
Reply

Thread Tools


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

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

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.