Primality Certificate for (3198^3727-1)/3197

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 36.447425% 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.548037%

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.

Given such a witness, Pocklington's Theorem shows that every prime factor of N ≡ 1 (mod F). As F²>N, N can have no more than two prime factors.

Express N in base F

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

• c₁= 3 7803473737 9895959463 6148180424 7404305354 2411474396 8222815487 2341539003 0155466872 1508457473 6873027046 8178906618 3984288238 2732388828 6885838051 3135822633 7043697357 7434436119 1910967701 7652381426 1760082073 4868249764 0732843943 0789242860 3936757826 6853415126 9588041714 1058171552 9300400578 4539487808 8445998019 9508139106 7582073698 4149355621 4365430248 3343826292 2683646515 4720867578 6545104241 4791321823 3173752958 8195935413 5770342723 6195765118 1177290842 1014357465 8791850557 5849563992 1479025768 6557308229 2955309266 1562868668 5822538287 5081501362 6859939032 2096875052 3598905730 5256600755 3901533545 0370001740 9391168559 1127283595 9951719077 4553738565 5482642008 2617738463 4607913013 7956792876 9908899564 9003179237 9187775091 3032775530 0237163281 9088859664 9668518766 2834617058 3038910740 4172008481 6010391811 4812543991 5788592857 5581036131 9910523582 3250899484 7564656233 3052595390 6698025868 0145143772 6556066322 7416847911 1884646513 4660802072 7118342017 2023734998 1377615749 2598830936 9713125457 2851160731 8218131985 6643233431 3249116261 8288571961 2284575183 4216002736 9823440161 6154741553 6651394877 4367586460 1216709810 3263425737 4033673855 2194706969 4994861302 7380391222 8446132498 4503047053 4884360508 4094301767 1969414006 9269021090 7275113334 3983152567 6311846807 0893329742 6289557113 7103582682 0930400487 6614779501 8799736441 0524129529 5448566328 2030888303 9872930796 3758120034 2632469424 1581872119 5961545123 4382086469 0437233439 6555768901 9459691260 2924579797 7198127098 5418390312 8289428156 0255368313 3902904732 3071498460 9319004325 9771268472 5705494494 1668594109 0905286835 7117491002 2199286715 3751256992 5298559586 9658339320 3379155007 6404470054 4505915357 5576629175 3758353278 8658026554 8608551403 6947647320 5460357667 5805158195 9217557948 3770799320 0505945888 3762260308 5254558872 7302533609 1825921507 0968485907 2511901417 4080209256 2957376964 6690108070 2731340886 7272990581 0792456183 4139803245 3586725406 7820840852 0019386453 9746808443 2821642195 9571365994 0241557917 3882977938 3836681639 2825729159 0217901253 7934379491 6145452813 2397317952 9156190374 8214770771 8678542744 2600751712 8242290451 5315331543 0282533350 1671723233 2580477922 2372477611 9280551820 0229797860 4007727251 9841740042 1066053710 2352138503 3622438536 1071274407 2630535738 3318463764 8213620066 3539395046 2225086244 9297172217 1847938232 7627039387 2433750290 6757361752 6049654093 9415900414 5672677148 0407766971 5900565378 3287208055 3544867687 3463883820 9903283052 4279247401 2686676781 5593427906 3089051108 6102826573 3692730156 4019178972 7835629914 8236429719 8112497082 2023639484 0288399677 1586592563 0461530763 3541381341 3762624972 6836236568 6054659731 7999042648 1908962583 5042362779 7005994301 3554986862 5163428288 4446113636 9867376558 8729409702 1520263106 0938646333 5026768247 9653285982 0410372137 8211143524 4405381031 2085231952 1393461428 2280451249 1441447530 4977369744 7924492002 8595559927 1173276364 3892184657 4591608657 7267764449 2636095934 9945179572 9630730383 8396127850 8095535915 9971509315 7471437319 4191508151 5681733906 1403488009 8888386446 2692857852 8330111047 4534128254 1230580299 6327303493 7476338645 3175575967 0844323439 8333242798 2936003957 0092454555 3084549120 8411420408 2685072442 1621146292 1266503019 1369960650 5768120784 4671698973 7283037567 9028838575 3969200452 7066141955 5719405389 7804914132 0748729212 6563271286 0750596405 1940890294 9330604249 6821079306 3722241850 7994959759 8478505422 3049865409 5651580386 1317202531 4449683802 9863399224 7993277455 0855115955 6741647930 9714792725 0361422840 1647925432 1890280047 6115244008 1120676891 3824929975 9907378980 0066082357 3678757408 4297642124 4800467377 4559263294 1452334873 4254835489 7850694304 4772922303 1047735234 7591019926 2661525615 9184722060 3955668645 8521583981 1531414443 9723703519 2203121424 5653677873 1235178381 2501528589 7995245573 5201559542 2844338013 3180191898 2179948645 3297374570 2360362893 1333897065 5444461933 0894321871 6996045428 5803243376 8665635408 1910213695 9453639833 1465648746 7209520279 4160005164 4042742512 1090028292 3354462559 4223672057 6268849896 4748639606 5380429641 4961057967 5259736078 1518185633 8380034923 5763196967 4963810621 5786652664 4537385889 7184763205 9085564062 6229404495 7073681004 6122897877 8440848450 8325735401 2353138071 8894565825 2739679899 7859707527 7779940214 3963657862 9447364901 5849076339 0164668372 1927538006 3206036851 8626088269 1739117665 2530214113 7067345821 9125549234 5112893750 7263399890 2682638831 8346296895 7785644476 0650550359 5177020591 2183833162 7695240967 9333882047 0928479250 9887252672 8158805885 1147607977 5794692985 2064749018 4691279153 6802040387 9439643054 6737098202 6349373788
• c₂= 9595969 3221005976 6046488101 8123598438 9258487039 0994064970 6508656518 7574377852 8398624844 5913910312 5403009231 2233427050 7504155949 7898153489 0370177650 2183223031 4093850744 5403357030 5584292896 6429851424 6605768230 9310857324 3491596070 7198140200 6066555202 3869584181 6771290244 6595500896 8167721208 9110642901 1421439010 7220555790 0351265277 4824557495 2516715416 9575847670 8698837107 1117722420 8860430489 4166872723 2632539691 4164481851 7267009579 9892361559 5289350676 7616404260 6918801957 7978140634 3295718591 8838566389 8465477607 1359083727 4495801193 0743548206 5285832149 0866357979 6113395931 2213335626 8769133396 4834105575 0224733938 4106295893 0799493044 3975899341 3487545202 0531714431 6647254891 3985394827 9851364213 1648033328 2125616164 9419005159 2231813270 2580328801 9437251010 0266526844 5733717027 6731121113 6791351790 9361337385 2260733675 9240824764 5569726582 6953089894 0800896458 6016026761 7611930859 9915740746 2186934746 1345635080 3448425476 9087030807 8235182155 4737779349 1865444327 3275141635 1150213518 2935409735 5636157617 9654312596 6488099631 1206660417 5968511074 2420958813 3803223094 7693656531 6693547690 3898626393 8362948400 8245773498 1155495499 5325994871 2586445449 1840201604 9309981053 6253405490 6467344490 9211777479 7136613279 5656043348 5422536451 6475025005 3863935676 1865200516 4448548564 8261624087 3188354237 7738504872 3595611725 6920991601 4729290539 5208784576 5407206481 7043792378 7977484705 8942232806 7540289771 9963689628 7265434444 5245656824 7258580246 5816995446 4480637625 3235095872 3349733719 6385004920 8842197323 7777761287 1977411238 4805491272 8511518584 0604471950 9952771417 7555570712 9934784692 3010355835 0011193930 1645528310 1473412754 1827441832 0949024947 1860795567 1503348760 1175682938 8487169321 0659911906 0674207416 2122947979 1904926091 5842612489 5394374979 3490614899 5604610172 5379155266 0989985566 1349532547 1196332632 1505885022 2366937137 6166915578 5984083738 7578721915 9049784615 5473763169 6099938388 0628837693 0904670001 9316151986 8773166577 7862671977 9628521596 7962190694 4144790060 7780855694 6276855693 5423971871 0352964487 3660129453 6848687767 2633329510 8658579550 1444408801 9962542809 1101500304 5116526197 3264733680 1110706909 4081326924 8397392538 4258209435 8082723604 0532420716 4594257174 5650564652 5049815180 8652626923 5111001769 2176367943 3438866439 6814618966 6678804896 7672727131 5371508302 1351817764 9339911185 3012192667 3783606974 9176896450 8997672939 3006272355 4681298217 9902294108 6109366184 2903868926 5382675391 8912078326 7462410066 8407285718 1366247826 4256718692 2414192047 4953799383 8539942956 1803311186 5573669566 8180536009 9509272282 3844614039 2420774070 8605957496 5169548174 7910053620 7267643255 3060743366 2458321895 4611216323 8408922858 1004958546 9225925849 0114619778 2248852129 8678649229 4541921373 7870947343 3141598280 6583790585 7992187525 1389991346 0692141655 8595104647 0687483713 6322345345 5707341531 4653242046 1729246647 8755654560 8628945764 3418440843 1223972081 0433468986 8373263641 3172646070 8892268957 6180298098 0291371951 1817286836 3326975188 1198967575 8297878395 8429272004 1072128773 4954874481 4239131299 8551992719 0460557022 8455166591 9074936022 3300063512 0301453447 0601639721 3746298163 9436301781 1477052181 1151331233 5037798701 6966044464 1838415587 7776052427 7125217657 9164265005 5175768312 8506226118 7023361885 5585278954 4678891354 5657253426 7616048318 3527436255 2327017754 6939728278 7353417761 8747690351 8122864640 7793563774 5387750577 2028236435 6668803183 6052062289 4870599314 3706697334 9897957267 1481040555 0123034033 6734858543 1868436018 2165819831 9258516479 0612603268 5741904511 6290213778 9983919569 2081231645 4891052004 8197471849 1810139897 2595610222 4403411210 0786808687 2895094457 8166843057 0390916740 8341268147 2308145862 3353616137 5638084593 2883776571 8045815570 1469462548 3831702810 6502478247 4087233557 5190778272 0408355810 2126573888 5744546218 5853607754 5246035524 8594633379 0260745626 9785366447 1833378897 5685128783 8068973550 1843431473 1387070664 8679893443 7104249997 5527427078 6027405743 2081628231 3492960289 6477420898 1474838407 9151814006 3717697493 8168972922 9052432197 3623905265 1671994805 1082873328 8205116987 8300279824 7270551740 3727903793 6055567347 5956077875 9546216771 0372643916 1123559607 5155436034 7584592774 2428895770 3818114987 8954857117 4316747933 4916941626 1331883200 2512224275 7245576122 1589322566 7548121763 1589607889 8149955894 1397813377 6738734914 1904827013 3845565452 8194199949 3613179877 0494102376 6735231418 7022422406 9379598445 0055628754 0715853378 3495557921 2419806678 7594450533 2488754765 8232050574

Brillhart, Lehmer and Selfridge

Brillhart, Lehmer and Selfridge's Theorem shows that N is prime if and only if c₁²-4·c₂ is not a square (given 2F³ > N).

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