Primality Certificate for (1046^4177-1)/1045

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 34.512135% 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.377515%

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₁= 523077669 3546593143 8935128900 4257686994 1093037704 1652207053 7219584672 9685079592 9051651860 8470886525 6346701687 4194376984 9702649109 9628452085 1487678408 2413726727 7334742307 4914474905 4814235237 5496978571 2931787654 0560292713 9559582638 6983179343 4698510166 6717508073 0631900658 0213601398 0615000644 5067295995 0811056837 6701748301 1407497624 6037938114 0064284338 0474464650 3155513552 3411032732 4967258438 3432633753 6949502453 4852872328 5497588820 0535599142 8802350525 0187830436 0565970489 4022013760 7833702140 2441710851 6595886279 2344616746 3327376786 8373844041 2502168689 7152391503 7486401296 9758483290 4786729703 2162774407 3809009447 3528245584 1081195912 3684212900 1283839157 9493638931 1473483273 5806900618 3144075394 7379890547 3539680768 7196077038 1840722762 3406376212 6357691727 7958959675 1741303665 2949324615 5360954350 8470257575 3238604128 8823376060 7210629575 6619323914 1697624824 5874453090 3372266043 7812116324 4789953952 5970393110 6509457094 4505128707 2588422954 9030512962 0852865706 5245872780 8780092629 4284803149 0291056875 6940778579 9339292519 7439339843 0314175629 4256618824 2843900226 8313442341 9331537385 3697011329 4475876480 0568865705 3756823620 5101893134 5885756996 2940773085 6081515289 9222289597 4009027183 9912099041 2744990534 5230397540 4074049163 1333736322 4747106133 6379208632 8064419989 0935329354 1485648723 7749823624 8203615099 0244550050 6326388571 7224700807 4756404657 2565832713 8867322783 0567089665 8468424387 8909195580 6618759238 0359302584 4073489877 0181759535 3125870993 1157836484 0143636960 3798486035 7630428080 1456132140 8350522017 2779530680 0081160354 6723029052 2247844669 1836954731 0974305237 7830464112 4178350986 4133758511 1594307928 5944570593 7453829413 2849900282 7683706928 6010454178 0674222044 3613536608 5356919259 9221290913 5474541114 4378884433 1019390843 7914971657 1728519294 2321903473 4613587632 1534498872 1186346027 8373533292 4548333328 6584033623 1219359862 8223525239 2655538812 2763925250 7634944890 1148826331 4367274838 6657234191 5585853684 3698810084 9147733397 0461412387 7971225853 5511014176 2446205724 8687618076 3299873111 7543907475 9814543194 4967983339 2960054632 9672356727 4741663551 9475595675 0158691466 6558812462 9700877536 9887738981 5930833396 9432250172 7593279481 8949321308 9329249700 9780718021 8938769112 0822921868 3652987199 0246471247 6143142836 8656981698 5713318716 0830650624 4012294423 5384657354 4996887215 9281557890 9859139302 4048800206 1457960002 6632980151 2817114997 1243436514 7760477289 1531564010 1216544933 0990087422 6580850737 6350573745 3046412703 2034033613 3006105418 3214293526 0311341126 1558791083 9681637765 7481639174 5741331424 3175453539 6669925589 2096763188 1034068588 8080636246 2204643530 4898217617 2160510100 5503297160 4519726890 6601945875 9033752571 3536979531 5743908095 7948129293 3785578921 1672133042 1117687622 7519948744 2011073588 3942974371 3734818460 9277774939 6633581006 3162660972 0877296180 3431684366 3106022203 1977953826 8139659066 2211128764 6927995004 8426440117 3786004032 3892659103 8846052159 4802659472 4935363109 1189954831 5841185886 1058007191 8241366614 1514633225 4377426801 7914244984 1292325615 7381770263 9165265060 6892775691 2052131243 9513179425 7205993471 0897828769 4528078262 0700130118 9017739644 0374562551 1336175284 2069089061 4146753189 2689175605 9209374640 9449004369 8076316437 8067607430 1589125460 3393470077 8398150747 5354335172 5548085089 5990394595 6353815371 4061467500 7270182496 3155894510 5840321617 2691204486 6612419666 2564387052 3012095844 5866830599 3308428068 1337681872 1684795681 9157859686 2917266355 0130104579 7902857276 3132408783 3421611258 4351164312 3416761174 5301613988 3710371370 5466597243 2400242700 3713239490 5352198090 1180768408 1134765592 7524438299 6842931000 5732302702 7337877950 6653676167 0662977516 1199852671 9131116759 1029179578 3391547372 8465726745 8257872580 6564933419 4929655975 9837428741 1555266544 8884466575 5242129308 8928427709 9338738476 9206109591 9310002297 2649968765 0462958927 5912642640 1725241335 3167477034 1664695034 7326021595 1637394371 3967057509 2474418294 4243157676 8050825321 3201130850 8423016458 9203032616 1462039278 5937018329 5421806247 9984881976 1920259063 9872096438 8498037783 0681920692 9321330934 6923296979 8553160409 3992432167 8296400164 0977678749 1523321899 1323529860 4894874793 6345506679 7264971678 0704289959 3383724081 7914833455 6941133266 0819418605 6446992905 0625212515 8825006018 8366660314 4140746000 6004514830 7774706204 2504771881 1732178114 1516184171 9405024803 7631694900 1350816711
• c₂= 111 1783042685 7312695796 5545708384 8666533863 2516675577 2688999609 9513375143 1624722280 5361396516 7254108891 6333345659 5653639947 7497435061 8141774247 2073797225 8284407312 3967282439 7397761098 9231807290 2478837837 1503991685 4802219671 5566497122 1202443269 3688648290 5878653600 0024699915 9632490843 1833789992 2701577266 1547759754 8602274144 0836375541 2037330976 8979404637 3353665007 4502058882 3450392336 7213830763 5874528918 9711443459 5316405479 9061520798 7280027245 7365607298 1159896987 5783979718 0435079867 3340261884 4930140408 9339882438 1218803131 7956698023 3598269955 6053518145 3374483437 3805920703 1679821841 5404331407 1912037067 5448376334 8930249571 2902815511 0053478638 6073528895 7784232382 2537746368 5517544973 5124413015 6603902370 2560984754 7477359460 2829558823 4740988745 2583649333 6044626666 8170408621 4495687272 9952038219 6406560311 4114122233 7332211175 5742958779 7140986661 5029726276 9161811119 0083351040 4662641357 8848702799 7665296332 9316299786 9422366240 4989660275 7484020222 1170066389 8807974147 9316830875 1965355596 3432326861 5585650245 0907266030 2342234685 2347811030 4993674015 5779857568 3178363934 0533609241 2793051070 8292897606 5515765827 4690067186 5618021402 8748613760 9691130660 1686538179 0510511770 5845132491 3786055555 7069169489 6243557319 4380945233 6768260606 3379035257 8508277631 2915405693 9760351569 3338622071 7827370936 0577204766 5948808498 0091287045 4197734901 3284293999 6961027399 1329775833 9035788396 2697052502 3190975433 8847787587 6596341637 0217976995 8050838215 6054508027 2833252741 7399442951 3175099325 0222797664 4076416853 2783800774 6640476462 9827045422 0692583993 7237721725 4477209660 6382617283 4060516344 2255788119 5393317398 9074918938 9367604480 4421446453 9158378034 2993756801 1762043978 0283250301 7727370660 5885214572 7069973010 0350283421 1483816208 4054251796 4871019019 7011812518 8873411946 8778778102 0762972516 5073934508 8713561636 8016129284 4414282985 8984378381 1330653119 3003038716 9272964463 6668003280 4326723517 1962180513 5011588797 2863143532 7143798646 2513640803 8240036629 0866748051 5474738131 6267193523 6560101411 7438015411 4294230992 4048637712 5797644987 0882822270 7172000102 5602619252 1174378681 5624555785 7851621249 5306747084 8019505943 3306401169 9010058030 6884162066 3386861623 1242888892 7595560106 5889688276 4889397320 7402159158 3600900276 7964564328 3217609750 5765288611 8034825969 5433127710 2490437410 9123883272 5681587597 2234538362 2854759459 4457527244 6153823386 6640943875 6342217260 9114392513 3264352478 2097211788 4803960162 4480415973 3521759903 9276090923 1988557241 9730837246 0054956589 6830698845 0676093225 0902669598 1926348658 2811981063 5021564382 4162038455 3561548580 3179410430 0301138305 7587321955 4439971877 7756236434 5749877415 8919460906 5587192556 8786799142 5494814880 0716577918 9954265108 5027294676 0975016536 7268325810 2357816968 3669745002 7566655916 1425107628 6151342080 7745658865 0351972912 4934869803 2810445953 5036554092 3126164376 3554863414 8384729140 1258139032 3877991640 2757400937 8033773964 6533596167 6956520389 3663132119 5851784946 9708135855 7818026766 5358323269 5883110414 7129742977 8399627411 0191452695 7070384130 4276899063 2865120158 9687104496 5029607092 8594590616 8435771047 6475800702 1905835825 4347734775 5412310458 4803863525 4163944939 0603572815 9811183034 2347100441 7882196076 2206152925 1075174274 5314416680 1351092032 3511791813 3819188715 0205077684 5632455692 9808972975 2751673023 0279874917 3880142388 7633150403 8871634279 8431968416 0687776412 6572241410 4741012070 0015854945 3170240313 0637257312 3718476092 8373971564 0696467458 3166431345 3820868591 9311075770 0000501052 9033084374 3047173712 9589017723 1023518817 7039198214 0101067010 5407056124 8295907458 0896107185 5258098793 6445498562 6648226013 8949695263 6059679906 6640896518 5398780296 1553773247 8705590172 4628228258 4686435720 4729625569 0118543164 4647499992 9169969427 8910934258 5807737348 6777111880 2197474355 1813231145 1627693638 5733103846 1547589677 8688714903 9858465585 8411689485 2495238845 8437913120 3318083533 3829228393 2779186771 1596536244 9741760892 9671338907 9179230332 9256131535 9526526399 2438092992 5758892075 7882258480 0167047880 1717142975 2570156916 5150264738 2287997851 4888955289 3441000656 3546621077 0680584095 7158485041 5701048382 7434006908 6892698821 6841560815 8870372324 5479377188 8695892893 9477152114 8520900175 5652497454 0360138047 5368884052 1053262626 6428641966 6230041283 6589422480 2858600817 6580843826 6871879866 4707017546 4224890653 1023590731

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 ≡ 5 (mod 64) and therefore cannot be a square and N is prime.