Primality Certificate for (9473^4969-1)/9472

This certificate uses a theorem of Coppersmith and Howgrave-Graham 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 25.609447% factorization of N-1:

We need the product F of all the prime factors from this partial factorization:

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) = 25.609447%

Factorizing N+1

We have the following 0.1068% factorization of N+1: 2 * 569 * 1567 * 3899941 * 180975869 * c19735

We need the product G of all the prime factors from this partial factorization: 1258606487768843644334.

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 = 713 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 three 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₁= 1097701005 4623213384 2136241252 6535996915 9502624514 0391972272 9489212966 7360284622 7240178300 8133619398 5816706269 4373517337 9779495006 7198013144 5162377546 5697311522 8531750423 1542986932 7325721273 3743952277 1020751609 7666778632 2723840428 1757676524 7879359871 4559554559 7923490373 2744516890 8691152644 2329584222 0553634092 1563595691 6662875968 5222810860 9891548865 2462860802 8098905998 9349458777 5028027822 5879923112 2017692292 6363829672 2011835482 4587693220 6038880459 2105833586 2562137315 7337524343 5935732166 4063666300 8938109194 5652540016 4110269841 3320975072 7897301792 8212287663 0263511525 0743713116 8374865302 7942459198 0496318466 9046268026 9997207850 8927961899 1702648168 8041657981 0165887854 7919561227 0388004914 7875466333 1988448488 6020149273 0415493355 8160378422 0805709660 8251782281 3757357704 5340590118 3691878685 5851193328 5176747459 0770469352 2068820607 1961033164 4739534878 2855355436 0534468097 6190541566 6822736262 9338451520 4798733907 1834607701 6406687060 1145990758 0558023870 1700938242 2715858979 4454821294 0060709733 3958758527 9474157657 7498617791 1890685687 0041324967 0144111615 2477385212 5048187314 4955824057 9918913688 3511650626 8672952222 7053119800 2495546158 4181784969 9200672401 1017853989 7292317756 2594388628 4728263531 9894260093 2721043646 8560542129 1678942277 8731859453 0462244759 7360832335 6889148580 6777184513 4852797191 4468146141 6698118830 9681062624 4497084043 6412148790 6671247627 2465104522 3270576208 3896252531 8675768729 1832297597 3745936340 9401198229 0367389789 9506951815 9649443514 0623344925 9604145718 4624162738 9199826209 0783983969 4681767175 4949790852 1184311988 3240892908 7656628757 0547713815 6554790442 3357590001 1013106738 5142297836 0563377698 8889804709 4858856669 5690693093 6042092370 3051039390 0672713055 5107372772 0643309949 4030602181 0415173802 6875200570 1974999798 1769014117 1680201632 7827704509 3183997502 2860184407 5507089477 1800282320 9360518959 2744140990 7431241057 5733116060 7413919348 4037024140 1605812538 3406939015 9470850096 0103904800 2775881102 0561351014 7787276362 9395852797 3585674836 4557893656 3425303459 3508635285 8461990658 9555131552 9052425568 6567222623 7549546464 9908743040 7826481791 8732760559 6206976763 4232543331 8320912680 9652393966 8352533854 7673337899 7240106323 7637304461 7221573508 6188797154 4300803139 5154620434 4747590056 1038160981 8256571944 8361527101 0009186954 5773100952 8593211342 8617596166 5267499636 0085152383 2268759223 0262401943 7873528279 3272053415 2031914847 0999866017 5542464094 7007912859 7538887658 2052900376 0680386801 3073563138 7031116680 3433103455 3429768138 6069859289 6383870245 6850778685 9093023416 3901311451 3901203652 5192256574 2118573816 0555759416 8823594334 7496912274 6389546914 5657280618 3977451971 0962584212 6510737286 4898816384 2369199614 3684079311 3175941646 3997696494 5847868103 0510923578 3886755167 2030204788 6831018039 4014263690 9312165867 1518013288 9144952615 0520010629 8366564982 1640497623 8431123592 0355604125 0383451722 6582570589 2179002602 2407348681 4226817594 5415545117 1172317223 6496404420 1438811325 6182310093 3243099278 8112079839 0165218125 8524183988 8327578461 9506393490 4249545006 1165546360 1885578445 0828163270 3554805121 8772307473 5331978638 4790836463 7457064619 3444791359 8253286741 8717337513 3586120662 5350015230 0942670372 2741302399 6078766736 3335122717 2351227381 7252261311 5995669449 3047685933 5324956175 1252497628 6586209859 5494621259 9058082420 4659478110 1636411645 1319851415 8591406359 9340795107 6658253562 3320056627 1914509817 4524661543 5474873404 9175163257 6221299902 0700415405 8510628912 4070139163 4276480018 6825231808 2017690084 2289506483 2535924841 0022809409 1333161196 5575399478 7699570299 8679633769 3266387106 0766828437 9943339545 5305604499 3427408652 7374728317 7226287864 4746960609 4092644481 5934737774 1240916530 9452076225 6266148836 1135219109 8580947434 8024501122 9879913821 0737107843 5638139082 6915074460 3713194329 2601902916 4931041220 9288944128 1489367459 3421829136 9526638692 1157079596 8251734742 6106146990 0845130820 5614985298 1901373574 9163815625 7976281122 0459905028 8352167323 6608359286 9912881174 5614358576 3347755570 0166419209 9339078735 5384064650 1299939062 8238414448 7497443770 2737641918 3815855990 5830119063 9628857218 7057983834 9101278646 4059436856 1596747100 0050557379 4991692079 1941797479 1974530814 6449405134 8179139840 1604805823 7506620910 3281645479 5856770475 1712525839 4745076364 6412731824 3169274918 4316542022 9054151512 6128739411 5541019730 8287574856 3000827932 2660119485 0771114807 3806426528 8864213010 7641138210 3599259430 4119866077 8908065699 4380562597 4471389016 2478420311 0443096802 7994681615 5664663487 9555075988 4185689382 3861549761 6884614224 4024394353 9317317133 0078462021 4891576172 8086027176 4894933790 3229646196 8453266795 6981348242 6273659341 9047894173 2050257373 2670227365 6003621437 8852331527 2791040795 0905137307 3046375495 3657949026 3628358760 8307229492 9689154100 0509061645 2866621741 5338841837 9848472213 4726533922 3262784304 4721669340 0803355533 8388764588 9424465997 2312569285 0673951265 2264238514 0788612097 4594202848 1655757065 7330603361 2964393960 6596931883 6568489353 0768053039 0805929451 8336086048 5328016760 9396664384 5493954739 5176095895 0682264362 4208069128 6957993682 0864538441 6895620188 3069080865 5050149027 1048763995 4565760662 6974952026 8307562299 0540184429 2486326218 0937106627 4664044091 8213787795 4705524070 3644381391
• c₂= 6312112 8437182116 8524040832 7209494454 8815470700 9788843167 2860499837 0152476202 2438509638 7859674514 2693138349 4752811358 3739005267 4198677547 9435776807 8699412141 4539987178 0625108430 9773694294 8519251542 7070093871 1348469103 0518318090 2861490335 0438866696 5436638668 7212209239 2082085515 9875707078 5135882110 6958380741 7304407443 4388288258 9681312779 3380306998 8843339453 0150346584 8527692365 2435862792 6215152563 3035878915 7020218690 1985916242 7443805614 5845905321 4258642555 4156515995 3281599016 5325286425 9756500814 3326797572 0794481679 6161032412 9586752490 3930568942 5924245351 8295830714 2492381005 1972626981 4855000576 5823142413 6646761243 3250279596 4070222185 2800530976 0009684494 8208460667 2844094873 4249873965 4414534882 2638482020 4630389925 2049170554 0071604119 8980833362 9191251919 9079430813 5285219162 6185586233 6618706038 4964099895 5264241915 3112634640 0805491865 7803900213 8583824095 3601066357 2199413614 6736868591 2937144026 9715663254 9320883790 3583576885 8531363251 3034768129 1010848921 3905576903 8929690459 1087714884 8239947089 7006826038 5734922239 0689885839 8189125339 4312265792 2691846294 1931597074 5426492408 2512740302 7326338550 2058259562 4513630477 3726085098 5480454688 8845737214 7873803222 7328459414 0938905957 3264218181 6824650481 7561392750 2521583078 9042465727 7104323144 5964428314 7164772630 2921579072 6001496981 3374729471 1548285229 5547996608 2280687293 4316589856 7806672027 2590804542 8551684302 1981962505 4907099971 5740582416 5104936974 9354597607 4784011876 9946253618 3409147373 6206852340 0767110358 1354346313 4769969520 5999779152 2253101386 4872357781 9066153471 6769882113 0207154846 0904825206 1262803546 1440809009 5813019630 4199663766 4652725545 6414012672 5876356874 3616001805 4296461482 2043045990 7595313817 3087356003 5492770867 0426857090 8813432958 5282283812 7095575400 2253315002 9683178047 2064737789 7240304699 4378175667 1832069817 6841839087 8497804620 6849117481 8087921456 7718393097 8237229526 1555004813 6619968889 5621397601 3100296196 6956153975 0871995383 9430732484 1973945410 3410101879 2100239689 5248051517 3872519946 8050419524 5608097414 1446823204 4119309798 1977830163 7607334236 0026848942 2904423808 3166136320 6769007013 8247908573 9483467487 6211645524 3909435596 2583866861 2265535178 7044887398 6305211370 1718966845 3225634511 0651178351 4013324980 7785379134 7705112068 3558919391 0737474068 5356109155 0028295583 5791299996 4933546275 6523643527 1287542237 0839212133 5614858251 5521672611 8613794087 9583624098 5907703916 0867209097 0835595036 2438901223 0997690155 5392822417 4573659294 1936665637 8151478006 0745804776 5615735039 3180985030 0563480340 1135190201 9247008444 4699429711 6527000365 3245080054 7146072061 0157947125 4955715468 0777806569 9891107515 9666989681 7498800338 3673868939 5957361251 7550580240 3819886644 5220786057 3395398487 0690287078 8111185792 9985918401 6799597166 7227394125 1743408179 1185861364 8528489810 7043432095 5477504834 0405123592 8534778238 3168550740 3809280882 0488485148 7624310876 5579712229 6358873724 2931095437 9219066711 3102130910 4778233991 5788777957 2753356838 3462591882 5429954491 8754278812 6892042876 1184032644 2301103884 6785214156 7597724005 5923427452 3259388576 1917946733 4785919084 8564047251 9509045397 1273430450 8181809741 1485487045 9506520296 6822612607 9086181619 1169371248 7091919777 2739374557 4788462634 9888982764 2034025606 8722197341 5332303213 0540779413 5606469283 3983025633 1657173139 0231432853 8142387609 7890831483 6244697049 1839915468 1484316352 7061052796 3850329790 4283666600 0267821881 2880483192 9177425997 8947541790 9502582072 3368263736 3824548275 0845499913 1325916767 5731174468 7319692462 9128150428 0675718915 6344539320 0441865595 2384459447 0854276554 3372686766 1536669022 7930995205 2878835189 3605024753 4851577062 2494546139 5083153683 0755718018 1750143382 5390977786 5854372964 5041377114 7308655174 4316959083 7471102277 3398716572 0234622182 0764771065 6628533508 1059703695 1385694652 1047801552 1164615412 7314623149 0450709857 9972335292 0980736865 0585417002 8230710163 3065112941 3236027332 4609087566 3537779976 2637607426 0991058336 0799642153 9375498240 0255340088 5071952749 6069809858 8326730017 0174717714 4107626675 7310170733 3314616166 0279768137 3800796245 7357591053 1958533848 9550825768 5995005560 0559360245 5513082917 8472728260 3626481704 2370479925 2126103812 7835322816 4147650914 8956799446 3663209899 3477048051 3970849984 1904223467 3978892398 2632738167 0853692348 6234842892 6060886850 5437380619 9324679620 4355961839 1126679545 6903330234 6081109264 3866113278 4104970499 0637681777 6574074677 2753221287 9853684412 9241103739 8163909830 7972612433 9032885454 3008026037 7597117023 4416115863 3327847064 5247005869 4374113552 5177968860 8403251640 3181438450 3054039436 5767683466 5151956245 6684427324 2218018374 1678653214 1789796841 6780605430 6590081152 7745395319 9021011324 9044611712 8472097191 2962957693 5330194723 7299327257 8356921919 1056805596 6193463587 6907164003 5814540679 8686749401 7778382237 1542325176 5926600364 7488244456 9805054930 6318413620 4560737086 2660718327 4040327086 9676685612 1646364764 0307763394 4364780424 3702472583 6316082982 6377647465 6306245784 4065105596 1989863416 0960997960 0586084931 5682449314 4423563037 7143818610 3628795907 4468806162 4101130519 3978702722 6483676411 4678325963 2389596685 3110251800 3358800584 7207558912 0404799191 9210272801 3408741685 5096299007 1344365854 7176884216 4099204125 3963702198 5575432077 9044022095 9049410395 9958516713 4306808739 1041367098 0075384864 1678316494 4471013384 7186111829 8831593817 3054395987 7295860690 4528258775 5148958355 4042735858 7894665028 5986687382 4917464443 1397979575 8480438191 2252519694 7837086551 1606954110 8519190324 7896598534 6157380379 7638732226 3640953478 7206133972 8657158184 9536087957 0955612224 0247421800 0189606123 0955838862 6488796948 0140099575 7447737380 0270963688 2378597877 8677916446 2342744786 8035031846 2738826225 4406381518 1059276420 5043881067 0720420077 3669990217 3840099112 0918114374 4912942656 3695212075 1424187042 6604152860 9014644229 8777449820 4148124637 2565755775 6167855166 5374053891 4633644186 9260745723 2386291952 3004452611 4092111954 1914432678 5745458317 5610834984 9177613123 2189051189 0548350360 4332449549 8832566600 9853718390 7597277779 0501346672 3202766653 3516871592 3552373179 5439113822 7417323147 4813862720 4447645989 7717977506 4955169564 5543750961 3474274338 6652128197 1486712313 0236864195 8113471461 3441696597 1029407246 5638231959 0164022967 1458686445 4276250484 0420262248 4251618796 3341005235 1581555253 9997418417 1709021078 5351389355 7127093740 1733598352 6818778090 7093861150 0926055674 5765508261 4514595959 8019151317 8016778035 0487725966 3666989386 5534100483 4674697818 6642147029 5568804939 8469044571 1618164350 8938614634 0500774341 5015115821 2446837714 6092470962 2699498467 9688201203 2749966882 0112400478 1909861381 9582387101 0401954173 7335432869 7199004568 6304723509 3776949117 7533780976 6362613026 4255175171 2469921219 7280105492 7336532419 9247624978 3320881943 7206336717 5976369400 2076917399 3307133757 7933716481 9354021768 4691051107 3011352657 3812614842 3067849887 9657712221 4313590829 6589928328 8593802993 8827890766 8121223919 8382980440 3139159396 4208141792 5389708837 2498372551 1127061869 8383630413 7839769382 2319425913 4328854548 9661098084 9916930049 4638863373 2805779363 5635221967 8480368220 6756603945 7391011508 3595488459 0748468902 9622824727 5112730597 7077537964 9315899586 5274151947 6401235184 2639711453 0983481052 9619141390 4147741830 2250020357 2054328389 5539563531 8825878347 3018619813 4202002546 6585215950 8561122071 5073311640 9868503666 0657327527 4792136164 2482384992 7668092446 9857764396 3221331256 1657194774 5577594676 4759124586 6194442734 4958243360 3828844015 4263110150 6239953250 4737554302 8319924172 5625888230 9236280516 9262579285 5212427574 7183330082 5595694155 0240199969 8781603073 1264431875 0670628109 0966391491 0908228253 1652523957 4434931338 2999328043 4322419258 3592357752 1808848168 0775007046 3679338691 6842972155 4859074645 3307294261 5934095010 2929941224 5224339295 7312925942 4135318017 7168017386 1318435453 1547781145 6065558456 7320433821 1612201081 9222190317 2399718929 8322191298 1448542000 2603784616 8526234129 9342050076 0013423851 5723388382 0424311768 1865350689 2616468466 6702624458 5373766844 8534074840 1041140786 9426510349 2926569304 9959322683 7906461902 7912882834 6677242808 8968808037 6096267782 8848064902 3907018946 8622727952 2349536507 7876553024 4205285540 9859858092 6472997485 1862204677 4346182503 3194782958 2337677948 8497220824 8342553366 1237239164 0940117219 0152053115 4271215663 8918400059 7688552150 9944412964 1483061211 9802578163 3739776528 3787204827 4225342752 7238540758 7665498661 4586776579 9393147689 8523827102 3738459056 6436934944 3653979926 1251786824 6934712167 9287420573 5994404869 2298450814 4990738938 4825524363 7356313089 5183647031 6207608518 4017614937 7851149665 8340392968 4226852456 9988877018 2698856560 4379268322 4339110352 9626619876 7275253069 9427273940 4120936333 0248011106 6514644560 8643156401 4072308072 0561940272 9450774328 3409865425 9892489727 2699947107 3331025936 5868269358 1635183577 4421651953 0759599047 4898866083 5923208268 7379719630 5423672838 6679680689 4634574689 1981672269 7419292488 6894330525 7129135379 6448204244 0659482966 2536012946 6223216020 8738840858 9972895651 7737568328 8143438051 1847693980 6670960174 6668545922 6907420458 8056252453 4557192455 6654917646 3907866789 6381701918 2809362099 7110625376 8969613163 0181553031 0293299471 6922674451 0424658496 5656814096 3622584961 3178600852 7882672157 1909219572 3947742025 1268484198 8887909017 9308494390 5349977513 2197374315 8495839106 8958041944 2738964213 5843471501 9061882633 1865580167 8200126764 0514251029 9968254457 2526316969 9701187388 8240181953 6805185256 0531374246 9624922121 4393059036 9224498553 9816115384 7999932450 9248858675 5727031988 0564155744 9755013554 3529275749 0020929963 5259096497 8974916861 9515550995 1715880349 3528701782 9231141558 9904812900 5397347170 2947877796 2699805466 2903230164 8713803649 4184255413 8231489329 8208141014 8521859341 0132136106 1377943441 9914547856 9974648180 2653958145 6470712905 6652683305 0212950684 2580456541 8951005883 8402894288 1680753880 0421912767 0532225711 4657934212 3245944533 2228739577 8700371687 5299914986 9868366061 2600674926 8585769036 5640863005 5613751011 3105917630 1883219260

Brillhart, Lehmer and Selfridge

Brillhart, Lehmer and Selfridge's Theorem shows that N has exactly two prime factors if and only if c₁²-4·c₂ is a perfect square.

Here, c₁²-4·c₂ is ≡ 42 (mod 63) and therefore cannot be a square and this stage of the proof is passed.

Coppersmith and Howgrave-Graham

We are left with two possibilities for N: either it has exactly three prime factors or it is prime. The non-existence of exactly three factors is demonstrated by the Theorem of Coppersmith and Howgrave-Graham, here performed by a Pari/GP script written by John Renze and David Broadhurst. The output certificate has been PKZIPped into this file.