Primality Certificate for (11398^3319-1)/11397

This certificate uses a theorem of Brillhart, Lehmer and Selfridge to prove an integer N prime by making use of a partial prime factorization of N-1.

Factorizing N-1

As N is a Generalized Repunit, we make use of the algebraic factorization of N-1 to arrive at the following 35.199993% factorization of N-1:

From this partial factorization, we use sufficient of the largest prime factors of N-1 so that their product F is at least N ^1/3 :

Note that all prime factors listed above have been proven. As primes of under 250 decimal digits can be verified in a few seconds, proof of their primality is not included here, in order to save space. Larger prime factors can take from hours to months to prove; certificates for all such factors have been PKZIPped into this file.

We set R = (N-1)/F. Note that GCD(F,R)=1 and Log(F)/Log(N) = 33.361590%

Finding a Witness to Primality

Next, we find an integer witness w such that for each prime factor p of N-1, w^(N-1) ≡ 1 mod N and GCD(w^(N-1)/p-1,N) = 1. In this case, w = 2 suffices.

Express N in base F

As F² < N < F³ and N ≡ 1 (mod F), we can let N = c₂·F² + c₁·F + 1.

• c₁= 4 1482921005 3948391690 5511801848 3430666295 4697055277 2596901494 2195570524 8547191674 2801380758 4151534232 9251676661 2778974984 9263973310 8921915134 2658555846 5053347074 1868430736 1334742468 2896015210 0272846122 9881927238 7990498887 5373892162 8618079567 2585205505 5694077137 1367077130 2308418511 8208482145 4206820037 7519189529 9584292561 8825903000 2575909333 4106241008 0842279759 7658923438 1900591968 0490713883 8869133575 3291901478 4913875096 7232528760 4458591208 4896932237 4846304224 7162339185 9928885106 2175296790 5962527525 7152232723 4255306591 7506522088 5902202421 9988944207 4355802734 4200091108 1801988842 9732930924 1682817223 4883563607 9334036619 1982587434 7291769035 1516137364 3312072227 9195082037 8642581147 3412114717 0187715646 7459566984 6455122719 6659965627 4993172215 9475304071 0975563045 2181600301 8400004508 6133857343 2013147170 2846618184 6794955200 4199652596 6829756479 5241623341 5333736941 9902669940 7169313588 1722026872 9042245546 7045414067 7186041643 2692118265 1141157911 4826867421 6478660492 8169192731 7689543936 4415168591 7473444414 7628630076 0760506904 2380089497 9910128142 9969614723 2900003190 1245582105 7308088317 9510933665 6100695251 9511977321 9050398792 6633041217 4425100823 3460952037 5279745567 9675267425 9301246232 6902338892 8103465441 8928056564 0519394341 1960985401 5322923648 9927680072 9149206704 6246475295 0566550933 1188926746 0624578380 6011009402 0424541313 7953214292 7139737851 5834390781 4114544675 2656439753 3888472343 0605474572 0366267303 1491797030 2345775688 6922102014 5753908866 1905277534 7555267104 9691206174 2052268719 8828644859 7425511683 7289900591 6345124637 2818813364 7513542168 3763511313 4718486474 7404838219 8476704800 4498767394 6237752856 3891907978 5150920486 7438942031 5358848227 8892712159 7913478507 5821690305 1155531424 8652071032 6453343837 2257716155 2788251272 9310578572 5147591249 7851135571 8332362031 3207250788 4050762643 6514960104 7278383190 5189088745 8297295413 1792435467 2293502157 3913710133 2344454067 0151430707 0091658049 4453270047 3690233736 6577238691 2203220383 5271081456 5274478565 7445823952 9023486811 4117532908 8637088929 0211802864 3493992419 0232122396 1252460575 8031699268 6701397237 5702708310 6046895051 6414328448 8752540474 9210615306 2302921378 2320304228 3639465662 4591832261 2842689568 2164119468 5915261195 0845146653 9215875035 1827676016 1328825321 6364106177 7757692094 5182933495 1369467694 9986201312 3532893454 2670253184 1574675564 0597187363 4394835971 3698508131 6645415205 2787148185 9296994027 8285685590 0019525590 6514315649 9141841609 3441176907 3546381903 8956485971 4071627959 3302474358 1633159672 5939368167 8790682041 4976038609 7225900995 3698286536 6595834238 4822533580 5327303105 4462236684 6908987227 7933311864 8287591790 8599394206 0844135191 3909777197 8032325436 1385476543 6666947772 4642744422 0770492935 4525369257 9707364725 5369857007 0729540737 5989799642 9665331756 0403563566 4552411295 2701965904 6375433107 6643965929 4302047435 0644737152 9431439716 5962574337 3763881983 0987819687 7064635764 4209621158 9348811243 0326219994 3514725115 0298554631 3928788940 0211508137 5198805133 4458056798 7623741815 6659984661 6262127272 3281366291 6612681994 4268889717 0179671524 3562741956 1863356900 7617276231 4082017695 9317764705 1609688296 5458092869 7897028656 6437253370 5634328475 2961563066 4414526853 1823191574 7831172625 4009438035 5813679357 0105242941 1084525676 7984119567 9769492132 7300078368 1079677312 4544481271 1874750215 1991821381 3561777414 9113957510 7846700634 1285371555 0769823392 7451103004 7701001377 0521388740 5259385107 6722584680 6399258995 6683390206 7942962666 6670568849 0616720509 6470926311 1227665017 7148496584 9595109366 8894417791 2449498593 7078141180 8155717894 2771347896 6721054639 9159331470 2206060522 5092242791 3396905576 4416606282 7033963439 6132011446 9012594177 4290783836 2151623626 2068885268 7990362634 9702976133 2244978133 4892685065 9989475824 1899552866 7331902919 6154204950 2519932365 8155783537 1705266405 7371952528 4367461055 9022910917 2341196178 0255505398 7195835767 5832030813 5648056750 8410825935 6925566041 9380631829 8568171535 7834837734 2795190193 5756579843 6614154513 4104589932 0518212759 4604411105 2351101597 9156917857 7854766540 1384847257 6902520532 8542335412 4179878335 9715087748 4736700876 0939777071 8290109844 3426102303 4029961617 1578779843 9511858335 0098685805 1351148063 5308099456 3042147065 6059393243 4703292790 6648810996 5319924942 9246691400 0251812562 8407971019 2192822887 2303936619 4130111874 3497967979 1916139245 1649885877 6727242824 8293242186 0388488882 4220154427 0777012026 4255914204 2673976076 2652439202 4123424111 1860074710 9249322480 8705389294 3108987094 8285346361 0039561979 7105135291 3117030700 6153644986 5910657969 5734642591 0656350204 1942503037 5600828886 1765045950 9345909884 7770505008 8169667837 2294887026
• c₂= 1759993959 7734015113 8492256553 4777615972 5220056472 6079525077 3133648905 8208977633 9519814472 7958663135 9378200679 8706685918 4492662203 5728238978 0661010440 9774367259 0966534213 2182463820 6875064674 8506369364 4247722485 7687962381 9890247486 4678034348 6701492283 4175338503 1340893943 6304295359 3398414617 0921299123 8310276702 7834244638 6683844415 3588337571 6271037559 2802108065 6841307604 6032708939 7130352595 3286356656 6857323512 1006089124 2110807775 1173086773 2643274455 4024002194 6107147289 3841541123 0216516856 9806837996 5194954778 3259447998 1546030919 2701958327 2962202721 2145950531 3450101706 4744501881 7790416010 4225931555 7340052266 9335922876 5412549771 8289092666 8245195855 6342265507 1497394474 2956281992 6223919583 1045195961 7596698930 6348152507 2180096912 3285201385 4968686985 3323318862 5171569629 5461936280 1475318655 2641298261 2736190216 3509164387 8866504413 3277015339 6954938273 4907253796 6168278007 9014755546 6532870018 6067785578 1731492889 0560901354 1310884628 2076534645 0314651477 1223636117 6825734732 1507847711 8412799019 2977532643 3620782930 7232307663 9306666771 2927062326 8042878521 2852216020 4162928733 6953906766 0402899481 8178577539 8010152214 6147170993 5366063758 5924265427 7101783260 6008265311 9216671236 4896112087 0499935644 3620426364 9269998913 7484365949 8926125301 3420714355 5400159290 2221363271 4712887430 8658164662 7609185316 1709751905 4527333478 1547445795 5298537545 6037121579 4702014587 1284756583 5239660911 7638469411 6101316930 7125547437 6537583335 2344968559 5472448825 1093990943 8244042327 6328585818 3003640337 6516985672 1792391103 9005076388 8455356311 1093211013 6460040875 4125701368 4928514923 2299175603 8066784569 8090245003 5095277999 8600540233 5420652765 4888419388 9819190685 1575293071 4941199981 9721488208 3998485971 6961749491 5586778769 3268533333 9016360789 7329169956 8190752264 9766594162 7169111922 8471251385 5951383360 8259729048 3596236461 1868958651 7781453369 5591237630 1311016442 2318818890 1112427114 6451283570 1042194456 0558110094 1273476123 5772107178 6619596663 3712966207 7508216929 5472730060 7949736534 5715194049 6108729135 7266591550 9205710426 8890429242 7793579492 5404495693 6959501683 1393049834 5655377480 3503748442 0231661255 9569358669 8678696221 3834917034 0797895742 9828697247 1837237141 5164496629 8367723977 6142977433 3032894628 4722731892 6294584197 2880206688 9362973187 4200505597 7327022873 3772750293 3578803733 1329135752 9744556448 5081356606 8339282148 0450904077 1514617965 2342037248 4857169126 8766543015 8620216968 8792338159 7854557768 4386641112 1674828673 5903674229 1878797996 5652053802 7184594721 0269064832 4943783008 0263981365 5590175719 1749640574 5366335628 3263611262 7810816472 5476269562 5658645042 6530562206 4880723469 4595824103 0460156231 1230737786 5729827927 3086633016 2505487025 5309513758 8366584976 2523549801 3544246952 3903482944 9761071327 1352519338 5883292271 2534739438 0086395108 8921769718 3714874327 8707915554 3543126269 8886329947 3853077449 7796524285 8439206811 9883626418 6508615651 8171117906 8469108346 3057379294 7698472915 5845772085 8860957347 6557147798 4241353792 3699181316 7958389131 9018639133 2858772858 0676238853 3663541789 2313328739 5586653550 2153310940 8077183476 2869964687 5537161005 7340580627 0621721884 5981440187 2364273024 0264104224 5370787473 9250353629 1563155794 9418421027 8814708172 7239449354 5003738408 9465611009 5542448378 4861987804 5992850774 3197863550 3619051774 9977370058 2128761995 7428133151 4002821859 4762665152 0118778835 1628295178 8287055589 9959382266 7216204404 5555955458 9439444698 1881416339 3393175497 8292542178 5222604991 2054685040 9710563549 4379195491 9711202811 7750411786 1744635977 4541545815 5205907653 5214088660 4768176809 9832632667 7735016519 4858932707 9197288764 3122182306 5249510982 1175002509 6386036980 8038109278 8194954904 5484479191 4812019517 1167245698 4785140349 2913167351 4328808974 2729074843 6372339905 0382542104 5205922747 3674742907 8901230238 7224095578 3716216959 6490480413 9345580137 2515496749 9269072878 8268728831 5125412538 2270017037 7079042835 6348949726 1543540031 6341408090 0699576538 9621098452 0242346455 0514850478 3633161059 2942375611 6600528648 6200609479 4281646002 1322749589 5606367504 1190114724 5112918212 0014840496 5844493738 7190869468 1188234425 3334992749 9878960260 5600180002 1003429238 4409010057 8821110637 1745746891 0100565168 7658689992 0837210562 4747714304 6699962411 4932256258 3690933420 6778576019 1020554140 3738864904 6466585789 4705342640 2873598646 9055745985 8735176962 0842599836 7824754543 3304185671 8333212813 1277062146 9667917426 3528255724 4158455651 7781287218 1436410304 4794279311 2141458230 7465554552 6062435528 7252395076 2324902808 2071858704 0175793591 7021138573 4134426440 3560361411 5482650794 3773418611 7636187463 6252282480 1811266043 7089555187 0956895805 2384460760

Brillhart, Lehmer and Selfridge's Theorem shows that N is prime if and only if c₁²-4·c₂ is not a square.

Here, c₁²-4·c₂ is ≡ 6 (mod 63) and therefore cannot be a square and N is prime.