mersenneforum.org Factorization of (x^p-1)/(x-1) over the integers modulo n
 Register FAQ Search Today's Posts Mark Forums Read

 2022-04-10, 06:09 #1 Dobri   "Καλός" May 2018 73 Posts Factorization of (x^p-1)/(x-1) over the integers modulo n Let's start this thread with the polynomial (x^p-1)/(x-1) for p = 11, so that (x11-1)/(x-1) = x10+x9+x8+x7+x6+x5+x4+x3+x2+x+1. The corresponding composite Mersenne number is M11 = 211-1 = 2047 = 23 × 89. A complete polynomial factorization is achieved over the integers modulo n = 23 and 89 as follows: x10+x9+x8+x7+x6+x5+x4+x3+x2+x+1 = (5+x)(7+x)(10+x)(11+x)(14+x)(15+x)(17+x)(19+x)(20+x)(21+x) over the integers modulo 23, and x10+x9+x8+x7+x6+x5+x4+x3+x2+x+1 = (11+x)(22+x)(25+x)(44+x)(50+x)(57+x)(73+x)(81+x)(85+x)(87+x) over the integers modulo 89.
 2022-04-10, 06:24 #2 sweety439   "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 357710 Posts Can polynomial still be factored over the integers modulo n when n is composite?
2022-04-10, 06:29   #3
Dobri

"Καλός"
May 2018

73 Posts

Quote:
 Originally Posted by sweety439 Can polynomial still be factored over the integers modulo n when n is composite?
Concerning the Galois fields GF(n), n has to be either a prime number or a prime power.

 2022-04-10, 06:32 #4 sweety439   "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 357710 Posts So if n is neither prime nor prime power, then polynomials cannot be factored mod n?
2022-04-10, 06:53   #5
Dobri

"Καλός"
May 2018

1010101112 Posts

Quote:
 Originally Posted by sweety439 So if n is neither prime nor prime power, then polynomials cannot be factored mod n?
It can be done, here is an example for p = 16:
(x16-1)/(x-1) = (1+x) (1+x2) (1+x4) (1+x8).
However, note that p = 16 is a composite number.

Last fiddled with by Dobri on 2022-04-10 at 07:13

 2022-04-10, 11:50 #6 Dobri   "Καλός" May 2018 5278 Posts Let p = 13, then the corresponding Mersenne prime is M13 = 213-1 = 8191. The polynomial x12+x11+...+x+1 can be fully factored over the integers modulo the prime numbers n = 2kp+1 as follows: x12+x11+...+x+1 = (x+4)(x+6)(x+7)(x+9)(x+11)(x+17)(x+25)(x+29)(x+37)(x+38)(x+40)(x+43) over the integers modulo the prime number 53 = 2×2×13+1; x12+x11+...+x+1 = (x+12)(x+14)(x+15)(x+17)(x+27)(x+33)(x+41)(x+57)(x+58)(x+61)(x+69)(x+71) over the integers modulo the prime number 79 = 2×3×13+1; etc.
 2022-04-10, 12:06 #7 Dobri   "Καλός" May 2018 15716 Posts Addendum to post #1 (p = 11) for completeness: 23 = 2×11+1 and 89 = 2×4×11+1 because the factors of composite Mersenne numbers are prime numbers n = 2kp+1.
 2022-04-10, 12:16 #8 Dr Sardonicus     Feb 2017 Nowhere 23×257 Posts Sure, you can factor polynomials modulo n when n is composite. But factorization is not unique. For example: Modulo 4 we have x^2 = (x - 2)^2. Modulo 6 we have x^2 - x = x*(x - 1) = (x + 2)*(x + 3). Modulo 8 we have x^2 - 1 = (x - 1)*(x + 1) = (x - 3)*(x + 3) = (x - 5)*(x + 5) = (x - 7)*(x + 7). How bad things can get is left as an exercise for the reader. EDIT: It is well known that for n > 1, and q a prime number not dividing n, the cyclotomic polynomial $\Phi_{n}(x)$ factors in Fq[x] into polynomials of degree f, where f is the least positive integer for which qf == 1 (mod n). Last fiddled with by Dr Sardonicus on 2022-04-10 at 13:15 Reason: as indicated
 2022-04-10, 13:41 #9 Dobri   "Καλός" May 2018 73 Posts Let n = p, then xp-1+...+1 = (x+p-1)p-1 over the integers modulo the prime number p. For example: x2-1+1 = (x+2-1)2-1 = x+1 over the integers modulo 2; x3-1+x+1 = (x+3-1)3-1 = (x+2)2 over the integers modulo 3; ... x11-1+x9+...+x+1 = (x+11-1)11-1 = (x+10)10 over the integers modulo 11; x13-1+x11+...+x+1 = (x+13-1)13-1 = (x+12)12 over the integers modulo 13; ... x1277-1+x1275+...+x+1 = (x+1277-1)1277-1 = (x+1276)1276 over the integers modulo 1277; ...
 2022-04-10, 14:28 #10 Dobri   "Καλός" May 2018 15716 Posts Let p=1277, then the first integer k for which 2kp+1 is a prime is k=10 so that 2×10×1277+1 = 25541. Thus x1277-1+x1275+...+x+1 can be fully factored over the integers modulo 25541 as shown in the code section below. Code: (x+5)(x+6)(x+49)(x+59)(x+69)(x+77)(x+95)(x+114)(x+119)(x+121)(x+125)(x+142)(x+150)(x+166)(x+180)(x+187)(x+203)(x+216)(x+223)(x+224)(x+260)(x+279)(x+283)(x+289)(x+312)(x+319)(x+344)(x+352)(x+389)(x+403)(x+428)(x+436)(x+445)(x+471)(x+479)(x+493)(x+534)(x+544)(x+591)(x+641)(x+657)(x+668)(x+707)(x+734)(x+755)(x+794)(x+795)(x+815)(x+841)(x+853)(x+861)(x+862)(x+883)(x+906)(x+915)(x+917)(x+928)(x+931)(x+949)(x+954)(x+978)(x+1024)(x+1043)(x+1051)(x+1077)(x+1098)(x+1111)(x+1121)(x+1130)(x+1193)(x+1217)(x+1225)(x+1253)(x+1262)(x+1311)(x+1317)(x+1324)(x+1353)(x+1356)(x+1378)(x+1384)(x+1441)(x+1454)(x+1463)(x+1470)(x+1475)(x+1481)(x+1483)(x+1502)(x+1517)(x+1532)(x+1555)(x+1586)(x+1633)(x+1639)(x+1676)(x+1701)(x+1717)(x+1725)(x+1764)(x+1770)(x+1805)(x+1838)(x+1866)(x+1880)(x+1909)(x+1925)(x+1964)(x+1969)(x+2018)(x+2063)(x+2070)(x+2085)(x+2091)(x+2124)(x+2165)(x+2166)(x+2227)(x+2234)(x+2256)(x+2261)(x+2290)(x+2299)(x+2306)(x+2310)(x+2319)(x+2375)(x+2377)(x+2389)(x+2399)(x+2457)(x+2462)(x+2484)(x+2502)(x+2533)(x+2548)(x+2576)(x+2590)(x+2598)(x+2636)(x+2654)(x+2673)(x+2696)(x+2698)(x+2709)(x+2735)(x+2740)(x+2747)(x+2748)(x+2753)(x+2772)(x+2789)(x+2850)(x+2853)(x+2914)(x+2929)(x+2975)(x+2990)(x+2997)(x+3025)(x+3041)(x+3043)(x+3068)(x+3079)(x+3108)(x+3125)(x+3154)(x+3160)(x+3165)(x+3232)(x+3262)(x+3280)(x+3282)(x+3288)(x+3411)(x+3420)(x+3530)(x+3549)(x+3550)(x+3553)(x+3567)(x+3570)(x+3588)(x+3614)(x+3630)(x+3736)(x+3750)(x+3761)(x+3792)(x+3798)(x+3799)(x+3801)(x+3857)(x+3861)(x+3880)(x+3896)(x+3913)(x+3936)(x+3956)(x+4004)(x+4010)(x+4011)(x+4013)(x+4048)(x+4054)(x+4058)(x+4070)(x+4083)(x+4104)(x+4121)(x+4131)(x+4139)(x+4150)(x+4177)(x+4192)(x+4223)(x+4236)(x+4237)(x+4241)(x+4244)(x+4247)(x+4256)(x+4257)(x+4260)(x+4261)(x+4282)(x+4284)(x+4306)(x+4317)(x+4321)(x+4329)(x+4336)(x+4348)(x+4356)(x+4361)(x+4426)(x+4500)(x+4569)(x+4581)(x+4593)(x+4647)(x+4656)(x+4657)(x+4675)(x+4690)(x+4735)(x+4768)(x+4773)(x+4791)(x+4812)(x+4820)(x+4837)(x+4846)(x+4884)(x+4886)(x+4898)(x+4922)(x+4927)(x+4936)(x+4940)(x+4980)(x+4990)(x+5014)(x+5021)(x+5065)(x+5075)(x+5084)(x+5107)(x+5112)(x+5126)(x+5140)(x+5167)(x+5179)(x+5191)(x+5245)(x+5251)(x+5271)(x+5301)(x+5318)(x+5377)(x+5400)(x+5403)(x+5427)(x+5443)(x+5455)(x+5463)(x+5476)(x+5486)(x+5491)(x+5521)(x+5575)(x+5577)(x+5583)(x+5600)(x+5610)(x+5628)(x+5649)(x+5682)(x+5683)(x+5728)(x+5749)(x+5761)(x+5784)(x+5787)(x+5794)(x+5813)(x+5817)(x+5849)(x+5861)(x+5928)(x+5967)(x+5969)(x+5973)(x+5976)(x+5988)(x+5989)(x+6009)(x+6014)(x+6044)(x+6061)(x+6078)(x+6090)(x+6141)(x+6149)(x+6168)(x+6188)(x+6236)(x+6247)(x+6253)(x+6256)(x+6290)(x+6292)(x+6294)(x+6303)(x+6337)(x+6393)(x+6480)(x+6500)(x+6536)(x+6537)(x+6546)(x+6551)(x+6568)(x+6579)(x+6581)(x+6603)(x+6617)(x+6668)(x+6688)(x+6690)(x+6697)(x+6720)(x+6732)(x+6735)(x+6736)(x+6769)(x+6778)(x+6791)(x+6853)(x+6861)(x+6862)(x+6893)(x+6975)(x+7047)(x+7067)(x+7075)(x+7082)(x+7133)(x+7210)(x+7225)(x+7234)(x+7283)(x+7295)(x+7308)(x+7312)(x+7370)(x+7384)(x+7391)(x+7399)(x+7419)(x+7465)(x+7471)(x+7548)(x+7559)(x+7601)(x+7657)(x+7678)(x+7682)(x+7691)(x+7706)(x+7719)(x+7732)(x+7776)(x+7789)(x+7791)(x+7796)(x+7800)(x+7815)(x+7822)(x+7838)(x+7839)(x+7867)(x+7891)(x+7922)(x+7967)(x+7970)(x+7975)(x+7987)(x+7988)(x+8028)(x+8057)(x+8064)(x+8082)(x+8089)(x+8132)(x+8283)(x+8284)(x+8293)(x+8343)(x+8359)(x+8370)(x+8423)(x+8441)(x+8455)(x+8486)(x+8490)(x+8590)(x+8600)(x+8605)(x+8619)(x+8623)(x+8632)(x+8643)(x+8652)(x+8670)(x+8680)(x+8685)(x+8754)(x+8800)(x+8803)(x+8807)(x+8844)(x+8870)(x+8877)(x+8893)(x+8909)(x+8949)(x+8958)(x+8967)(x+9023)(x+9053)(x+9059)(x+9080)(x+9101)(x+9131)(x+9141)(x+9183)(x+9194)(x+9195)(x+9231)(x+9232)(x+9249)(x+9254)(x+9285)(x+9287)(x+9353)(x+9360)(x+9365)(x+9367)(x+9369)(x+9378)(x+9381)(x+9445)(x+9458)(x+9503)(x+9560)(x+9564)(x+9570)(x+9617)(x+9662)(x+9667)(x+9716)(x+9724)(x+9725)(x+9741)(x+9771)(x+9873)(x+9910)(x+9913)(x+9916)(x+9953)(x+9964)(x+9973)(x+10001)(x+10033)(x+10044)(x+10075)(x+10085)(x+10146)(x+10154)(x+10179)(x+10188)(x+10201)(x+10249)(x+10253)(x+10303)(x+10308)(x+10320)(x+10326)(x+10336)(x+10343)(x+10404)(x+10414)(x+10416)(x+10419)(x+10422)(x+10460)(x+10468)(x+10484)(x+10515)(x+10529)(x+10556)(x+10560)(x+10591)(x+10637)(x+10644)(x+10666)(x+10672)(x+10690)(x+10700)(x+10730)(x+10762)(x+10769)(x+10797)(x+10799)(x+10808)(x+10809)(x+10896)(x+10899)(x+10900)(x+10942)(x+10954)(x+10969)(x+10971)(x+11018)(x+11034)(x+11074)(x+11125)(x+11142)(x+11147)(x+11207)(x+11209)(x+11223)(x+11229)(x+11232)(x+11238)(x+11240)(x+11247)(x+11276)(x+11279)(x+11291)(x+11323)(x+11330)(x+11334)(x+11380)(x+11390)(x+11464)(x+11468)(x+11472)(x+11484)(x+11534)(x+11596)(x+11608)(x+11627)(x+11648)(x+11670)(x+11674)(x+11681)(x+11705)(x+11720)(x+11747)(x+11769)(x+11775)(x+11776)(x+11801)(x+11806)(x+11829)(x+11840)(x+11841)(x+11860)(x+11866)(x+11870)(x+11887)(x+11892)(x+11972)(x+11975)(x+11996)(x+12005)(x+12007)(x+12009)(x+12049)(x+12051)(x+12061)(x+12082)(x+12090)(x+12102)(x+12127)(x+12137)(x+12176)(x+12179)(x+12202)(x+12243)(x+12271)(x+12295)(x+12319)(x+12325)(x+12361)(x+12384)(x+12422)(x+12423)(x+12483)(x+12487)(x+12545)(x+12551)(x+12552)(x+12591)(x+12618)(x+12627)(x+12638)(x+12661)(x+12672)(x+12692)(x+12724)(x+12759)(x+12797)(x+12801)(x+12828)(x+12840)(x+12876)(x+12995)(x+13003)(x+13031)(x+13060)(x+13077)(x+13080)(x+13121)(x+13163)(x+13231)(x+13256)(x+13263)(x+13264)(x+13274)(x+13287)(x+13318)(x+13330)(x+13334)(x+13342)(x+13350)(x+13424)(x+13433)(x+13449)(x+13454)(x+13488)(x+13514)(x+13520)(x+13533)(x+13546)(x+13564)(x+13596)(x+13600)(x+13640)(x+13656)(x+13666)(x+13668)(x+13719)(x+13727)(x+13757)(x+13789)(x+13815)(x+13863)(x+13868)(x+13898)(x+13946)(x+13954)(x+13969)(x+13987)(x+13991)(x+14004)(x+14011)(x+14046)(x+14064)(x+14074)(x+14087)(x+14091)(x+14109)(x+14127)(x+14130)(x+14139)(x+14162)(x+14179)(x+14188)(x+14199)(x+14208)(x+14232)(x+14236)(x+14244)(x+14261)(x+14345)(x+14370)(x+14371)(x+14406)(x+14455)(x+14480)(x+14508)(x+14513)(x+14515)(x+14522)(x+14542)(x+14565)(x+14607)(x+14614)(x+14667)(x+14703)(x+14711)(x+14716)(x+14754)(x+14774)(x+14775)(x+14785)(x+14790)(x+14805)(x+14815)(x+14818)(x+14912)(x+14921)(x+14957)(x+14998)(x+15028)(x+15032)(x+15049)(x+15054)(x+15074)(x+15086)(x+15105)(x+15116)(x+15129)(x+15139)(x+15148)(x+15154)(x+15191)(x+15226)(x+15239)(x+15244)(x+15268)(x+15280)(x+15284)(x+15335)(x+15408)(x+15417)(x+15434)(x+15451)(x+15485)(x+15495)(x+15514)(x+15549)(x+15594)(x+15613)(x+15672)(x+15696)(x+15699)(x+15707)(x+15721)(x+15728)(x+15743)(x+15747)(x+15799)(x+15847)(x+15916)(x+15938)(x+15944)(x+15979)(x+15988)(x+15996)(x+16020)(x+16025)(x+16094)(x+16113)(x+16141)(x+16173)(x+16180)(x+16204)(x+16207)(x+16211)(x+16213)(x+16224)(x+16318)(x+16320)(x+16349)(x+16351)(x+16359)(x+16360)(x+16368)(x+16378)(x+16425)(x+16439)(x+16516)(x+16529)(x+16578)(x+16585)(x+16588)(x+16598)(x+16617)(x+16643)(x+16655)(x+16691)(x+16700)(x+16714)(x+16721)(x+16748)(x+16763)(x+16772)(x+16777)(x+16785)(x+16817)(x+16839)(x+16895)(x+16905)(x+16916)(x+16956)(x+16970)(x+16984)(x+16990)(x+17036)(x+17065)(x+17090)(x+17127)(x+17145)(x+17161)(x+17163)(x+17188)(x+17192)(x+17214)(x+17237)(x+17244)(x+17273)(x+17293)(x+17314)(x+17323)(x+17330)(x+17346)(x+17376)(x+17384)(x+17385)(x+17402)(x+17405)(x+17407)(x+17418)(x+17422)(x+17423)(x+17478)(x+17482)(x+17510)(x+17584)(x+17593)(x+17597)(x+17605)(x+17611)(x+17618)(x+17620)(x+17632)(x+17639)(x+17642)(x+17675)(x+17689)(x+17720)(x+17730)(x+17742)(x+17743)(x+17748)(x+17766)(x+17778)(x+17780)(x+17881)(x+17888)(x+17956)(x+17969)(x+17997)(x+18023)(x+18031)(x+18067)(x+18079)(x+18098)(x+18126)(x+18136)(x+18140)(x+18166)(x+18177)(x+18187)(x+18191)(x+18218)(x+18226)(x+18239)(x+18242)(x+18253)(x+18271)(x+18273)(x+18279)(x+18304)(x+18327)(x+18336)(x+18349)(x+18350)(x+18352)(x+18383)(x+18397)(x+18402)(x+18424)(x+18440)(x+18488)(x+18520)(x+18559)(x+18582)(x+18583)(x+18594)(x+18621)(x+18643)(x+18651)(x+18664)(x+18682)(x+18709)(x+18761)(x+18776)(x+18815)(x+18820)(x+18865)(x+18875)(x+18889)(x+18921)(x+18949)(x+18953)(x+18956)(x+18986)(x+19079)(x+19117)(x+19174)(x+19203)(x+19224)(x+19230)(x+19231)(x+19235)(x+19239)(x+19263)(x+19274)(x+19276)(x+19283)(x+19303)(x+19397)(x+19416)(x+19430)(x+19456)(x+19519)(x+19567)(x+19576)(x+19584)(x+19605)(x+19612)(x+19622)(x+19632)(x+19673)(x+19710)(x+19723)(x+19802)(x+19817)(x+19847)(x+19850)(x+19875)(x+19891)(x+19902)(x+19936)(x+19953)(x+19955)(x+19969)(x+19973)(x+19986)(x+20008)(x+20039)(x+20040)(x+20051)(x+20080)(x+20105)(x+20142)(x+20156)(x+20168)(x+20228)(x+20242)(x+20243)(x+20274)(x+20286)(x+20324)(x+20326)(x+20337)(x+20355)(x+20364)(x+20369)(x+20375)(x+20377)(x+20388)(x+20409)(x+20410)(x+20419)(x+20421)(x+20423)(x+20433)(x+20440)(x+20463)(x+20478)(x+20495)(x+20505)(x+20508)(x+20564)(x+20574)(x+20578)(x+20588)(x+20632)(x+20651)(x+20692)(x+20771)(x+20777)(x+20780)(x+20796)(x+20862)(x+20886)(x+20888)(x+20901)(x+20913)(x+20956)(x+20966)(x+20998)(x+21011)(x+21012)(x+21025)(x+21037)(x+21044)(x+21080)(x+21099)(x+21109)(x+21126)(x+21129)(x+21137)(x+21142)(x+21144)(x+21202)(x+21210)(x+21217)(x+21231)(x+21236)(x+21237)(x+21247)(x+21253)(x+21264)(x+21276)(x+21299)(x+21325)(x+21336)(x+21385)(x+21440)(x+21442)(x+21453)(x+21459)(x+21466)(x+21470)(x+21520)(x+21525)(x+21533)(x+21550)(x+21566)(x+21571)(x+21599)(x+21620)(x+21655)(x+21694)(x+21695)(x+21766)(x+21768)(x+21777)(x+21778)(x+21837)(x+21853)(x+21871)(x+21913)(x+21985)(x+21995)(x+21997)(x+22006)(x+22017)(x+22020)(x+22039)(x+22060)(x+22064)(x+22075)(x+22112)(x+22123)(x+22128)(x+22143)(x+22147)(x+22160)(x+22162)(x+22184)(x+22201)(x+22210)(x+22224)(x+22256)(x+22269)(x+22277)(x+22305)(x+22336)(x+22337)(x+22442)(x+22444)(x+22474)(x+22485)(x+22520)(x+22578)(x+22580)(x+22583)(x+22584)(x+22586)(x+22628)(x+22638)(x+22645)(x+22650)(x+22667)(x+22672)(x+22715)(x+22778)(x+22813)(x+22821)(x+22837)(x+22871)(x+22875)(x+22925)(x+22929)(x+22942)(x+22973)(x+23032)(x+23076)(x+23082)(x+23123)(x+23140)(x+23146)(x+23167)(x+23169)(x+23173)(x+23186)(x+23197)(x+23200)(x+23207)(x+23263)(x+23265)(x+23275)(x+23293)(x+23316)(x+23361)(x+23395)(x+23401)(x+23403)(x+23429)(x+23438)(x+23449)(x+23477)(x+23524)(x+23526)(x+23559)(x+23596)(x+23627)(x+23629)(x+23652)(x+23668)(x+23669)(x+23684)(x+23702)(x+23725)(x+23767)(x+23781)(x+23804)(x+23805)(x+23807)(x+23820)(x+23821)(x+23823)(x+23843)(x+23850)(x+23867)(x+23946)(x+23947)(x+23978)(x+23981)(x+24048)(x+24067)(x+24082)(x+24096)(x+24099)(x+24126)(x+24146)(x+24194)(x+24197)(x+24203)(x+24241)(x+24245)(x+24283)(x+24323)(x+24419)(x+24421)(x+24426)(x+24450)(x+24461)(x+24492)(x+24513)(x+24526)(x+24528)(x+24543)(x+24545)(x+24553)(x+24577)(x+24594)(x+24603)(x+24606)(x+24641)(x+24689)(x+24711)(x+24727)(x+24739)(x+24765)(x+24791)(x+24815)(x+24827)(x+24831)(x+24835)(x+24857)(x+24885)(x+24908)(x+24909)(x+24916)(x+24936)(x+24943)(x+24946)(x+24971)(x+24993)(x+24994)(x+25023)(x+25066)(x+25079)(x+25083)(x+25108)(x+25124)(x+25127)(x+25156)(x+25165)(x+25180)(x+25187)(x+25196)(x+25230)(x+25246)(x+25247)(x+25296)(x+25315)(x+25358)(x+25378)(x+25382)(x+25390)(x+25452)(x+25489)(x+25505)(x+25511)(x+25516)(x+25522)
 2022-04-18, 16:17 #11 Dobri   "Καλός" May 2018 15716 Posts If xp-1+xp-2+...+x+1 = (x+p)(x+...)... over the integers modulo 2kp+1, then 2kp+1 is a factor of the composite Mersenne number Mp. Also, if 2kp+1 is a factor of a composite Mersenne number Mp, then xp-1+xp-2+...+x+1 = (x+p)(x+...)... over the integers modulo 2kp+1.

 Similar Threads Thread Thread Starter Forum Replies Last Post bhelmes Number Theory Discussion Group 30 2021-11-26 19:47 Alberico Lepore Alberico Lepore 1 2020-05-27 12:20 axn Computer Science & Computational Number Theory 66 2011-09-01 21:55 smslca Math 3 2011-04-18 17:18 Cyclamen Persicum Math 2 2003-12-10 10:52

All times are UTC. The time now is 21:58.

Tue Aug 16 21:58:36 UTC 2022 up 40 days, 16:45, 1 user, load averages: 1.20, 1.27, 1.22