Primality Certificate for (7568^3361-1)/7567

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 33.737780% 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 ^1/3 :

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

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

Express N in base F

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

• c₁= 1702101 7620681330 9605676790 5694796498 6481557764 4030150281 7399383669 0660704815 2830151245 8930485395 4678337716 2145171920 5451357609 9929421482 5849458182 6074555005 3409964411 2550429972 8895650516 2093915511 1197829054 7379576401 8742598687 3758091079 7730627396 8034566990 9259511112 8597788323 6346101183 2307766227 3382170026 8781607145 2261746100 4070053922 5254570541 9292907966 6249841628 7405233209 0595458800 4026759712 3190490818 6028488660 3338754691 8102103538 4668073691 2887378171 9324595184 2243600047 0107256058 6474470207 5372516627 9830124678 4681588763 0294105661 4779271054 9993409890 1801799485 8398191056 9354020655 8697484771 5521942686 7348205671 8393516777 9323805431 1323881709 0548163541 8732524190 0052686214 3164152754 6976309167 0411643037 8759006342 7287686260 8710476634 4112086807 8268251229 4555563645 9288858607 7144635315 3751910838 2636930828 2144843657 2848669225 1051132702 1520870438 8170411222 7372772170 4541110468 0737573387 1231788567 7684324443 3626273100 7056636261 2938605904 4630302664 4523932325 9815389377 3541339191 9429780658 8399444539 2377402466 4423427233 0138178928 6511845234 5540705655 9279771755 2335361057 6200601859 1041097034 9006116571 4010120689 7459700682 1988779338 7100544846 9515776552 3743780704 5701079518 1610091655 1947132891 3115169639 0919912687 3400090074 7215884080 0605223857 2236897219 5110491695 9744610504 4500495003 3254916220 7133680393 1000142023 2125065856 2939026296 4464912389 9409088088 9191598920 9079226023 9035054854 5854361628 3368200003 3002836678 6807039297 4704827330 2507554792 8454486776 8583795423 4290222554 1837261342 1486037442 1481948267 4221017622 9950698718 7085461825 0282324264 6994140287 8999758242 2891076730 1657392442 3363719696 0933214595 2095781784 5906064771 0462076661 1561538325 0874455063 4935402353 1459695365 6709521249 3025146221 9122625901 1731823943 0261110731 0320000567 7004651195 2513020672 1854980252 6129599415 0503022850 3783412636 3471961323 1183609051 2593127194 2793114344 5509820488 9423323731 0934999614 0830816998 5926595289 0437611823 3193204109 7045033621 7122010838 4040270729 9112945420 4303423620 4220741601 0506264304 0177296983 4258426473 6027568725 5293044056 4413572892 4864655931 6578396780 8812046127 2124708376 1165860703 5145082518 9961803312 8122937316 8050910463 5601675694 8154898874 0871707044 8014556989 1921870923 9347775697 2129745919 1906940748 7485561096 6077161282 0363590428 8959081894 7369928578 1646492974 9483038323 8519142386 7692596455 3130958566 5500489853 2827186297 9744358394 4947555750 4596336073 3997465979 6889632886 4388078916 1359065223 2368091921 0325494086 0239397916 8549385094 7280349470 9597815401 7058808636 7192274172 0836346213 7594708873 9571963277 8461551913 2879669353 6621858622 7998542979 9542332897 2171111228 8799949385 5002333438 7483459937 7496308355 0312528384 7388504187 1718649799 9669731864 5019264705 8227672730 0824060293 5705963349 1557158923 0355622550 0703481521 3401068699 7898427362 7225430908 6474386765 0622086901 5089663364 2662792443 1338853031 6183259259 5104610241 9891566167 2545234941 3373504127 7027256828 6250819388 9173892225 6189069897 5194130621 5049812852 1952181911 8621234576 0562615617 2110798486 6583448772 6712930744 3337613477 3884954260 6666656705 6297585260 4104509462 5743450299 4096575934 6788683249 9469035489 9599020812 2437128321 6409118331 1085532826 4742290355 0504660813 5148494429 4594218411 3407975700 4901439905 3482758330 4097843732 8180800591 0332315966 4395680506 7336204041 1034223400 6720276138 7014285297 9171462014 8402712653 3336345214 4189453828 4474289403 2465222114 7039540847 9775753410 1894801709 7887982186 8343554305 4461409851 8180435034 6945165271 3925656827 8926758383 0730270918 8577493467 3555563519 3017499023 0982418662 0183509258 3023164131 1210802070 5917304794 0536617650 8904285398 5799438513 7369992864 7720704424 7901333856 5797128568 8418430408 6090305388 4264145920 8543214138 4363139543 5326248283 4786449418 4312213338 5939714918 9104167568 5588341810 8823238466 1801414685 0716900880 0918497967 2202259151 6523854346 3837682666 3559556801 9080694076 0995596649 5769980724 8701451752 7264903593 1740153549 9332268491 3427437405 0428894475 5697133302 0220541138 4077622214 0697877609 9066484271 8711379385 1561461483 6287248979 7742682106 4368544741 7327079845 6547139629 3204061559 5957666584 0135829029 1682279418 6436598700 3823234261 6108586055 1672513386 3824713782 2122604175 6701938268 3950676943 8888555313 6101137957 5270620023 7769685527 0001921940 3272880488 5684660442 3043135809 4048313981 5781120757 0372170581 9479074966 6185350898 8690188822 7200800875 5030966206 4022846194 3063519817 7291676714 1665880240 4219094486 9678763861 6004637961 2773186450 9263020265 6982559515 8165082339 0977620955
• c₂= 2 1583287918 4533969205 4170155739 4087555316 5851422662 7506672731 0489584676 4173531165 3297980039 4471068268 3600357924 0371814851 7739216155 4595255643 7545114816 7135061074 5193111066 7057022144 6115163678 2834385896 0328826659 9795071226 1924440556 7543730241 8393278494 0715989710 8404844263 3971733824 2303844485 2532945650 1212874406 7733450186 5300818735 1562314041 3084701402 4881476337 8960803329 3874006552 6812518258 8039069777 1925510506 5752533409 1607976789 1619595995 1198341753 6011043357 6675092049 9834049274 2450267586 6766023910 5214602199 9890978649 0212839612 7216821476 5336003299 6684968407 3182736698 1312110285 0804754438 9465946534 2185472497 4833497687 5886733110 3529014279 4011570290 1153128566 6595802523 3838727719 6180944087 2918592802 0516382406 1720764268 5564378243 1786065061 3879814616 2335247374 1177097438 0312823449 5052149045 0350861113 1373806754 0910224990 1440044569 0108473648 9039327344 3125999935 0965931690 9014867076 4044329070 2587912761 1731712901 7186072007 9186320761 6793380094 5601917247 1063050726 5441582799 2651075959 6157889122 7492757768 5204769282 0579978919 7494963673 7387007383 4048712182 1377056162 8730925768 2800493780 9906994436 7834671121 9326706577 2592950861 7553861864 4843585609 1890589040 8032160272 6769444639 5833429187 6386317551 5987854259 0005687179 4234398132 5780476182 7117577470 9825195481 3608619960 8989825237 3070946441 8959237758 2160687796 8574718686 8241882733 7855384466 0517695156 0843612930 7041130761 6180023879 1872222190 4814903737 6004762467 1902312156 3106883178 6673302756 1127867972 9003654028 3872415145 7527058655 8986077358 7084131826 7607641059 1392199509 4888528946 7300765350 9641505947 1271925988 5212955810 7859620986 1949376233 0398176980 0733362793 2817345780 4517366830 1502646941 6146069360 3288439396 2658898058 7563787560 1044219183 4957736798 4002705932 6929277431 2864508556 9813812811 6194757209 9375018305 6209071645 5346350482 1380326472 1063354316 0338562643 1842603122 4797840262 8485448738 1812302400 2341169042 8240942446 5536480528 3285988239 5252019635 5698476052 4600871732 8055849750 2978653166 9476121257 1963600275 1889509628 4286286691 7108085275 7463177433 1830786688 1291502524 4214437214 2210851896 7024523669 1408562330 1323139722 1729680661 7246822676 9456847050 9787222892 5786560706 7720769018 2985886418 5285797306 8275197452 5979683937 0802345265 7583346894 7687410576 5897750514 9522866047 8906209824 0558240469 7064830669 5489609491 2916266662 9160652348 2045055161 0722259319 3841727304 9355532255 2537643927 3521621370 6265146602 2961119594 5654407553 7970934846 4236725435 2602110054 6427004032 6302485955 1637859155 6745376028 1946516204 1882037343 8042104698 2161173601 0206996855 0680607134 0255560596 4126898804 4575739263 8132947515 3160613349 9648451647 9180678090 9775170683 5934396835 5429952504 5985494588 8560048546 7408396296 8110604181 6628362998 5453749777 9790538432 3330327467 2229712278 3507922943 1901328193 3549957747 6152852491 2757627873 2500545819 1104521246 3446983261 1381990361 8567682334 7951226524 8589698838 8178474198 9133479460 5862976823 9149525789 0686981669 5883737123 7923193194 7668419569 9235226507 1458802851 1376161818 1583610178 9726290824 0385895688 1370736998 1960932459 1308353567 8413477321 3280436965 7100024619 7609361562 1039451221 2663056834 6982057976 0841805510 4193432028 9509794551 6771720229 7069095811 0035126738 3540208956 0106516776 9002686113 5311746262 9033058608 2615572851 1062785584 3095487380 0982408264 7981758248 4629022175 7576632570 1458176917 7394304224 8917715497 4722757305 5653053887 0986950080 8655693919 4203957319 3003835816 2355683158 1225528640 9499781202 3532305167 2106472699 6288202882 0896253120 9306229052 2275758538 6632746216 7289923442 2668972457 4660900616 6043067363 0847368810 4714227155 4487658503 8587564321 4694588067 6674690125 4134102908 3734526390 1626677717 1025828670 8541480063 4847844021 3368816653 9848299928 3227405283 0462097032 6965539276 0279342087 6975793783 8424651079 0180292414 9721249565 8750666809 2820620773 3525824848 3188449887 7469100949 9560068278 0574725522 6278220203 0771641012 8535771712 5067409929 1565676946 9333794146 5780898540 9170680300 3700104630 7330662470 8051531247 6470535822 2849590832 3201286668 9267297600 1154824351 1428492873 1032225937 3585369055 2179334472 3947050726 7445891006 0775434753 4795457246 0580428895 4699274553 3992121487 7920968186 8994357090 4616980525 3630285491 3249081020 7200949529 7000137630 6110893454 0100616858 8686853093 0255232981 8533960026 2602048114 5302400450 1410052487 1622615247 5691845697 2547454447 1666673696 7235161983 2970203882 3121909678 9178653199 9690189535 2456508996 9094333255 7942033543 5669839917 3345535936 3032575527 6253924551 4224212069 2310147715

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

Here, c₁²-4·c₂ is ≡ 13 (mod 64) and therefore cannot be a square and N is prime.