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?

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

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:

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

But this is just mindless numberology as RDS would say :smile:

[QUOTE=ATH;468109]But this is just mindless numberology as RDS would say :smile:[/QUOTE]

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 [I]a priori[/I], unlike the current case.

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

[QUOTE=CRGreathouse;468106]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?[/QUOTE]

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

[QUOTE=science_man_88;468131]my thought is it would depends on the quotient of n and m[/QUOTE]

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?

[QUOTE=CRGreathouse;468133]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?[/QUOTE]

[CODE]2^8879+303739843600201780229559357872879038676960262489120195396723638998386369890038384347169507383794208257305119708925611845957893440035529761546248224756230767606752407310994540509660479841943513239686495448676228199698281726798850373670605908211847089753771780571077949002583513663473223344864754609701535480409879741814202008451374223594253273338745920903205607983895885697555806555700912609856502909956209520899216710452298409514515636738682062057845107588533406479128630166867761639022270110110762690636707255336367286918997683459678286072386081898493352245877510407780124799058145776090722286700535274838167871601421024786128849558822139144189073627202143461275694302581161258415736458497691860378003790969727712041542428731279066292722243380936317979225441328182908556733707758258584262580041071041333987564312827358831370497954482254000137040954082327647542702005756369083290192173944035718508162926782380486815954072415385425690001638203642361196864188922891377697597927061833052145533277265687337313858223160139880019730440678276848576203349118070144067627678557509284101387202419427518991094392418619357285940945273143463556390952338150467206805485171189836851829900235122268422480301237556359386947806404061028773184022065103025877386099112846442971272563735370285345397467391193917506960993423226790520769683657185925534429235797970480327689586345492894344091596871373639287420784197550009277863211605715335721876795661089858869975705296870969980226659899341726237943469881216989519141760748639521383738582321918888612240325623721733954547168367500411960675720879754691059795041922459584290430897032198268143269357355048117785359372315780270623591952141525727594811498433443743320645519382959338398244302686596029195524515604303766843257933891111558477455958856720245297786015832542677839519521027937892620305626644077540180226200920983529636026616758124104348968339977658316215817940220609391586687783647605813069597324475757683483826449937124417317831740809158897251701847069932641966026189208302966420138171899694319436242735487769554487631012482643735747896809769871207428988832505299169713019981532607144268117176000942123286321844097269197782673981866419942559664522614908178077083153873325845127021366104828459991988840763715491047020274685126508527096302438704781681091776736198928410372912110609390745114911006718553015678440174524001900860192817049215977962656305499211339938834233267445162302267352483791017550347477263965099707453345312033500109301625433767365662369885884313117778750328710649817819537819845353095370834969189392778773766659381272488974525407230622645671554248689906463134653364715181836300836549017090866522057867263[/CODE] is the cofactor if I did the math correctly but I can't say I know how to deal with it off hand.

[QUOTE=CRGreathouse;468106]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?[/QUOTE]

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

[QUOTE=CRGreathouse;468133]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?[/QUOTE]

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

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

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

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

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

In your example, where [TEX]9089=61\times 149[/TEX], the primitive of [TEX]2^{61}-1[/TEX] is the [URL="http://www.factordb.com/index.php?id=1000000000000000061"]entire thing[/URL]. If [TEX]f[/TEX] is a factor of this primitive, then [TEX]f-1[/TEX] is an even multiple of 61. See [URL="http://www.factordb.com/index.php?id=1100000000027905681"]here[/URL].

Continuing your example, the primitive of [TEX]2^{149}-1[/TEX] is the [URL="http://www.factordb.com/index.php?id=1000000000000000149"]entire thing[/URL]. If [TEX]f[/TEX] is a factor of this primitive, then [TEX]f-1[/TEX] is an even multiple of 149. See [URL="http://www.factordb.com/index.php?id=1100000000493725055"]here[/URL], [URL="http://www.factordb.com/index.php?id=1100000000978628479"]here[/URL], and [URL="http://www.factordb.com/index.php?id=1100000000035148364"]here[/URL].

For the [URL="http://www.factordb.com/index.php?id=1100000000006709815"]big primitive[/URL], from (1), if [TEX]f[/TEX] is any factor of the big primitive, then [TEX]f-1[/TEX] will be an even multiple of 9089. See [URL="http://www.factordb.com/index.php?id=1100000000978628579"]here[/URL].

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.

[QUOTE=CRGreathouse;468106]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?[/QUOTE]
Well, as I'm sure you know, the prime divisors of the cyclotomic factors of PHI[sub]m[/sub](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.

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.

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