Primality Certificate for (1809^2531-1)/1808

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 40.358285% 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.658281%

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₁= 45841 0863722228 3746227169 1243255752 0816656263 3519859161 6798991523 6312461395 4742956060 8592014366 4326811228 5197844216 1303667350 3962592474 4739968930 4175302978 2690600945 5580458470 7417133086 1335294511 8545055981 6318082858 9847921903 6675532550 2111900175 6814405583 8075229019 9436600654 3280221626 8816234826 8211083167 3286653220 2655334532 5558831870 2606883661 0356540768 2260357505 5124034082 8629305452 1180823238 2045877731 3259948619 4481286052 2286557923 9003442586 2792323020 6887600877 6723557894 0701149073 7557320139 7483848559 7323890746 8768489404 7877245248 0004775806 0248287303 7160675511 2192888123 3615961278 6347874988 4074551445 3926190984 5496552391 5917208834 6282870632 8724391842 6747139217 1621209308 3166616483 5854522960 1611073661 6327911580 0886653383 1631459979 0178013520 1155308385 1193861403 4126568599 5958019376 9704155848 0929887038 7791207734 2311073328 3835576353 1509482903 8930678383 8174074703 5320370274 3685006148 5329391101 5435974283 9715476785 8044030343 2018538871 1404431361 1987282882 2452710526 4418195563 0594246725 2017827394 0386985674 4080694057 0757977533 0966089488 8495660903 8287101820 1538065174 2949571816 7826315948 1687152062 5617256414 0598087201 6128075946 7550194998 5477506048 3943729280 0934065688 0413445505 0204789596 4209681890 3918694480 0423840355 0108039495 3889313977 0230991982 4307506254 9598372958
• c₂= 525060890 1620169397 3600475454 0314289100 6126670616 1524903186 2379907900 6453157916 8009608354 4706614986 0385706579 3072568465 3034955304 9522207528 3517595010 7641831446 8575725622 5684291074 3039369276 2634631338 8530259399 6918733343 2038570422 8555467288 5560350933 3020432017 4617316058 4749300432 4709005611 2560468325 8386907678 2002324791 5759537245 4805044038 2195308148 0229161634 9327362841 1716112926 1765901123 4724878087 4378087640 3308338330 9973892734 5161556884 9575145528 1543510144 2709189588 6216458626 3627320427 2726965082 0977538381 3396050814 4261107027 8234097591 6521846610 5098408629 6062595639 6758000077 3062372447 1967927262 1934935547 4017539011 7228128224 9810080542 6722241521 9181795223 6080965898 1656393562 1279395247 9897331305 6767931777 6862196243 2708176569 1618203648 5444794875 1145755219 4925048874 0955047014 2093407050 0400794303 0921707850 7110947670 2659349935 3827680567 3797036729 8916246889 2908749591 6650184696 1490522604 1308957435 4245350559 6368418787 7099241426 3513269203 1253613206 2120166221 0630988323 4073150748 0020099480 5181050402 1008436434 9162586300 1619329557 6031181492 7031210108 4726901288 7180257732 2598672071 5205611516 6675978389 7704371558 5692836012 6583915390 4873892236 8560300591 5118410270 7699483557 6234250935 4462325662 2680524715 9461736697 6926757183 1086537406 7609039008 0565979375 2218822343 0631130011 2667277384 6533743712 6288581826 7214461771 3557617498 2813675263 1605428480 6774665809 9408950841 3662009608 1174615008 6336354591 9102308245 6666275785 6055205106 0987412482 5661243986 6151559978 3932048641 1264732614 0849301501 4349967135 5999749381 5172482611 5010755315 2276547712 3554521243 5907873794 8938196108 1729388874 0005289339 2043538463 2782843434 1967892958 3339303119 1826137262 7106538435 5349567728 0956743411 0947670726 7828863991 9606852617 2154910350 3165906633 1331486335 9037932122 1210601360 1331623124 1959597944 1669788252 2159705042 3313417521 3487145777 2778324182 8268979774 0205972073 5911009398 8178069106 2991536479 0356353057 2167879134 5116075054 0643384229 9566637148 6641259873 7442137566 2770341482 1480286591 0491016311 1161315239 4037031977 3350113358 7887228018 2952821443 4881471840 3966703807 6394443700 6546413301 2493187186 0588112954 1296409596 7967523570 9594525728 6214226417 9656975215 1933747197 8461248052 9715503559 1298883970 1646208882 7030132527 4186671558 4935007235 6779641792 1038220139 9862539911 2017780554 3981347942 6436277710 4972164698 5621627314 1694913019 8862595801 9876613238 6213092398 2351111557 0480771745 5593703100 3546379298 3073562421 0690676660 8082855649 7287581152 1151924333 2081591569 9413464280 3369153892 5721140802 1097618601 7262486873 6499054485 8652011242 2588649694 1088792973 3129900178 9138354192

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