Primality Certificate for (3085^4703-1)/3084 | ||
| Andy Steward | 16,407 digits | 25 April 2010 |
|---|---|---|
| Originally by A.A.D.Steward 2010 | ||
| A066180 #635 | ||
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.060668% factorization of N-1:
| From | Factorisation |
|---|---|
| 3085 | 5 · 617 |
| Φ2 | 2 · 1543 |
| Φ2351 | 4703 · 300929 · 10367911 · p8184 |
| Φ4702 | 2910539 · c8194 |
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 :
| 3830 5063406981 5196119076 6292760299 8314378397 7475970175 3695680556 1895521813 3397167781 5785062873 3612335892 7730816850 6182536938 7458987453 7372569221 2362234071 0255324359 6604275174 6576630154 1395606545 5510279455 9151094728 4662169356 2364979937 5649556034 4379986674 3984155629 6659700540 2402743167 8682454236 0357871129 3169524374 0997669636 2504396863 9291699980 6963401607 8708689269 7857193624 5306171538 1768338898 4587477413 6185766553 8328087483 0615237784 6781304865 3625711474 2398438019 3444151545 1070978296 9085682072 7992350909 8232637869 9781913981 3288297335 5445464521 7468059564 0932089429 0369400065 5352257659 6108689334 2171057059 1730344030 0868378459 3112544826 5281348181 5436198321 6267796221 9613548638 3391358951 0320821577 8849670940 5228866293 2438210324 4582173888 0626601585 7521581424 9543436737 6342837413 2686801091 4620008855 8563221558 6956525437 5127179115 7855397731 3191769059 5606558185 0849998423 4565135555 0258540126 7610208860 6604676770 4732311514 1650920126 7263936118 2092246243 8689469826 0557260845 4060914191 0496425740 7410688494 4727430687 5702490106 3603181796 9844928611 3900266916 7746193841 8602714050 0041464002 2028029078 9214935844 0777301479 5811979810 6983069290 8876991315 5030878817 0545745829 7481569253 0826646856 6590931421 5146435397 3068735239 4771803366 5906386917 9304141057 3644072080 3791084943 3650434295 0689506180 9310266770 9106630423 7419106679 8237085557 1361396080 6901439688 7601693827 3434854272 0905427060 4129175236 3751469298 7690314250 3805299681 7910421174 0262305152 4062385472 0031757893 8131034025 3074193316 3118850254 4161847367 5875992152 5135964062 4745518674 8173165278 9122297352 0035938364 8833792783 9802867630 7474127845 7450853334 0256027276 3460356830 6993973176 6808300892 3821599183 5676352427 4619194025 4177176464 3472378614 4935923020 2914502918 3206858890 8051547082 2081141372 8342723077 4691030583 4708769158 1195621609 6907619190 9755479118 9017711494 7073557966 3176642826 2517971440 1102631642 4353153912 9018891551 7007995147 8187941820 2444151161 0691289930 9248894773 4087022157 4548355948 5378253472 2631038046 5207798363 1842288417 7311957255 8331542694 8516487915 5545329268 7303289191 2957755690 6595687708 3850249615 5724912848 9734193643 2192734398 6414814417 6550836467 7849243588 8802934347 0743618554 3370420188 7048270788 7387306451 4690379068 6387904017 7582213860 8946806475 6653224338 3813290549 9619639855 4809750597 0423933910 2341046996 8231030729 5002278625 3591429753 6881798707 3542326819 5450091309 1614575102 4333918073 9099797960 4979210026 7805901930 5214371035 5016259524 7438227818 6496861302 0950160630 0187754127 6932454762 8741044047 5745030358 8014863960 5607440147 3316895322 7009043314 8629683282 9562438083 1299660106 9285247449 6422330176 7359704231 9185388228 1334564115 1584527094 9897236040 4526646203 6242041414 3660485180 2067623492 7354978186 4645882247 4210696833 4040676111 1621183482 5405134036 3001554518 1274291977 3320939243 1553318440 9415094155 6690530023 5749762209 5078300404 7238984673 1289847763 4625840717 2330257565 9889325302 8179838378 6668549834 3763369014 3099404740 7107068983 8483680806 2267570943 8340048840 6620507106 1059221508 1323892590 6530620319 2314671971 5035439199 7436506558 6516201163 8763497000 9445353501 1682893959 3115230435 8130103520 8624397967 6342347033 1503893316 4095664515 2089013687 7795355400 9804763884 8023688681 2004910962 9953066918 3823433824 3880184239 3009143203 3745595999 4051282886 9146388336 3249358245 3021704955 5596655413 0336850794 4620154488 7557727630 9530984632 5206151010 1573416214 5499314000 1642984833 6254215479 2589214011 8041444213 9786774275 8585469129 1702540421 6844012833 2940875311 1138887988 6156481628 3685357469 9363277308 9711170916 1874490484 0337475519 6433183383 4768486023 1597105982 8849041117 2994960642 6564161372 8958291099 5218680174 3828753570 8394824997 9390214824 9404938748 5411258080 2813103916 8891821346 5264649345 6379349868 8173900380 8774541521 9416174930 6846959907 1272260169 7910045752 6277957503 8873084453 6641854232 4436075340 6519768007 7870974927 6356582713 2609743188 0453737652 2150281613 9966775084 8821631136 5355682125 0202900145 7021190695 2971033528 4149967307 8790410282 2682926270 2683546272 3032107928 9995177014 4396623773 5364402269 1557434472 7803732457 2970915189 8532820581 8397853971 6607836536 6857252041 4165572105 8018900320 6837520902 4225173386 5405760769 9530476343 7599806298 0792357188 6126448642 0767579105 3727268720 6690927628 5303679109 7591993899 2815342956 3479112856 5574024870 3103713642 3115152069 9261355262 1704968069 6701081516 0484976574 1491574104 4254995900 6017192896 5065652912 6897555975 6587692998 6688211140 8451506603 7902394367 0819036776 9231975173 3663851984 4342589361 4428397163 5000726019 4933147928 4844180689 0295130133 5834543457 2800836310 3941814357 4800775977 7509758049 2553002266 1148827093 7801427241 9792026292 0664433534 1171647582 5058061743 2122215453 1109274400 5733962686 1264575581 2696727411 7256418752 3277497233 3012718104 9728259517 5598941883 2387916561 5272453584 2874418513 6186921250 5300901936 1864353536 0289196351 0856816587 4330942774 5658515826 9902387712 3602064093 4332091074 7660439694 4851263849 0476655672 6607036317 2878892415 1811958080 2837415377 6838116655 9112228237 1447165436 3641584004 4127656888 9436878878 1799127651 3814904318 1637165390 8073936135 2896078960 8244067291 3002538217 5006158131 1445734187 8713251849 2959425931 9403206700 5217284770 1736957497 0842176287 3066295422 9923249225 4892815653 1275774859 4921597867 8908372916 2911190765 1518533358 7167636038 7346063593 2691459387 7457494055 7792230414 2207783688 3731367687 5606543028 0964097409 5914946856 0431246445 9610632490 1947964610 9323617962 4847410475 3203173987 1952468959 9418793140 9138104601 4720850433 6194523292 1021404115 3603554395 6839377790 0899213194 6430638103 1777748408 9511293167 1686226063 7065560857 5585223834 5305973454 3300910275 9434242760 6575455537 8090535842 8390418708 5691997265 8958035103 6609406448 5644521624 0398904008 1386819267 9173808925 6871091233 6270212052 5579578616 8517981706 5696170900 5780119035 5139900723 2533231586 8222487417 9495876966 1613548297 0185821632 4412952373 9373798025 3318747441 1175209228 9914188953 9840804999 2974065668 0096304893 8316483779 7097173822 8412069902 3825321605 6996937803 4096028586 3661742315 5337742218 4591488957 9878275773 9520716365 0941561940 0639518195 9822965500 4959045858 0578611016 7086129823 8997067092 2250822220 4820616618 7464449615 5532806090 7749844651 9782462580 1816539650 9406049690 2721302733 0772753564 2357679369 8672451536 1194458049 1227035222 9492446265 7627432753 7300547836 3941503956 7750060725 3957014008 7644738407 9851032903 4752484929 9160872729 1645563321 6105925198 9457351731 9996863615 5829591997 1122991359 7360078343 8729457862 5117893601 8223704656 1547203285 2974322210 2309437615 2123802850 8897383963 2736714564 0464445777 3804544696 9036416615 0812687212 5248766069 4934205115 1723870455 3010025093 8693902273 2028415549 6386046756 6557414435 2371120947 6282137174 7508699154 2404498874 3552043824 5731524779 9382049636 0182239833 4096711656 6398532552 4311407078 7564823236 7923467454 2090007561 6868376667 4825810387 4197982611 7856096351 8108751226 7057568221 8164775974 8232625010 1132105924 5136537697 8870991844 6407576044 6613669140 7103808613 7078324644 2300491641 3290833925 7334131931 3232060778 2155173537 0714045899 5963076733 9870006336 6744505398 1472355453 5595319654 6315845110 2653564833 1110901697 7326331416 2641016788 5846233477 3912356851 7905670473 3597819978 9118749047 5160224554 2807781383 7239981228 9733967690 6844590313 9267009817 3919490896 8027531655 2066612179 8691265588 5400854171 3654070256 6152866389 8847178644 5082140621 0589212960 0819553143 6476570022 8827493101 6393273529 1890540775 6252538443 4718342791 6580955073 7707384011 7074288217 1653996718 8254244715 3300043171 7078892668 4366973383 4912268031 7656751377 4614245353 5151323763 8617123821 1853598296 9658331594 9474505419 8012259826 6152850224 4889704726 9446694808 2589843489 3337125713 1016299427 7906454581 7905222131 8328939939 6157796971 4329382261 3491102321 0437454696 1646927657 3458082725 9578963577 9436099200 4028145082 9334495193 1048438739 2804904759 8400327821 0012581931 8096879258 7122021440 5769732929 6031742338 7893737140 9680254314 3878895446 5735248666 5216630533 9577701676 8323307268 9835708713 9428867728 8357391653 1485888173 6411993957 4950965772 2182720742 1592908543 5185438847 2293437505 7381742308 8235419529 4226826561 9208960334 7838778142 0657361497 5910461102 7055047347 0828969389 6970140419 3580223588 2612655832 0463738685 0688712498 5510076963 3258488169 2920589366 7400895449 8221884283 2098534278 7051836502 3656864783 6313475022 8058603149 1831539066 8614451066 2777946710 4413605203 3103629309 7100822327 7108988677 4854496136 5076240107 4209708352 5195130489 9976527264 3470634752 0779521158 2775186723 |
| 10367911 |
| 2910539 |
| 300929 |
| 4703 |
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.018132%
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.