Primality Certificate for (683^5483-1)/682 | ||
| Andy Steward | 15,539 digits | 14 September 2009 |
|---|---|---|
| Originally by A.A.D.Steward 2009 | ||
| A066180 #725 | ||
This certificate uses a theorem of Pocklington and Lehmer to prove an integer N prime by making use of a partial prime factorization of N-1.
As N is a Generalized Repunit, we make use of the algebraic factorization of N-1 to arrive at the following 50.087841% factorization of N-1:
| From | Factorisation |
|---|---|
| 683 | 683 |
| Φ2 | 2 · 2 · 3 · 3 · 19 |
| Φ2741 | 65295093313 · c7756 |
| Φ5482 | 5483 · 16447 · 49339 · p7754 |
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/2 :
| 4611 0242694186 5180511427 9496912899 7317039861 4855835353 9644725925 7483727931 5700251529 9930835609 9751111131 4751259100 5532546251 5869279818 6297933672 9932418112 5326270421 0008561095 5405672846 5575564479 8863483030 2220368513 0176141176 2285030469 3635436870 4135800755 8261598105 2010602546 4052456499 6931523184 6160835084 2986712015 3383345956 4311750418 9540161434 2732805422 7764144822 7290339676 3286371144 9469319310 8517753606 4632946861 4123821898 6528171296 4468083613 6589832290 7830413148 4737793930 6584720409 5779804148 3836175469 4346383262 1015358233 1511968593 7966669767 2186423249 6488619302 4478015615 0135278640 7912206080 4354791196 8596508684 8730141828 5346747802 0759974225 3948253493 7078777418 0006035788 4859145633 0986359505 2510372560 6876530593 6954086030 7840708736 8252460817 1138065924 7433774238 1426367058 2170555533 0018624009 4050591389 0264881885 0340930227 3997808640 5731478788 0867957184 2809762786 8447316735 7960978964 5401209836 0182218709 3373456295 8180079436 1260569108 9193822335 8730393793 0388351280 1896430438 4309203759 2392848832 7454988925 9235553734 0533981136 6053511084 8241579902 7712988834 0390378262 2865818761 2450807495 8944947962 5435107894 5253748643 9867236917 7724619780 8630627817 6095027176 0687466505 9517922413 0158214377 5218571602 0926583540 1697870521 2676389498 8031486367 9261268903 4221951599 0673158762 2759635960 0767193116 3280588300 0785156947 4861098561 5628557862 6593072948 1392934802 3528647033 8602301674 2701400026 8975224442 1818111891 0333542991 9753094052 7350718022 2405881785 3149192168 7757122316 3362438145 2964882999 7420348769 1680699583 9903719602 0152035412 8195086824 4403833549 2265947567 3299688509 7590866970 5303220186 4034411214 1565312368 2897567306 4664461977 5306169449 5363492431 4715110393 7322804071 6723561036 3711408252 8270227628 3762703880 7043205554 9440805009 7937173073 9904859178 3085264731 4045676073 9115869695 6677435379 7488010571 2416170587 2572426861 7708709173 2217940566 9278532350 8006219180 6275705714 5601614835 1401812871 2309691939 9547260068 3947101686 5326073627 0834215651 7259224874 3367742444 2634036166 3016556007 0067102586 9323960921 7764085902 0162520852 9804012936 8688986332 8420579603 6192231215 6841843922 8232557148 8109420161 5580419258 0005216877 0423751744 4328660043 6056784229 0988551532 0440609102 1523970858 8513457215 4754832129 9872313635 6349583845 4556614486 0732088832 5768028999 6659648489 9057547997 7254610562 0709668255 3446679107 7477189312 9527053542 2003041358 5292985827 8602523163 8069263216 8268482749 0214543494 5492391961 8679536948 1058841326 2000216486 1765347596 0191033803 2075192489 5925186807 8815600118 5500699550 3203301998 4458079336 9082135044 8423164004 3822607135 5678209992 2525106643 2615168738 8773050528 9161771045 4040544518 8239181670 1498674467 8239438226 2500992297 3049600605 1708074908 1036004564 3465915917 4207992694 7947765230 5791319391 8758496493 3834228196 8197747941 4089248909 8775497222 1974407553 0383555003 6496534193 4647843755 3901369816 5321282791 2189100555 3075385766 8830331700 5719755365 6326069288 0936369727 2400362341 4489434348 2954534408 8449949574 8377946754 4446974561 5659942981 8193437564 0823797408 7356608225 0534090801 9214160520 3114621389 1252162991 8019909912 0240974468 9310690235 3394696402 0266431495 5627923252 7284871273 0163395150 2269598419 3143618092 9263608742 5480843274 0332058169 4986564334 5733822487 3845738260 6649607174 3293009245 9448370805 6131470829 9150925589 3856014661 1462737292 7098712579 0075281230 8564432475 7731671062 1960146762 0183846433 1245927174 0082310597 3363537601 2590540548 0599951234 0601592729 2613583681 6327830873 1302710125 6807174623 4836802849 4284837496 2238272827 6371080779 4439959779 3700532530 1001112394 3936789205 5981479861 5366302375 1621616552 1234818427 1885888072 9322361898 0243113442 2228646726 5286132274 2330320083 0360503519 0148926238 8260172176 9368136442 6752294497 8506700291 2676414741 6279198324 1395606127 4684861378 4476193481 0703303473 6938395094 5287991699 1353239731 4385731970 9673524879 8597561288 4910805321 8328030519 8206567806 1727674879 9541643226 5602858096 8329542326 4553508077 8117830122 9761767690 3654922442 3903891015 7269365079 0043108927 1894110577 1208104555 1864793329 6763896982 8268781696 7923749245 8777912716 1164147792 3436982140 1271625556 2963561854 2382838666 4462851976 2496965019 8172323156 9475217234 6960567019 8157314463 0881520718 6327333120 9398980737 6589555378 2535105082 6493063370 2266823857 7686314449 3235264650 6848686003 9163039859 5977945186 3123305905 6483146242 7861910288 2895757716 0476777985 3834350484 8141492499 7094040146 7360203138 8445680277 2918413187 2414776910 1438554619 7829870621 5325080506 5407275893 7949606017 0545816286 5566306031 0826383718 2608474148 2767797063 7259980241 0619063431 7226898260 4923595270 5149467714 5248462247 1221104562 4570562913 3392740343 1624721663 0283468270 3859412740 3131088768 1244775158 3037215680 6340041142 6605424609 1433304247 3560060184 9361918352 3113019126 5870885427 1993455800 8319348889 7563840841 9383006668 3998401768 6412045240 6617227874 7457608148 0886540731 3780798437 9413136097 3903652430 5012910118 8836041778 5672455340 7079375765 4137113708 7705214672 0063402489 4462495612 4523146895 9208754071 5061592446 4654305472 1171411745 0154634580 8524140892 0708838037 7128861345 7571153808 7895977959 1913829164 7417383869 9231269915 7537969331 0330120125 9611899572 9645615286 3828584646 2647289370 2753526730 1213186660 5103288401 9455946073 7947569697 8411050456 5147115648 2034018581 8456205832 9111988221 3465243934 1278210072 6539596965 2919069647 2532345782 9700384736 5821311072 4687409665 9528534945 7606976192 2315027486 3194133028 2452212418 3618590232 6978203802 9428444846 1632091458 3803001247 2337222795 2986519192 5123431835 3308804595 9621908814 2619130689 8235982360 0936854993 9904755261 2212131766 4002665141 1184415214 0033318853 6635066532 0419890281 6922356163 6781220178 0974428289 8421550082 2849617402 7588428958 9047042679 2188325121 0463608754 5261991426 1617904249 7726516803 3031848291 0723607522 3385288902 0534941550 1930867358 5043609267 0852757941 8197227541 9585646448 9765825229 5003589336 3414005149 4226525539 8820802876 3787311332 4753334605 9548460089 9938111883 6721976819 8717331183 2000897219 5259101036 4250757051 8103942287 1804103356 6227623228 5207260971 1901224326 7077585712 9079500994 0796567464 9699707051 5658758473 9178995027 4784372680 0396172583 8599133064 5462017599 1916581707 8969688995 9202366680 2204292276 8087751953 5214822863 0504989924 9184289053 2740913834 8407068677 5436165240 2114064438 0727083891 5048062746 9109029126 3140089184 4204221481 4535864610 8489717352 5298320149 0734377633 9495630610 2103175395 0260107124 0281500653 0605058251 8527290938 6605932916 0997010124 8738159487 9847241503 5250353454 9565927814 4306780723 0760712367 1506945627 3233355484 8216266566 4373065590 0694035650 4171484475 5301401415 9751458454 3816133579 4903983836 8944080556 9101637765 8945430507 4348659328 6279714626 5673518228 4034622839 8934323939 3638735007 9082698317 2768463216 5971137581 9801647456 9682973336 3035705206 6370660777 8555452631 7538877287 1640281646 0227639518 8730293633 0338046188 5302447933 6844644329 9298332067 0510625365 2477248170 8338760751 6705941332 6208288602 7813662832 8770683113 6028416638 3331708575 9438472575 1581628218 7041196926 0304204021 1654166494 2804774637 4754199176 9125260367 0219437835 6950381339 8027970731 8145364922 9647886748 7679786350 7687200319 2645300673 0548975889 7854727751 5749754333 5108441965 0982734260 9759019326 8734113290 4467170465 8716834870 3344530088 2180734230 8599738022 2521669476 6937368601 7826351108 7966294085 6938554053 9640384608 0490507897 5667618070 3303211045 7339024296 7043400434 8540391803 8150374381 5744166224 9796652416 5197604958 6634835681 6240951142 2605623628 7198776912 5784040350 0152409796 5166913070 3907251800 2779231436 2203350968 9472664072 1711317595 7644953520 9336577644 6585408003 4538914040 1105627347 4170608109 6572438023 2101697958 1054542221 4825137793 4184687216 2160792427 7568775995 9626810636 4028067901 6459482676 3500396521 0787710840 3400634092 1691856422 9199215712 1272863636 5839726394 4504154573 6466534498 6738652281 1445635725 7747459199 1405765290 4292082366 4951563471 3391275749 3444372148 1419967742 9005284884 5349255308 5722348462 4523137673 5623909704 8516505606 7626702724 5802752618 7357884018 5420432509 7952100388 5328570059 |
| 6 5295093313 |
| 49339 |
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) = 50.000157%
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.
Pocklington's Theorem states that the above information is sufficient to prove that any factor of N is ≡ 1 (mod F).
If N is composed of two (not necessarily prime) factors, let them be a·F+1 and b·F+1 (with a, b > 0). This would imply that N > a·b·F2 > F2 > N, so N must be prime.