Primality Certificate for (6848^3671-1)/6847

Andy Steward14,077 digits29 September 2008
Originally by A.A.D.Steward 2008

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.395266% factorization of N-1:

From Factorisation
68482 · 2 · 2 · 2 · 2 · 2 · 107
Φ23 · 3 · 761
Φ5311 · 4651 · 1520588501
Φ1011 · 199893608035171
Φ3672203 · 6607 · 16883 · 222863687 · c1385
Φ734140929 · c1399
Φ183554785761 · c5608
Φ36703671 · p5612

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 :

50 1893387213 2357776559 1489456500 3747279535 0964736441 0359181714 5023408594 0301962577 6639831991 9874183885 3591980637 7152667296 8076614930 5021656555 7715163288 7262567032 4472092330 7264472641 2735160886 9973377270 9594717257 7484036692 5415507059 5904620863 3736129258 4605835243 1652628609 3477667166 1124191691 4565044934 6224263339 1787287891 6954559639 6472150344 8892136260 9241289759 4574514388 9438479230 9855119772 2482725881 6070365022 6303218791 7324581744 1113409781 6516823082 6324227799 3491507959 1984034837 1446804402 9462164381 7100450133 1090141402 0656395800 4408763159 6281845334 7902551047 9047804363 4993012675 5436288860 1253134203 1358651828 8372902823 7948133318 0238923619 3267117415 8213566157 6332071052 5951703070 4861885798 5104201930 4305639835 0434573470 8006201282 2765771028 1050849346 1248458792 2231719799 0487637977 5986929902 7669521156 7104794875 0459027167 5086813462 8621506586 8097151007 4850891567 7706962614 4626420293 6480709708 7771928366 0737400314 1943403129 2037153997 7255846740 3195618550 8803517657 9156157758 2226294572 5857284958 0201486076 5208472521 2523928935 8221668073 7134138548 4803477721 2698389938 8281011136 3601532573 1044604588 5868708333 2837325300 2295779609 5960298252 3812890408 6048274607 4843597633 4731920116 4438734400 6015123285 3654648433 0981241351 5955680069 8255544476 5238472802 2381692931 1988957401 3172423881 9015453165 3015963196 9825404606 6817600699 6329164125 1565133153 3242928854 9157089203 2456564641 1603960382 0769075520 8993194174 9014498768 0612889029 6505756601 0387590442 0307876665 8984176111 6714067728 0019551543 9728539921 8937389490 0454291353 1897802721 7201503948 1822918726 7872448345 6469802787 4783614192 5357455597 9712854843 8902878879 8029492503 1259196470 9467051692 2024122283 2858407291 3263104383 3826465632 7606803755 8947911468 3433421829 1737189475 3943984341 9856830205 7700312542 2126615902 9840224708 2388597883 9127441962 1312514548 6718197565 0031319723 0527310415 1887311353 8508778883 5804329415 8668098447 4903363568 9299545348 3751617787 3901069605 5987028153 3055676539 5870681628 2793940435 3944758289 4404387568 8500602326 5989376829 8795015411 8221986333 3079058566 7425445664 0977341275 4748775660 1404187249 4976733836 4556828300 5873291558 3844297255 3141665128 3866910105 4832516158 5088907138 4225916403 8818002300 8428461885 4641450581 4714769181 9070551509 6867651024 3330067248 3726929973 9372444338 0320126419 4605800400 4707211052 8487477254 0194278641 7400224729 6011656687 8050824167 3253869162 6502717417 3475222717 6703743979 7421227430 9191713419 6482856420 1376418438 8724039052 5359811112 8219843862 0614115318 8441373123 6503011506 5326020061 7061364929 2596394568 3023524384 7329732756 4852033431 9790408780 8397595816 4127744331 2971670614 3248944786 9595057902 1469320974 9398430757 2509581120 1505611083 4144377302 6542359260 6010268223 6358373276 4040239872 4290952378 6544348644 9446050752 0465952592 4484248733 5061099957 7024948322 2882136006 3107966109 0041602410 3212858513 7190108095 6510545505 5239811714 1121774039 9898414985 5687749551 1447996614 6778507353 4092586616 3002763418 8722368043 1863056019 2316630205 1978998200 2815281337 8808556702 4507624352 2226576386 5542210556 0137820130 9911387736 6003309409 4926951061 5157990105 2856061425 9239521131 0700846584 5751394003 7261644484 4793731945 1674703492 2847538546 7489851071 4395089233 4288361977 9453016640 7865022203 6561623939 7087699672 5248720371 0247738287 8405949620 7428246043 5870110760 6659996159 8619292550 8740506802 2671380213 1093841033 7381345169 4566706439 1682538547 1976802411 3440489067 4517038294 0995761744 1969530278 2186790705 3523780129 6999937026 9449715931 3112033506 3000847144 0482373988 0671859938 4726734454 7407072035 7662911178 6041442492 3298593528 5857310469 1609025495 3119421280 4953401382 6383709932 0127179952 3053614834 6091420962 0170733953 5590332853 8296679964 1190001164 3976264399 1421686415 1585150264 1201863676 8303013427 1362095313 9858244876 1278679264 8177797721 1548494813 9092905466 0246093348 3396204647 0928619964 8461782419 2626097570 4421564860 4598738531 4945538324 1883519623 7660658133 0316572972 5910857596 7201712020 5583755908 8870857957 5824170936 9111055375 4828467207 3216217090 5812736602 5486438532 9315126241 4892368474 8876668505 3119856423 5132957256 5218069576 9926466749 0857841623 8226559083 0044224073 4157293080 2601266832 2020465084 6624628386 8688702785 5632356589 3345769011 3372804472 4309705233 6943454001 8230909059 4861901959 0522780865 1808315629 2143523511 5944479124 3897496809 7445748389 7191576133 1840867765 4777573029 8374438617 5211004837 5596955836 0371772268 9442925091 2851971664 7578066193 9594606070 9273348509 7447916366 0525768573 4953984753 6291905739 9285489665 3510230308 0689619970 5663249614 9361237918 7730316577 9995244431 5233716459 8286459059 1053188152 2850385106 4811586178 8839410895 5301936191 9276321172 9348259455 4708430586 1703757055 2266674759 0376997830 6322357390 4255221750 3490699827 1534800626 3258052860 0452680177 0296487793 6348610486 9968310294 9282963581 1036288638 7644775940 3948955233 1360324264 7782850850 4633166047 3998981558 1787045260 5015433135 1112891249 5598131259 4461170623 1110593627 6703268962 8583053735 5019670799 9613428891 9749375505 8096757970 4933356655 0817332634 4379249407 0688649935 0167011770 5968161715 9069140209 6394989012 3388043198 3899376070 2555726708 1368611387 7189866218 8920068881 7796931529 2548835087 6915342651 5959465400 5201116154 4966933287 8033695008 9983316253 7631973833 5827757517 6221887256 5014989920 5128185874 1210369796 3277648051 1750338695 9535912016 0944599739 1196839449 5185187518 8949337928 2219264767 5778469826 3163078317 1399857875 1549203432 5079172977 1446734084 0517708543 9243545884 4147885381 5307272794 9902521990 5369368846 0596246930 8328648712 0473957526 3479850517 2005359387 2533359605 8938497206 8811188163 9852864498 4460226194 7067881354 6406257899 7494911172 8670851219 8746632846 3920878075 5477342968 2212970523 2690998477 0156778975 8667807236 5836202078 2584154369 9474079485 9357143689 7314910828 5783202148 3466022653 2669721422 6536546471

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

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 = 5 suffices.

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

Express N in base F

As F2 < N < F3 and N ≡ 1 (mod F), we can let N = c2·F2 + c1·F + 1.

Brillhart, Lehmer and Selfridge

Brillhart, Lehmer and Selfridge's Theorem shows that N is prime if and only if c12-4·c2 is not a square (given 2F3 > N).

Here, c12-4·c2 is ≡ 5 (mod 63) and therefore cannot be a square and N is prime.