Primality Certificate for (4676^2161-1)/4675

This certificate uses a theorem of Konyagin and Pomerance 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 30.471170% 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 ^3/10 :

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

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.

Express N in base F

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

• c₁= 227924 6161209526 7723345622 8628128595 5557695057 5424629562 6373897249 4596031372 0443060856 0556379176 4416704172 2251637240 5806760509 6441782455 8994939843 1709660164 3039623291 2541209291 9619176646 7812761391 6597742510 1448765884 5253496569 3841529619 6799613360 5094353647 7791570191 3515547605 3858164731 9512547045 9176667015 9362791347 6551460935 4582007610 4103707362 2536221452 4880436937 4255659097 5253877990 7308341426 7166920799 0004685294 5081747231 6851084588 3404859038 8933028499 3012686406 0870192085 4062947966 2291397001 0680782422 2377442246 3002295804 9066870913 3763512284 9628574398 3688304465 9715782229 8243187051 1480026518 0301725448 7961730024 7158970732 5122889750 6363968279 0255189430 6733672851 4408583095 3933354050 1082465524 1492762162 7811317536 3674183946 1137915840 6089457778 1140999117 5889235201 0329198497 1023990085 6004813755 4782821206 4002950342 8118892334 6684396846 7265907008 5007827884 7888802505 4251952107 4708350241 7916145287 3306051775 0807680791 9609244383 5355166135 2167162396 0210695082 8559225567 6332689849 9373664853 3019645075 4199864499 6960826854 6284831484 4468104736 0299487364 1511458636 9781306442 6331468131 7634287324 8293527583 9529407423 5063745819 2563635949 2357305730 9883706360 2707526200 2427797413 1233204495 4142605087 1418897040 2227293417 8152288318 6334500454 6213852831 8501680137 0358009692 0158315877 6637859319 9172244788 9071256853 7449519635 6000742689 4110940255 5946681303 5618697425 4336389403 5332284776 9914954963 7691936966 7148643564 2511812585 6187715022 6741890846 7028628047 5031888248 6957761266 3581677683 5971941741 2395654554 1283530626 8670931822 2571752299 3201803971 1683393943 0923566796 3139267187 4604081746 4726703429 0480554189 6261661256 6708616325 8445373628 8925481991 0570828247 1223195407 4090642561 2855803157 1170172028 2447298471 6865344331 9497811429 0381485435 5695958731 6638594927 8230213163 8099394273 7588883045 9383151487 2406250387 5002231489 6478758664 1485325911 4271665145 2011755415 8130569918 6914790450 5042960448 9756117011 7978279285 7983752569 2301458343 8143223384 5684214048 2650430756 7196370923 5912016738 3029464308 2805355391 5700571113 2798310658 4965594313 4663559665 0841360979 2752820419 1539185465 9407918817 6605438183 4116275831 2943052238 6996599478 7564104694 2185843968 6932463247 9288650079 3511519635 3458657199 6934521086 1756348024 3457254102 9450927179 6601964071 4746505467 6765866296 8170202879 7374295007 1418587459 5611118366 9571251661 1629656934 8790608891 3258470059 6631326835 8617659231 1946667740 5962459407 5236069514 7629539974 7251419809 5251049287 6526974886 3706258444 0003464809
• c₂= 232108 0173731817 1102252133 9634731786 4793127774 4404968026 8439921822 5525519853 0011867230 6724484335 6581521373 5258889865 1924519535 2921236756 5264053180 2532334232 5769398799 9975744914 1007613258 7654894479 7299560493 6484216197 7858940422 5719040428 2183960545 3647433275 9652665242 4530331359 9841052922 7243519914 3180351453 7274116818 3290807861 7876041508 0388571260 8070749059 2706219237 9741375580 6730765680 8503481297 4279833682 5002227040 6968587825 8600038714 1295929530 2153191537 8680079052 4514178159 6099301775 4229888219 0106050064 6126876854 8214226877 3948572110 4352944590 6827298661 7268154921 7833505463 3083994538 6454207342 5825525632 0604837853 0544428863 9414205556 8022299167 6389550801 3288034518 7866746582 9641039862 1037891674 3634446753 0902157727 9062409726 2416696011 8739874707 8665190732 6713270045 3348772752 4585772928 5484085752 0033759525 0083370839 0589498640 8400441957 4403935797 5157936623 3405679593 2160966807 3436964153 8163286513 5314792602 8184579975 6018939073 1887254837 2292109247 9109319768 7877928823 3744426429 0860135323 8611505213 9985474358 1174566481 8722864856 4369004228 3487213350 2240746892 2696589908 6648565794 7716424039 5604136930 0444208814 2007133443 3533494974 9559371971 8987399970 9041446810 3821720652 5222239890 9187538347 4727215457 6004886986 3209775463 0363455714 8556789178 7528164859 3506462394 9779400115 5768251721 2444713337 7946982962 9070449850 7180076198 1070798299 2753599542 1461526559 6629770316 8851891524 0254554423 0289079329 6865212111 9916659108 1472560193 1802641920 1561465812 9841168523 2168722725 6406074870 5345979311 4181955542 2878888211 6950469942 8691565431 9945081950 9732952178 6380237097 4013741480 8836847736 9328092403 1313570220 5542811274 9855107397 5069230709 7036795756 0511442304 5613751496 8566738713 3338844353 5660627279 0782197341 4803130275 1485006343 9411759864 9395774686 7821831130 9826484110 8768228181 8790325250 1648247597 3886765112 6798760507 4828831419 4335378400 3281495492 6275467924 8712057059 0357277872 9897619596 6122041407 4123640027 0460186597 7586807249 6025028151 2454607415 9772730494 6845506530 1370271622 3764512276 0597866339 5176525881 7708483623 3008253985 9387926045 9580263136 2414520053 0576640400 1784041615 6342749081 8128670924 7235115165 3817727474 1612738442 5033060195 0756530819 4833085414 3786207057 3719872052 7769599545 9331391953 7034510271 4456046641 6479354927 4306314812 9570513922 8671123875 5924516150 5417196208 2093959680 2698102973 1454801882 6401824683 5102566286 7147069307 2654281162 3992367406 0795425381 8929454101 2043234715 3778128362 6396562460 4896748115 6780669979 6700076312
• c₃= 4 4149546998 8160225100 0716690602 5910783642 6518050757 3067650237 4657861906 2145652403 5208171257 7007678572 1307361821 0280514731 9886850843 4488590586 8400775141 4688850870 4155342499 5776073222 6739065803 7065593893 8347630494 3344263295 0598878851 8102093485 7006553870 5198251836 0442072195 0878935658 7905943976 8346312513 3492392831 3317751865 9325667213 2039192144 9356616247 5944686976 1325369117 1545053068 0632035519 9269624264 4892818067 4156120599 8210061085 6618291159 7784886246 5480609409 9423072151 6338245938 3629410444 7806192135 2349912199 5478712021 0230215769 8468117178 0438031904 4033034703 1385423851 3969613914 5316860285 5154894104 6847030693 6075692647 6933275817 9405009541 9776013225 4781135710 3362394848 9768986263
• c₄= 1182924 2173650852 6363057208 9547802425 3150563758 5162067370 3362966351 6645748860 8636865820 4993322784 8684102981 9156464035 0466984077 4044858117 1506014099 6586548791 2293548088 5304491571 8871422192 9760669466 3718328815 6328012853 3800079729 5127346921 1527142957 7090903938 7031889618 0103156032 3372464797 9605973887 5905101790 3192072797 9101424661 7228471057 7221496538 2609197657 9089716869 0366423504 8374954574 8312534934 6211661062 0502366915 1844586663 0644500133 4097165059 2127575759 6757306148 8343770166 9587174148 1964521421 7673658230 8222662096 4938285703 6074901777 4852354610 0197628543 6764967200 0172183106 6234838985 1280557319 3805192286 1754907507 2302827138 8738794011 1017127310 8668388408 7555963578 9423204622 1256958421 0419520971 6868058282 5412088657 9781314115 1062669813 5522788102 8765669480 4476408681 8220350873 4484029847 9839556248 5727165153 4354424573 1388219004 7941109583 0384575272 1639785190 6748293570 4477672973 9256764477 5346660868 4748167409 1780879794 3230657390 4356712466 4888054337 7107296332 1423618542 7399649203 1130796142 0911364067 3184948235 5470313364 1609478506 3804598691 3716378143 3415131404 6479925483 0498370130 6677238183 0480611024 1626767138 8462336774 4246856631 0372902946 7718426073 6502380982 9010067209 9545430045 4581145364 4586420826 3661491570 4186503231 3655847633 3860495458 9896179676 2153043187 3608381044 4686455230 3537309854 2375999499 5025468392 7922863085 7001909488 9308454303 7253319748 2566092189 0255733441 4556173180 8637966263 8116834108 6056625006 9363341517 3398224670 3517579566 9858856200 3659479583 9100743535 7710199319 7555339931 1550177084 0534575729 0744396898 8713668422 9735021519 1483833074 4153054563 2065234368 5004890339 6776929579 7573415400 3179311852 5830276029 4449768178 3156527729 1055227345 4404010619 0758974504 9135348049 9436315816 8586498773 2022809224 8771113895 3674956558 3943623699 3457463405 6703213863 0035661096 5955312703 3828627919 7920314195 1359126897 2606320212 3099442395 2421891871 3887058115 4723788082 7731104664 5488807734 4283071236 0112076497 6112408977 2513953333 4642366552 7353797884 2601539769 9273075827 8573005691 5969365957 7923203023 6227545740 1330558111 4540211069 4532692294 9547708027 6607948250 5238887506 3503975600 7561484532 9187193693 9175257854 5592319168 9557210017 9851407732 7204871557 8477408437 9016126206 6844163154 6402181872 0712822945 8715979236 3676639765 4040937636 1787672409 9582675881 3930075628 1285641168 2072294976 9155874345 4820607847 4211229256 1450918191 9253716025 4058563955 5690175386 7449290498 9521958718 5759188840 6048957166 6113924244 8178593008 5807421384 6435265002 5864588974 3391764262 1049563930 7800159349 2532586939 1773453288 7920863286 3774025483 3737290600 4533427867 0275809911 6226815534 9891918575 8300663142 8151573945 6295855447 2871431739 0259679423 4080326790 8871231010 7147585876 5083663289 3930910639 9004763899 7311430795 6304906914 9562229974 4851738795 4763086587 1267323351 9874627121 2709841511 2383783377 9723848172 5447156753 0589101422 1625569325 2856975012 8053495421 7707125771 2464787300 2336970717 1372161497 4129848413 6158756611 9122199184 0491494849 2009709974 8577269396 8144013448 6977357403 3379842377 8612348078 7867700086 7571810652 6952543162 5237949237 2463215562 1735563105 2988096400 9856163171 8293443189 4244471299 1597135835 8382904200 7201100725 4726149309 3310254532

Square Checks

For t = 0 to 5, we prove that Q(t) = (c₁+t·F)²+4·t-4·c₄ is not a perfect square. This is done by checking whether Q(t) is a quadratic residue modulo a variety of bases. If it happens to be a QR in all of the bases, we calculate s = floor(sqrt(Q(t))) and show that s² < Q(t).

• Q(0) is not a perfect square: it is ≡ 52 (mod 63)
• Q(1) is not a perfect square: it is ≡ 29 (mod 64)
• Q(2) is not a perfect square: it is ≡ 60 (mod 63)
• Q(3) is not a perfect square: it is ≡ 21 (mod 64)
• Q(4) is not a perfect square: it is ≡ 5 (mod 63)
• Q(5) is not a perfect square: it is ≡ 45 (mod 64)

Continued Fraction

We approximate c₁/F by a continued fraction u/v such that v is maximal while remaining less than F² / N^1/2 = 24634979 7527326637 1993469466 6535570919 5001035731 9119012635 1257139384 2859950235 8233061294 4332762903 2016881534 6599101750 7132073578 6603043752 7234106780 9688149287 1800002951 3232739445 4507895133 9341466855 4795559379 3702492985 4010007651 7841932925 7707107156 4234967346 0668830854 9608211485 0080414679 2996919340 6290140447 7264824823 6170513522 3556309953 4064037502 4579554734 9583074603 7582162036 6729011453 6005424127 5932890849 7790638715 3797632912 2196148813 8212483589 2528504164 6356144542 6206294957 2838864737 0251134983 6292150435 7207435194 6595727664 0554822322 6710444533 7542150220 2340996195 3728363149 9394616878 1062613309 1211099373 4635431065 0111990527 0655589153 4626738071 2817502016 1277588298 5000283783 4921361440 5454398487 4222410253 4010803525 0228977977 5500407412 6303847085 3092498986 7856952952 8792565455 0374600703 6066895044 2874088430 6778944909 3662706177 9776317629 2028849411 7707506020 4358910053.

With those constraints, the unique continued fraction is: {0, 1, 5, 1, 2, 3, 2, 1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 2, 1, 19, 1, 12, 1, 6, 1, 17, 3, 2, 1, 1, 3, 1, 1, 2, 1, 1, 2, 8, 1, 19, 1, 10, 3, 8, 1, 12, 1, 1, 1, 11, 2, 2, 3, 1, 3, 1, 10, 1, 1, 5, 20, 1, 3, 3, 10, 7, 2, 1, 1, 1, 2, 1, 1, 20, 2, 1, 1, 2, 4, 2, 2, 5, 2, 3, 3, 5, 1, 2, 1, 1, 1, 12, 244, 5, 4, 10, 2, 2, 1, 13, 1, 1, 1, 1, 3, 13, 1, 13, 1, 1, 6, 1, 2, 1, 5, 2, 3, 4, 2, 9, 1, 1, 4, 1, 1, 7, 1, 35, 2, 3, 2, 1, 1, 5, 6, 3, 1, 122, 1, 5, 3, 3, 1, 4, 1, 29, 2, 2, 3, 6, 1, 13, 2, 1, 2, 5, 1, 1, 13, 1, 2, 1, 3, 4, 2, 3, 3, 1, 42, 12, 3, 19, 2, 1, 24, 1, 6, 1, 2, 1, 4, 2, 1, 3, 2, 2, 1, 6, 6, 2, 1, 31, 1, 33, 1, 2, 1, 2, 1, 11, 4, 3, 1, 4, 3, 5398, 1, 2, 1, 33, 20, 2, 1, 3, 1, 195, 1, 3, 4, 1, 1, 2, 5, 9, 16, 1, 5, 1, 819, 2, 1, 2, 2, 7, 3, 2, 7, 2, 31, 3, 4, 2, 4, 3, 1, 3, 1, 8, 1, 1, 1, 1, 1, 1, 18, 15, 1, 3, 1, 1, 1, 2, 2, 7, 1, 1, 1, 7, 2, 7, 6, 1, 4, 1, 1, 5, 1, 1, 2, 7, 1, 8, 1, 2, 14, 1, 10, 3, 1, 1, 7, 1, 4, 1, 1, 3, 4, 1, 1, 1, 3, 5, 1, 2, 2, 3, 1, 1, 8, 5, 2, 6, 3, 24, 1, 7, 19, 2, 9, 1, 2, 1, 3, 5, 1, 7, 2, 1, 14, 1, 16, 2, 1, 3, 1, 3, 9, 1, 14, 3, 1, 1, 1, 1, 1, 7, 1, 15, 2, 2, 6, 30, 1, 1, 1, 69, 1, 1, 32, 2, 1, 2, 2, 1, 2, 1, 12, 1, 1, 7, 1, 3, 8, 2, 1, 62, 2, 1, 1, 2, 4, 1, 42, 3, 2, 8, 3, 1, 5, 1, 8, 2, 2, 1, 1, 1, 1, 5, 6, 11, 1, 7, 1, 1, 47, 1, 2, 1, 1, 3, 1, 13, 3, 1, 2, 1, 2, 1, 7, 1, 83, 1, 1, 3, 1, 1, 1, 5, 8, 1, 1, 4, 1, 1, 1, 1, 2, 209, 1, 6, 35, 3, 5, 1, 2, 2, 3, 1, 1, 2, 6, 8, 73, 1, 6, 1, 2, 2, 593, 33, 1, 3, 1, 4, 1, 1, 1, 1, 2, 1, 3, 1, 1, 6, 5, 1, 28, 1, 5, 1, 1, 8, 1, 2, 2, 1, 2, 7, 5, 1, 8, 5, 6, 1, 10, 1, 11, 1, 8, 7, 4, 3, 1, 1, 8, 1, 2, 14, 1, 3, 1, 4, 2, 7, 2, 3, 4, 1, 2, 4, 11, 1, 1, 1, 2, 3, 1, 4, 1, 45, 4, 1, 9, 5, 1, 6, 3, 4, 3, 2, 2, 1, 6, 1, 1, 4, 4, 1, 4, 2, 1, 4, 75, 1, 54, 1, 10, 1, 3, 2, 2, 3, 2, 3, 28, 1, 7, 1, 1, 31, 9, 2, 2, 3, 80, 1, 31, 1, 5, 2, 30, 3, 1, 38, 1, 13, 1, 1, 2, 1, 6, 2, 2, 3, 2, 28, 2, 6, 1, 1, 1, 2, 1, 2, 5, 9, 1, 2, 6, 1, 1, 5, 2, 1, 4, 1, 8, 2, 1, 6, 1, 5, 1, 1, 26, 1, 1, 6, 1, 2, 1, 5, 1, 2, 2, 2, 5, 1, 3, 1, 4, 2, 3, 13, 7, 12, 10, 1, 1, 13, 3, 4, 1, 3, 1, 15, 1, 1, 3, 6, 1, 1, 5, 35, 310, 1, 10, 1, 1, 2, 1, 1, 1, 5, 1, 3, 6, 14, 5, 2, 8, 3, 4, 1, 1, 13, 17, 1, 1, 1038, 1, 5, 1, 2, 1, 4, 4, 524, 1, 1, 5, 3, 1, 5, 2, 1, 1, 1, 3, 633, 1, 5, 8, 1, 3, 1, 2, 1, 10, 1, 1, 2, 2, 5, 5, 14, 19, 1, 1, 1, 1, 1, 1, 1, 3, 36, 1, 2, 1, 4, 1, 3, 3, 1, 18, 2, 2, 5, 22, 1, 2, 1, 1, 2, 4, 1, 2, 1, 39, 1, 2, 4, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 6, 4, 16, 8, 4, 2, 4, 45, 2, 2, 1, 4, 9, 3, 2, 1, 1, 5, 4, 1, 7, 70, 1, 2, 2, 4, 1, 4, 2, 1, 1, 10, 1, 6, 1, 8, 1, 1, 6, 2, 5, 1, 1, 4, 1, 1, 3, 1, 2, 3, 2, 7, 1, 1, 2, 1, 3, 3, 18, 1, 4, 3, 1, 4, 1, 3, 1, 1, 4, 2, 65, 1, 34, 7, 8, 5, 2, 1, 4, 1, 1, 1, 15, 1, 61, 1, 2, 1, 1, 18, 11, 2, 1, 1, 2, 1, 10, 1, 2, 2, 1, 1, 1, 2, 1, 1, 6, 1, 3, 1, 1, 2, 3, 2, 2, 6, 1, 1, 2, 5, 1, 2, 91, 1, 1, 3, 5, 2, 1, 1, 4, 2, 2, 2, 1, 5, 1, 53, 1, 25, 20, 1, 8, 1, 3, 1, 245, 36, 1, 10, 4, 1, 1, 1, 3, 1, 2, 2, 13, 1, 2, 10, 2, 1, 4, 1, 5, 1, 1, 1, 1, 1, 6, 1, 1, 9, 8, 2, 1, 2, 225, 1, 2, 8, 5, 1, 1, 5, 2, 80, 1, 1, 6, 2, 5, 2, 2, 9, 6, 16, 1, 1, 1, 15, 3, 3, 1, 5, 1, 1, 1, 2, 14, 399, 2, 1, 1, 2, 4, 1, 4, 2, 2, 3, 9, 7, 1, 2, 30, 1, 2, 1, 10, 1, 30, 17, 1, 1, 1, 45, 11, 1, 15, 1, 1, 1, 4, 6, 1, 2, 1, 3, 1, 2, 5, 1, 2, 1, 1, 1, 354, 2, 2, 4, 1, 2, 18, 8, 3, 71, 1, 4, 3, 1, 6, 2, 3, 10, 2, 1, 4, 1, 1, 1, 1, 2, 2, 1, 1, 2, 4, 1, 12, 4, 7, 1, 49, 2, 1, 1, 1, 1, 1, 2, 8, 1, 316, 1, 33, 2, 5, 11, 1, 1, 1, 3, 1, 1, 89, 1, 1, 7, 1, 3, 2, 3, 3, 1, 1, 3, 1, 1, 1, 1, 6, 1, 3, 2, 1, 2, 1, 1, 1, 2, 1, 8, 7, 2, 1, 2, 1, 2, 2, 3, 1, 1, 3, 2, 156, 1, 6, 3, 25, 31, 2, 2, 2, 4, 1, 2, 1, 2, 3, 1, 6, 6, 4, 1, 3, 2, 1, 8, 1, 5, 1, 2, 1, 4, 1, 2, 1, 3, 8, 1, 2, 51, 4, 3, 2, 1, 1, 25, 2, 1, 1, 1, 11, 4, 3, 21, 1, 1, 1, 1, 3, 1, 1, 11, 1, 1, 1, 59, 3, 3, 2, 3, 2, 1, 39, 1, 1, 3, 12, 64, 2, 1, 18, 1, 9, 2, 4, 1, 2, 11, 1, 3360, 1, 4, 1, 1, 1, 2, 4, 1, 12, 1, 6, 1, 3, 1, 8, 1, 1, 7, 2, 5, 3, 1, 5, 2, 1, 3, 1, 2, 1, 2, 1, 1, 394, 30, 1, 2, 8, 35, 4, 56, 1, 1, 13, 1, 5, 4, 2, 3, 1, 3, 4, 48, 1, 6, 1, 2, 1, 5, 5, 8, 2, 2, 3, 2, 1, 1, 3, 1, 11, 2, 8, 3, 5, 4, 2, 2, 4, 1, 2, 2, 1, 1, 30, 3, 1, 7, 1, 2, 130, 2, 3, 10, 28, 3, 1, 7, 3, 2, 5, 1, 1, 1, 4, 2, 5, 2, 4, 1, 3, 1, 1, 4, 1, 1, 1, 1, 3, 38, 2, 2, 1, 4, 6, 1, 2, 1, 2, 15, 1, 1, 20, 1, 5, 6, 1, 3, 2, 12, 2, 1, 14, 7, 1, 2, 7, 2, 2, 1, 3, 5, 7, 1, 3, 1, 40, 1, 3, 1, 2, 3, 7, 7, 3, 3, 1, 2, 1, 11, 1, 1, 1, 3, 2, 2, 9, 1, 2, 1, 4, 1, 1, 1, 3, 1, 3, 1, 1, 3, 1, 4, 1, 3, 8, 2, 2, 1, 1, 1, 2, 12, 4, 6, 5, 7, 7, 33, 18, 2, 1, 2, 2, 6, 3, 3, 17, 2, 2, 2, 11, 322, 1, 1, 2, 1, 2, 3, 2, 44, 1, 10, 18, 2, 47, 3, 3, 23, 3, 1, 2, 5, 1, 13, 4, 1, 1, 3, 11, 1, 3, 2, 1, 1, 7, 1, 15, 4, 52, 2, 11, 1, 13, 7, 4, 2, 1, 2, 1, 5, 14, 1, 2, 5, 6, 1, 2, 5, 3, 2, 1, 1, 1, 5, 3, 1, 1, 2, 1, 10, 3, 7, 30, 3, 1, 1, 1, 7, 8, 1, 2, 3, 1, 1, 21, 10, 1, 1, 1, 4, 5, 1, 2, 1, 1, 1, 2, 1, 2, 2, 2, 6, 1, 5, 1, 2, 5, 1, 3, 1, 205, 15, 4, 1, 2, 1, 2, 1, 1, 1, 2, 6, 7, 2, 3, 45, 9, 5, 6, 1, 1, 2, 1, 1, 4, 4, 4, 1, 1, 4, 2, 49, 3, 2, 3, 4, 1, 1, 2, 6, 1, 1, 2, 1, 1, 1, 6, 4, 2, 7, 1, 2, 1, 1, 4, 2, 16, 2, 1, 1, 3, 12, 2, 1, 1, 5, 2, 1, 2, 4, 6, 10, 1, 3, 1, 1, 1, 18, 1, 5, 3, 1, 1, 1, 220, 3, 1, 1, 1, 1, 5, 1, 2, 5, 1, 24, 7, 3, 5, 35, 1, 1, 38, 4, 30, 1, 1, 5, 1, 1, 3, 1, 5, 1, 2, 5, 1, 1, 5, 1, 54, 2, 2, 8, 1, 1, 1, 4, 4, 1, 12, 2, 2, 6, 1, 1, 13, 1, 2, 2}, giving these values for u and v:

• u= 2378349 9845780745 4959443112 6661135433 1180827605 6297813092 8174928802 9079713477 1252976625 2243978628 7789402556 6195934855 8954905987 4092624931 0643980514 4693725532 9363458461 6328769937 5235993353 5240821446 1600082743 3760936642 4945058978 0373707811 5232009941 1994553107 5871619900 0751277280 6714687964 9196825537 0601685526 4450240045 7717368917 0598468117 9570137537 9753070760 9816715578 8542811531 3728561055 1067086309 9491389012 6449776368 2455216227 0398593496 8296645262 2698071401 9403973214 3398634636 4982601251 8946939020 5967556550 8883371675 3292157257 4732519391 6575985574 9064984340 2615326334 1778660943 3333616610 8660893043 8408485848 8288798903 2559432755 5675867989 3402007657 4443116018 3210771470 7703560028 7892407133 5375506713 1921362803 7304525540 5413981551 2272887877 5000263434 3692644985 7085793088 6496617324 6473163789 0650930861 0797626153 3496056255 6390975715 2130130626 5481382159 6933991653 2149875884
• v= 2795858 5946753231 2067336792 5795079024 1245775224 7686675912 0177403617 8904460331 7038059640 2315459312 6832298203 0721507544 9841524835 1264011161 4910107649 5494419851 8071724331 6734674221 0910316553 4363560447 8573328843 9788124976 8425244797 1769853626 9702160314 6822408198 5618442334 8561703403 4172391850 1612121740 1365671087 7214165674 2052055698 4469564214 3343973704 2863371146 0647457119 5004177180 2328972907 5845734779 6449504961 7972686773 4907335179 3717814696 4802276459 1113027065 2871382897 4407569117 5592782295 1097624305 9227588858 5658065961 0239248626 1830065734 4427862473 7883468799 2492803382 2945926178 2454267668 5812367570 3878093390 7329381396 7508472612 8172008655 6856637699 7295762899 7337193968 0323377525 8372826006 9753902117 7282894070 7780635638 4567455744 7211448395 5920120979 5185096869 1731102421 4321339557 1334378492 7263025601 9594165826 4866820036 8630984251 3738841175 8837274928 6685858245 8438196889

We also need to calculate d = floor(c₄·v/F + 0.5) = 12343589 0427661894 2150569501 1063830550 6140378776 4681494642 1299405361 2353021788 1377880298 2299292189 2848537997 9652665360 1749216227 0711101794 2335388556 4134737917 5127385087 5220008258 4270586922 3480969648 9825517302 2630285624 8319594214 2178913472 6627048648 7673783218 3174322433 9573035949 5066034659 7236044064 5598262686 4330085375 2997974896 1037359399 3377391041 9089757559 1045069606 1574184551 7491402050 3718468616 0325405361 0295666286 7373524261 5876811260 0936474252 8010415343 1211657625 9556133221 8904653551 9414126621 5948852269 3291278433 1031722713 5482081180 5916162584 1172089073 6524031518 8072105291 2922265901 2560218924 0816163386 9827918700 3652684673 5372960843 3290228453 0086019828 5972767438 7822203920 2240871241 4054002832 5352098976 2254517747 3702172072 4767437059 7180239355 9955635985 0806048899 4746132739 2941367055 1121823928 8732079851 2210808111 6251044314 2318537641 3229978262 7526550176 6681480242 7095532088 9191753111 6118567910 6228986022 3824885923 7159105140 4140973784 4139070130 9777097470 2654592723 2175253212 3178874041 0287208961 4841597880 7831062613 5297259156 6806870474 4019907882 3918847103 4169902063 7672891107 1743606226 0305590817 9519589322 6637768434 8754325427 2704817635 5457319440 8380836565 9222720835 4829379959 6221440964 1134314335 6522228252 9309150214 0380595119 2487562586 8862500911 3970330359 2821980018 4330262050 0279226073 7747221295 5735286841 5071591701 2480334926 4165718861 3070989832 9608849542 7435458707 9846632865 5902316000 3639779041 7328775648 2986826849 5042170291 4539208596 8512874728 6459325987 8052524933 6176884665 2396359274 4312766286 3823376013 1314827967 9057101078 3217518079 5188164720

Cubic Polynomial

We now consider the cubic P(x)= v·x³ + (u·F-c₁·v)·x² + (c₄·v-d·F+u)·x - d, which we express as: z₁·x³ + z₂·x² + z₃·x + z₄, where:

• z₁= +2795858 5946753231 2067336792 5795079024 1245775224 7686675912 0177403617 8904460331 7038059640 2315459312 6832298203 0721507544 9841524835 1264011161 4910107649 5494419851 8071724331 6734674221 0910316553 4363560447 8573328843 9788124976 8425244797 1769853626 9702160314 6822408198 5618442334 8561703403 4172391850 1612121740 1365671087 7214165674 2052055698 4469564214 3343973704 2863371146 0647457119 5004177180 2328972907 5845734779 6449504961 7972686773 4907335179 3717814696 4802276459 1113027065 2871382897 4407569117 5592782295 1097624305 9227588858 5658065961 0239248626 1830065734 4427862473 7883468799 2492803382 2945926178 2454267668 5812367570 3878093390 7329381396 7508472612 8172008655 6856637699 7295762899 7337193968 0323377525 8372826006 9753902117 7282894070 7780635638 4567455744 7211448395 5920120979 5185096869 1731102421 4321339557 1334378492 7263025601 9594165826 4866820036 8630984251 3738841175 8837274928 6685858245 8438196889
• z₂= +53280114 0966503950 7948308221 6125477140 7073468065 6883631534 1130629213 8795021597 7975939074 7911627161 9845794430 9147542418 0830531483 2823818682 6331229236 1225356979 4589223409 3545048861 5350421086 3697721880 2301920697 5846573236 5106375404 8249576363 6333464563 3901233925 7357965369 3482937590 5985504471 4919536350 4096146075 3093832338 9030127936 5680854131 1575268334 7766678076 6760693517 2608703916 1466007202 9324515011 2549785496 8059323396 3268399925 7171973732 6118849489 8783391173 9983196716 5625812192 6153336104 4791950150 0088028071 9557756322 5919729045 7522056462 9649375376 4613861189 9749464894 8388764484 0250525125 0265154867 4182756152 4272133239 7436088915 4608211719 0319572898 7726550793 8248438057 8491627662 3549806825 7709292784 7721247458 3883838316 4388517432 1788057107 3652749175 6096966265 7536168356 0655564607 4827416871 4145963983 9582226444 2005685926 9996292717 6287766794 3762170927 5369598337 4911889912 4830709957 6919757589 1810241878 5075132090 1907077003 4985024337 7883479502 1156610846 9733913038 3640982711 0995573452 5415803209 2046659323 4602715789 4640220753 7955963075 7655111577 5175537281 6424378056 5037717639 8827118439 5947781625 3377546676 6711590134 2313694714 8675161837 8028596845 1111636246 8508220912 6294122428 0450231068 8102691020 9517525420 8721747780 2262772800 4263251680 0468028252 6570034732 8880765929 7508439842 1749976425 9011500182 4925232304 6310497597 4931571310 1387238378 2178246469 7206731147 2555602762 9916292493 7557550405 1832073703 3306557153 0019198931 4748710461 9021376388 6558223873 3761735267 7107007328 0206338845 8613047837 1074505402 4800044018 6903363506 4943515778 4538414538 8428171246 5418739759
• z₃= -103831 9320881338 4514697155 5518725805 6962378697 2385909246 9183906182 9691710570 8371299130 7593074668 2374137165 1010380806 8604302798 7557213187 8542171762 2182036353 8526237033 7752115485 6313364578 2850651458 7972954522 8460499792 3758206371 7647340835 2050388534 0502856013 0338676443 3242743900 1729338317 6193629399 5798815716 7589909759 2081745500 7773400049 8128827601 6980155894 7063349699 3817814716 9062913077 8516150519 1736044241 4040299671 6088970765 5454534218 8355864464 9152653106 1645496392 0997007393 0436864799 5756108832 4750520971 9187294504 8707298845 7437826388 7818297500 4229568681 9009422546 6873113303 3884480857 8583209338 5503660537 1206597256 5784009121 0886600897 4831122866 8928929505 4499105234 3957231576 5710017599 5533649322 4242818127 8906184582 7794890743 6721366004 4249832594 2742428449 1221422031 2854819266 3624512021 4294451453 9163357864 9538606417 1877639275 8256872374 8561733887 8806722316 7281474845 9165868372 1384892818 0010880614 0576820085 5893550660 2576487223 0890255411 5927749013 3992207037 5276223062 6643288778 9785965090 1304213596 4342462630 4921165635 7820933760 9960461114 1673107882 0137554981 2752169837 0358900700 8596809395 7561566093 5989663657 5619705753 0569236836 6012848562 9880102821 0259451517 1441255767 2325387797 8213552994 6405803487 7824570607 0111220727 6189323793 3560803316 1505403626 9189062713 2079878180 1755090447 8758346881 1037432897 1251088663 6708747109 8886693722 3660100238 4616617811 0816717407 5457084716 1118776424 0458541728 2560516633 2746514617 1114593036 5578181188 6863642750 1694878686 9114004675 2347790334 5136529181 1791507073 4467292566 3834364987 9841089175 1759268435 6462250785 4195670606 7539996069 7020315571 6356500109 8182191460 8874548530 3353901786 1163186077 7848204122 8957051476 4393292498 9232228349 8050796567 0235349052 7277793173 6962576450 4698371416 5277180285 6748687601 8924188673 6477429744 5651307100 0944942450 6861029363 0215282107 3459640401 7494663691 9471359361 7014790105 0040358117 4089644192 2853568351 7953505828 5676104922 3154360677 9902016241 1746185969 0217354019 5966792085 5939860116 0717780902 2155345296 9743409097 8331473857 6695379614 7107393044 3355352220 1326281035 4389344704 8854981224 2656442365 5100901013 5893493927 3681178796 5398917054 1776525829 1871937039 0503175256 8027593307 6446134860 4678187654 3998150097 6150969937 0959749884 5545708021 6932140090 9745356445 2647695110 4715864374 6325855677 9064444660 8281858065 8080810043 5021790671 3384483322 1104375914 2460051524 7226186361 0298486109 2945029997 1006546804 8965617801 9930557261 2109810075 9357920139 2161909163 7591184915 8977449968
• z₄= -12343589 0427661894 2150569501 1063830550 6140378776 4681494642 1299405361 2353021788 1377880298 2299292189 2848537997 9652665360 1749216227 0711101794 2335388556 4134737917 5127385087 5220008258 4270586922 3480969648 9825517302 2630285624 8319594214 2178913472 6627048648 7673783218 3174322433 9573035949 5066034659 7236044064 5598262686 4330085375 2997974896 1037359399 3377391041 9089757559 1045069606 1574184551 7491402050 3718468616 0325405361 0295666286 7373524261 5876811260 0936474252 8010415343 1211657625 9556133221 8904653551 9414126621 5948852269 3291278433 1031722713 5482081180 5916162584 1172089073 6524031518 8072105291 2922265901 2560218924 0816163386 9827918700 3652684673 5372960843 3290228453 0086019828 5972767438 7822203920 2240871241 4054002832 5352098976 2254517747 3702172072 4767437059 7180239355 9955635985 0806048899 4746132739 2941367055 1121823928 8732079851 2210808111 6251044314 2318537641 3229978262 7526550176 6681480242 7095532088 9191753111 6118567910 6228986022 3824885923 7159105140 4140973784 4139070130 9777097470 2654592723 2175253212 3178874041 0287208961 4841597880 7831062613 5297259156 6806870474 4019907882 3918847103 4169902063 7672891107 1743606226 0305590817 9519589322 6637768434 8754325427 2704817635 5457319440 8380836565 9222720835 4829379959 6221440964 1134314335 6522228252 9309150214 0380595119 2487562586 8862500911 3970330359 2821980018 4330262050 0279226073 7747221295 5735286841 5071591701 2480334926 4165718861 3070989832 9608849542 7435458707 9846632865 5902316000 3639779041 7328775648 2986826849 5042170291 4539208596 8512874728 6459325987 8052524933 6176884665 2396359274 4312766286 3823376013 1314827967 9057101078 3217518079 5188164720

We need to prove that this cubic has no integer roots r such that r·F+1 is a non-trivial factor of N. Clearly r (if it exists) must lie between 1 and R.

The real roots of P are:

• -1+ε∈(0,1)
  (Root is not an integer)
  (Root is negative)
• -19271 1604119924 2934155124 8646225961 1859376343 8510448465 4936485835 6827753467 1359091849 4306302132 1292186304 8834716844 8912262467 1787740913 2607826387 8593532930 8278056909 3559307475 2818487007 6229444143 5730688392 2789655640 4520122126 0179525054 8328593282 9732808630 7674790829 9761421787 6630961243 2359346669 3864232495 9918252414 4649801733 9373219888 1699939305 9099422517 7905575430 3007085959 5298741870 4835755511 6634010230 3288110556 1925419789 1129104406 1554164284 4670957090 6039361242 5239608679 5903233881 2812409843 2118988089 2971049200 5199579791 9021065666 2816030927 9060448702 3511188586 9328944064 3169467026 2658293625 8953076358 5386374629 3319777800 9726176175 6684331932 3614352844 8974040730 0906231800 5620499897 5788388387 6361458516 0917902594 3598462631 9142979966 6632322264 4880966809 0248429980 2702608532+ε∈(0,1)
  (Root is not an integer)
  (Root is negative)
• +19271 1604119924 2934155124 8646225961 1859376343 8510448465 4936485835 6827753467 1359091849 4306302113 0724200505 7386584527 3871735462 0570401023 9612081102 3891652342 6324013677 4880236800 1702695850 1847475930 9964436888 8801203179 4111298467 5238283084 1864554157 3803947827 3578263856 0473273890 4959987893 2752259008 7543830094 4759841906 1013079866 7724116525 5882679993 7932427149 8049092646 8217959588 1987102302 7375220717 9658590889 6917454853 8185035340 9600480518 3932241038 6018517845 4155717485 4347658422 6469867404 9158568612 0304178974 3278867491 3067918979 0181732068 9031094551 4890699244 4485422844 3077514599 7968071350 1632787506 9322700338 1429387039 0138002682 4731047671 0077124588 1818110017 0020487751 3580857341 9739692885 9874493733 7997086031 8626673468 6398578706 6749413451 8354914692 2990827495 1161266582 0309253573+ε∈(0,1)
  (Root is not an integer)

There are no integer roots of P in the interval (1,R), so the proof of primality is complete.