Primality Certificate for (10247^2081-1)/10246

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 42.441240% 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) = 36.513282%

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 = 29 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₁= 321502 4039410583 0764388556 8322980824 7867784083 2459837847 4547274819 8782608322 0329259701 5262302822 6435470721 5627798281 0673691830 3697915847 7827091480 0986568951 0345132641 1572085616 4117035856 1532852242 3526940902 4991574499 7144793175 3257877304 1777153768 2348165479 5728971404 3044172999 1941229660 7337669491 1926215593 6675744554 3128847289 3849455059 0575912791 7678162108 9587463606 5258321663 4584978978 3938523625 6064630216 0807903252 8657691203 3151039142 1821838527 4438259458 9842381081 0340434933 3677514645 3045319092 7475185082 4418634513 2059906404 4197260556 4120507210 4354559033 2816018902 4164446848 7198460304 3650114699 7971401303 5849373711 7813362484 8453485300 3589638433 6132053256 3309010722 8325911929 6174438584 5640621728 0978669420 9399316893 9703760001 1045681704 9757184758 6074173696 6604821599 6494458140 8635343868 1697260956 4037927366 5795346438 4977751754 7741121205 8902697963 3099380284 5805714502 2463221053 5857753354 6028914416 3455897729 4774052171 9637071597 4866448495 9616446617 3471466219 9553177162 2669013745 6937094419 3966349402 8051191475 9870482521 5004893948 9553853774 6892600511 7535735486 6328563304 6606335177 5031273206 1502806856 0527796654 8960779975 7725510397 5860362271 7271163476 9795076426 3327024512 6686594522 3072315350 5025808131 3817360085 7408036981 7823016488 6960574470 3122190384 5409785559 8014597932 0220523127 3885210323 0605527183 4889037393 0376867225 5032764470 6293354369 6721238033 2363107298 2883205424 6835298884 8340027761 7245359839 5113838145 9226479763 8630203226 8512705800 4110754065 2823811403 0198795253 5348964208 9025784342 5090067725 0178079654 4941924214 1369507560 5552767532 0566952613 0019823358 9598361950 4897000375 3458394226 4731458382 7959059129 7483754452 4272911148 3608686484 5846477801 5660607554 7442878622 6509743149 1475354664 4025975185 4860275648 6303747975 8065056328 7940676013 3097629110 9682619571 5427957936 8424323414 9958703800 6811001268 5853132314 7422336114 5692546362 2819128989 2394907891 3056437965 7330079602 2559096669 0228331939 4966168947 0429577129 7795028394 9580496740 6940580855 3128897721 5451477038 9864896689 1261079025 1728522492 1379620462 0080832732 7048814895 8535044362 2824112022 3713906138 1137253788 0060872142 5628772516 0099207905 2625059106 6617716894 6475483918 9870996185 8899522337 8907445102 3811124227 2672901890 6359410934 3370540788 7369547545 8027375505 8960833691 1029552174 4872253428 9437586565 4884619653 8087733559 9817551622 4914523704 8800932952 4988833309 3928842702 0890637862 4941389382 6685483122 9608131124 8298508311 3004517304 4601380491 0230439876 8134820457 8474064909 7308340734 2045472434 9285436277 6159822666 9770923445 8155693706 7893663499 9998273976 7189469208 6903492235 1942973999 9958474076 4317826034 8311888427 2314523420 1151791852 1302129374 0378295433 1305606010 3310643555 2314380304 3233293814 7108134242 2762368725 8595410403 2864248839 1046974877 9965201086 1118924399 7018319088 2546699142 8812389151 7852283369 1117535012 6272366558 0815293910 5241512772 5638639993 8953981464 4389949517 6814058694 5043884245 3028170430 7603905676 6690242429 7258538026 3320042077 8284607111 7857332617 2570843260 4726594991 4599659711 2354123364 1037160502 5115813890 2339981948 9414958346 6018704506 9893776292 8913630224 9309733884 0837212912 6522165087
• c₂= 1 3649246294 8271309013 1272995814 3088920422 7827068901 5365116435 1373806840 9616712481 8475824301 9823006700 2630898639 9807617216 5659827718 5908669334 7057096619 5917411589 0049313919 2783187321 9755419716 7278625305 9699794079 2738130709 4044436647 3766309241 4745199868 8108529365 5575786693 1287552580 5936466255 9016598342 1048760367 6562260801 3462102193 6944016669 0504296132 2038129035 6089698892 9171875882 2696743256 8592979842 5479712469 8742538195 5400162068 9155627793 9923168716 5516830113 0994867241 1785398105 2640633002 1678253241 5993755906 8923646156 8156059629 3293164967 6112947527 6406904970 2559392035 1657374420 0207235939 2156246854 5879710155 1112299327 2480146264 6775139707 3640546228 0955698211 9219702613 8284014956 2981396398 2311975169 1267061177 5817838157 0194503741 3342195126 2782376625 2061102518 5652346105 1887250298 3513766463 5345618939 2130553369 7788872346 8161477629 6148640665 4580949565 7484806860 6640429630 8255831078 4585849107 2479497875 8510662500 1801018515 5780952283 2909792073 2476058942 1295981928 1825230364 7304644106 7125764684 4738459470 4904625823 9022284531 1743464117 7624654936 7970404102 9505363095 4011158898 1293224554 6924129213 0605568503 1677926399 4318634632 1174499060 9035930876 8114198082 8819137655 1651171573 6600842407 3349805376 1286258052 2921816289 3800301357 3360141629 2871167393 7170213704 9919505618 3697481571 8033213048 4310393541 0086087283 5168644983 2606247054 3285251621 3778960027 7912387893 1514142322 9482648578 6274329436 9996211716 3414634705 3946574960 0948977405 8849236464 0550566858 8728983222 6710400676 1790061924 5625220100 3803139372 5002582643 5708458973 2778107672 5873817543 8254418576 6073796051 8927781554 1679413307 0947867117 6517748319 3821384620 6385453115 5127494933 8979476670 1725899719 0704399871 3536090143 8959927026 2052479445 8999547031 5045198160 0817880995 4203944382 0363622605 0496725559 1245495336 2796054727 2163460564 4884319119 7263189098 0992452036 8714007735 1926207553 6566173889 8550542874 8127774853 0660335590 7498571677 0683013494 2859249600 1805321884 8170576241 7370986580 3983641544 9505119313 6113312197 7458674831 9818895168 3033869157 7652990875 1188814807 9710842760 3491240717 7923851734 4473944282 1921200071 7977542391 0139910243 3559658127 8153795797 8903124956 9240875165 7050148251 5267073744 8688447804 6070332865 6472855395 0083638649 6302029258 6738992826 1235833809 0893452235 7394901607 1029510554 5690176062 0754104993

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