Primality Certificate for (9572^2381-1)/9571

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 44.014469% 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) = 34.660074%

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₁= 5324 1808723786 3641196835 1457113278 9367447228 3784988048 2027861530 1779637701 4682453248 8824845426 1006148682 9479997607 1580414979 1129293245 8478665992 0507767315 1328145700 7948183473 8847238548 6831569906 4098933221 7580505588 2220094308 7093986536 9113600486 2249923600 3287455708 5987247840 8457085932 6080691162 9519750061 4539070309 9702489546 3692134233 9310906627 8862127660 7295324825 3353590983 9778166827 4471756571 7463370251 2453711056 6243605675 3527637516 0489509906 5938094766 4922347342 5271727165 8884613647 2736070396 5430594846 9375601888 1101366856 7156043639 0623271348 0145945909 4688515869 9019163845 1604865862 8875398290 2575774610 7319688397 1258528909 1974302670 9030463933 7038493810 7795818416 0615765760 3960505922 0455686102 9281436293 6479359907 6448552565 9261339814 4382589002 0245687142 3923075882 2693561531 7281492134 6058774514 7152125298 3325019965 6422381833 1998293088 6874013994 4540502773 7842890040 2713896601 3710075490 8612401523 1096685076 8984551546 8951870730 9471434546 1566554765 8689357392 1505361905 5221818084 1871034987 4133237800 4537216116 5627247403 7309073614 0294781709 2131939102 0371159991 7405082667 9491415516 3188628417 0041093487 8482339415 3128739411 3858001762 2548581663 5432611009 0041813662 4296645582 7638292820 6954477296 2922207973 9001898471 8341186515 6999628058 6783875586 2070072135 0858702448 0549049827 4609279782 4601823611 6031758050 9743652160 8036373502 4567380513 5143319977 1985896916 5251991223 5257459517 0727732389 2810945783 3158097266 8455999386 7852282595 2555486746 8965185953 7485574014 6327865592
• c₂= 7085985 1304955100 7983843635 5925004921 3417888868 5808986040 4677399127 0088883722 0357034116 0959900096 4935283535 2072723472 7617956973 8261588223 9035293454 7301145561 7591366390 2716474513 7541924949 6543355431 5499873333 0469783742 9421323236 6440870411 9995856670 2130958532 4521904895 6773933626 3441704738 6617021410 4669971256 2580727427 5236420100 1575700733 6865146731 4207875687 1815685767 0944439855 2587201315 2199466149 2772562186 4472461838 2749706249 0258726252 2672846236 8280886341 7667383734 7397453574 9961991883 4019757804 1943999348 7600210176 9288509077 9072911918 8307356088 9089693644 8775646738 6118300906 7920801193 5067789869 2974269112 4073648852 6887824466 6587907988 1522285238 9818506921 5806878928 2087661277 4018561196 6760811630 5679938150 8567183635 9497746930 3654178759 2266567819 2362941543 6023524910 7824808007 1477422376 6873560114 6865004682 2434564176 3884572258 3405667081 2132995691 0435323233 2081555228 0422388607 5722475704 0776680872 5813548434 7432390948 3000680272 6470796526 0253500396 6700222840 1205818160 9968534101 7271215445 1874351325 3069991652 2830755736 6273979706 0352167770 3177738304 6332432810 6955993539 1056862281 1416181924 7171385432 6633113171 0504863927 5906027268 8543318561 1208102216 0760045259 7152041581 4536050934 0719729225 3680895886 6126489949 5811748027 4158706920 6310295324 2647894206 2213528718 8786688304 8434639169 6844066563 5210683541 2875145916 2335733939 7711360777 5737982767 0519629824 8382688901 0572574688 2711492924 8298591752 0190356569 8803644323 2334231124 8420506671 7228154055 5531808725 1322084400 9853804133 4743347368 7054914387 6932421481 4438904430 7179401804 6925988140 6689060355 6141354052 0534721838 9555018414 5031517414 6768006517 8388064533 9523317285 9530953372 5836799211 3251826390 2507662872 0766597594 8522245782 0684673275 5293741336 0452297990 6543130178 7127458747 5802286457 6853205136 0907126002 0823450227 4016248050 0892503648 2822920411 9424716763 1005074679 0409165135 3136090149 5140724145 4401481010 7794863230 2788622554 9669582664 1430181258 6056541812 3408826355 5106641935 0100604928 1944028372 4375415641 1723910265 9067157992 1264216550 1244870196 0275687965 0772289467 8454600433 6968556852 3698986359 7673441114 2909119514 6640171508 5366650590 2461568938 9408867384 9073323578 2909060467 6787110157 4891971146 1023209603 8261209636 6988349001 2259787572 8329120748 1191908681 7361463746 8160230879 2733191963 6842389276 6369835907 9128952416 0595420190 0121061537 5206239559 8984823590 7800362237 9988469662 2327656600 1807370625 8125034157 8144706462 7437640445 2306357893 7947865631 2939059840 6595745604 3046953314 5715847518 6871174859 5690199884 3171153478 0592859232 0056880947 8142085674 5645464280 4878477048 0688319734 8422700718 5573202462 3559429752 6829852594 3576939217 5020475693 1448953624 8847764122 0020501650 7183842987 8479297362 4582309690 6452669609 9848751056 6052378327 3303335526 0507523515 8818738807 5413675018 1604400716 8813076033 6411105314 2413932004 4132241785 3174199158 6064027106 7433006713 8517051068 5771736925 3438917457 8476537652 3548576754 3608714759 0237641554 5694872975 5058936352 6145680671 8163920684 7247335788

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