What, if anything, can be said about the factors of 2^n - 1 when n is composite?

CRGreathouse · 2017-09-19, 16:35

I'm interested in finding small prime factors of 2^n - 1 for some composite values of n. Of course I can search for known factors of 2^m - 1 where m | n, but when I've done that and split out the cofactors of each do the remaining factors have any special form?

ATH · 2017-09-19, 17:38

When I found factors of M(p^2) in this thread:
http://www.mersenneforum.org/showthread.php?t=14249

They were all of the form 2*k*p + 1 and 2*c*p^2 + 1 at the same time.

Looking at composite 2^(a*b)-1 factors it looks like some factors are 2*k*a+1 and some are 2*c*b+1 and some are of both formats:

http://factordb.com/index.php?query=2%5E77-1
http://factordb.com/index.php?query=2%5E247-1

But this is just mindless numberology as RDS would say

GP2 · 2017-09-19, 19:43

Quote:

Originally Posted by ATH

But this is just mindless numberology as RDS would say

Arguably there's such a thing as "experimental math".

In particular, you could formulate a hypothesis as you have done, and then conduct an experiment, in the classic scientific method, to try to negate the hypothesis. Say, write a bot to download known factor data for 2^n-1 from FactorDB.com and look for a counterexample. Also, in practice, sometimes looking for patterns in experimental data helps you formulate a hypothesis in those cases where nothing obvious suggests itself a priori, unlike the current case.

Where math differs from science is that sometimes you can go a step further and actually prove your hypothesis true.

science_man_88 · 2017-09-19, 21:49

Quote:

Originally Posted by CRGreathouse

I'm interested in finding small prime factors of 2^n - 1 for some composite values of n. Of course I can search for known factors of 2^m - 1 where m | n, but when I've done that and split out the cofactors of each do the remaining factors have any special form?

my thought is it would depends on the quotient of n and m because for example $2^{2n}-1 = (2^n-1)\cdot(2^n+1)$ and depending on n that second factor could be a fermat number which could have special properties for it's divisors.

CRGreathouse · 2017-09-19, 22:10

Quote:

Originally Posted by science_man_88

my thought is it would depends on the quotient of n and m

For example, take 2^9089 - 1 where 9089 = 61 * 149. Of course both 2^61 - 1 and 2^149 - 1 are factors, but what can be said of the remaining factors?

science_man_88 · 2017-09-19, 22:24

Quote:

Originally Posted by CRGreathouse

For example, take 2^9089 - 1 where 9089 = 61 * 149. Of course both 2^61 - 1 and 2^149 - 1 are factors, but what can be said of the remaining factors?

Code:

2^8879+303739843600201780229559357872879038676960262489120195396723638998386369890038384347169507383794208257305119708925611845957893440035529761546248224756230767606752407310994540509660479841943513239686495448676228199698281726798850373670605908211847089753771780571077949002583513663473223344864754609701535480409879741814202008451374223594253273338745920903205607983895885697555806555700912609856502909956209520899216710452298409514515636738682062057845107588533406479128630166867761639022270110110762690636707255336367286918997683459678286072386081898493352245877510407780124799058145776090722286700535274838167871601421024786128849558822139144189073627202143461275694302581161258415736458497691860378003790969727712041542428731279066292722243380936317979225441328182908556733707758258584262580041071041333987564312827358831370497954482254000137040954082327647542702005756369083290192173944035718508162926782380486815954072415385425690001638203642361196864188922891377697597927061833052145533277265687337313858223160139880019730440678276848576203349118070144067627678557509284101387202419427518991094392418619357285940945273143463556390952338150467206805485171189836851829900235122268422480301237556359386947806404061028773184022065103025877386099112846442971272563735370285345397467391193917506960993423226790520769683657185925534429235797970480327689586345492894344091596871373639287420784197550009277863211605715335721876795661089858869975705296870969980226659899341726237943469881216989519141760748639521383738582321918888612240325623721733954547168367500411960675720879754691059795041922459584290430897032198268143269357355048117785359372315780270623591952141525727594811498433443743320645519382959338398244302686596029195524515604303766843257933891111558477455958856720245297786015832542677839519521027937892620305626644077540180226200920983529636026616758124104348968339977658316215817940220609391586687783647605813069597324475757683483826449937124417317831740809158897251701847069932641966026189208302966420138171899694319436242735487769554487631012482643735747896809769871207428988832505299169713019981532607144268117176000942123286321844097269197782673981866419942559664522614908178077083153873325845127021366104828459991988840763715491047020274685126508527096302438704781681091776736198928410372912110609390745114911006718553015678440174524001900860192817049215977962656305499211339938834233267445162302267352483791017550347477263965099707453345312033500109301625433767365662369885884313117778750328710649817819537819845353095370834969189392778773766659381272488974525407230622645671554248689906463134653364715181836300836549017090866522057867263

is the cofactor if I did the math correctly but I can't say I know how to deal with it off hand.

R. Gerbicz · 2017-09-19, 23:01

Quote:

Originally Posted by CRGreathouse

I'm interested in finding small prime factors of 2^n - 1 for some composite values of n. Of course I can search for known factors of 2^m - 1 where m | n, but when I've done that and split out the cofactors of each do the remaining factors have any special form?

n|(d-1) is true for the remaining d factors of 2^n-1.

rcv · 2017-09-20, 11:26

Quote:

Originally Posted by CRGreathouse

For example, take 2^9089 - 1 where 9089 = 61 * 149. Of course both 2^61 - 1 and 2^149 - 1 are factors, but what can be said of the remaining factors?

I believe the following is correct. But I'm not a mathematician, so corrections and clarifications are welcome.

Your example is a special case of the form $x^{p\cdot q}-1\text{, where }p \text{ and } q$ are distinct odd primes.

The "primitive" of that form is $\frac{(x^{p\cdot q}-1) (x^1-1)}{(x^p-1)(x^q-1)}\qquad\qquad(1)$

For Mersenne numbers, if $f$ is any factor of the primitive, then $f-1=2\cdot k\cdot p\cdot q$ , where $k$ is some integer.

More generally, if you are interested in $2^n-1$ , where $n$ is odd, you must break the factorization down to the "primitives" of the form $2^m-1$ , where $m$ divides $n$ . (The rules get somewhat complicated when $n$ is not a single odd prime or the product of a pair of distinct odd primes.)

In your example, where $9089=61\times 149$ , the primitive of $2^{61}-1$ is the entire thing. If $f$ is a factor of this primitive, then $f-1$ is an even multiple of 61. See here.

Continuing your example, the primitive of $2^{149}-1$ is the entire thing. If $f$ is a factor of this primitive, then $f-1$ is an even multiple of 149. See here, here, and here.

For the big primitive, from (1), if $f$ is any factor of the big primitive, then $f-1$ will be an even multiple of 9089. See here.

I think the front matter of The Cunningham Book contains brief information about how to obtain the primitives. You can also search for papers on Cyclotomic Polynomials.

Dr Sardonicus · 2017-09-20, 14:58

Quote:

Originally Posted by CRGreathouse

I'm interested in finding small prime factors of 2^n - 1 for some composite values of n. Of course I can search for known factors of 2^m - 1 where m | n, but when I've done that and split out the cofactors of each do the remaining factors have any special form?

Well, as I'm sure you know, the prime divisors of the cyclotomic factors of PHI_m(2) are (apart from "intrinsic" prime factors which will divide m) congruent to 1 modulo m.

If m is odd, the factors will also be congruent to 1 or 7 (modulo 8).

And you know about Aurifeuillian factors.

a1call · 2017-09-20, 17:05

I think that there can be dinner insight gained with respect to the factors of 2^n-1, when considering that its factors are actually governed by the more general the:

a^p-b^p | a^(p.q)-b^(p.q)

Analyzing as such reveals that the extra factors have a predictable geometric progression and are thrives factored essentially by chance, as is the case with any other geometric progression.

2^6-1 is divisible by 2^3-1 & 2^2-1 & 3 which just happens to be equal to the 2nd factor at this stage of the progression.

a1call · 2017-09-20, 17:14

BTW the rule is actually more herbal than I mentioned and covers additions as well as subtraction with imaginary roots/factors for odd exponents.

2017-09-19, 16:35	#1
CRGreathouse Aug 2006 1764₁₆ Posts	What, if anything, can be said about the factors of 2^n - 1 when n is composite? I'm interested in finding small prime factors of 2^n - 1 for some composite values of n. Of course I can search for known factors of 2^m - 1 where m \| n, but when I've done that and split out the cofactors of each do the remaining factors have any special form?

2017-09-19, 17:38	#2
ATH Einyen Dec 2003 Denmark 6574₈ Posts	When I found factors of M(p^2) in this thread: http://www.mersenneforum.org/showthread.php?t=14249 They were all of the form 2kp + 1 and 2cp^2 + 1 at the same time. Looking at composite 2^(ab)-1 factors it looks like some factors are 2ka+1 and some are 2cb+1 and some are of both formats: http://factordb.com/index.php?query=2%5E77-1 http://factordb.com/index.php?query=2%5E247-1 But this is just mindless numberology as RDS would say Last fiddled with by ATH on 2017-09-19 at 17:39*

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
PrimeNet has composite factors recorded	James Heinrich	PrimeNet	4	2011-09-16 14:40
is M21934219 composite ?	S485122	Data	50	2011-01-10 10:28
Missing factors at the 'Known Factors' page	MatWur-S530113	PrimeNet	11	2009-01-21 19:08
F10,21=10^(2^21)+1 is composite	Shaopu Lin	Factoring	2	2004-10-31 13:48

2017-09-20, 17:05	#10
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 95E₁₆ Posts	I think that there can be dinner insight gained with respect to the factors of 2^n-1, when considering that its factors are actually governed by the more general the: a^p-b^p \| a^(p.q)-b^(p.q) Analyzing as such reveals that the extra factors have a predictable geometric progression and are thrives factored essentially by chance, as is the case with any other geometric progression. 2^6-1 is divisible by 2^3-1 & 2^2-1 & 3 which just happens to be equal to the 2nd factor at this stage of the progression.

2017-09-20, 17:14	#11
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 2·11·109 Posts	BTW the rule is actually more herbal than I mentioned and covers additions as well as subtraction with imaginary roots/factors for odd exponents.