Primality Certificate for (9096^2011-1)/9095

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 35.004210% 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.367909%

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 = 17 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₁= 17029 7312914849 9062416184 3887187848 3552951975 1154141574 1703380464 4498301808 6365575152 2279705099 9046424579 9369719786 1621468350 1848339104 8065894333 6259504696 7792812323 6764426860 2840255891 4263836076 8191973181 4476344172 9196619136 6404908208 4749382393 7554900170 1771713175 9824072480 7612731767 6481526643 5700301117 0005111903 1818268495 3004169829 8605776295 8260751884 9845236257 4998025298 1215306637 5353219858 2270044543 1179884676 4625071571 4644080004 7007005260 4473923337 2333172898 5257170245 3031593662 3982040261 3874881509 3994990858 2879843175 7323905506 2718361474 6759554934 7743803887 3799741021 3358928422 4878902734 2171608128 1878743101 1287539305 5706725440 9547762467 9203153971 3410512390 2322246252 6391046012 6110630360 1631555860 2290207127 6887447788 4278111428 2783640975 5555383192 4314134968 8451486237 6586553072 3257944389 7341410581 7547123481 4906789476 4711580876 2894610861 1630626467 1126242088 7035155087 1319537413 6108237433 4162189484 4638192859 2905569965 9771080213 7106714298 9077309113 5399592487 6618997035 8024212738 8390278551 5492176089 7400722989 6734599685 7429739992 4598640225 0543532766 8822714414 3321812227 1451053390 7672812521 3394492606 4227684285 3199331181 7764689554 5770615171 7866530434 6612002662 1489852743 0939802047 2610212062 5528126414 6795071627 6860900191 4713190276 6661667308 9252362141 8663028704 9437697591 3833281934 3790271985 4967632748 6371989733 0310601821 3438627794 4124988479 5236818176 5806915898 0912748236 5093736497 6285714537 5740752387 2293578184 4947326080 8347405931 7247386499 5141318058 6636745473 2804276845 8837669486 2434411908 9658428598 6967016622 0765707031 5188099394 3006948914 2001655934 6149583081 4785133643 2390550662 4105772395 5073593390 6681923087 9464978706 9908152001 2163512512 5097531766 4194950007 2353976681 7484153714 6034030100 1836938141 6776368311 5466302863 5706745600 2373587069 8588411695 3122507551 3459530223 2085066198 9831560187 7176572190 1392175353 5764290153 2156797090 3596798335 4637977059 4236750264 7800135560 9815903214 0032308230 3005244219 0853011483 5008854403 3825992888 6686693968 0042542922 1434918654 6559977568 8996673160 5580342326 2496372215 0976013399 6603570346 1179559919 9152392155 4115172956 3006151459 3750900456 1747462507 9853596699 9451085644 1522175727 8721336920 8894866169 3298141919 6509936445 8478552743 4948206021 7656019927 1696737903 0384504354 7617194952 4261354137 4160491260 3316128578 9843776021 9904416620 1357178951 2793992263 0322628982 8255605752 4166544478 3860544873 4593205228 0307015514 6432050317 6314421200 9630120984 3923642555 1554192810 5279228886 4292745080 4914368330 9241097259 3598688716 1750529082 4584163153 3204540681 6673181910 2976948245 6726878849 0462988998 3417169239 7033750928 8881956898 5547028787 4818356529 7981887154 8004213449 7607778273 2988440713 9346633639 6061184345 0268609334 2511188515 2923695641
• c₂= 8456391 2861223349 6415574255 4528939568 9499640786 0618505538 9604549076 2440772583 7156944856 1823624241 6358250283 5349425420 7798119890 2850941592 5073075080 8489784479 5882673563 0543332980 4234720911 2037973130 7197331869 1037031909 6338115915 7562770512 4031276864 6132909708 6205250845 3083339029 4018823251 4004365106 7536168736 1698504698 1728572257 9213355560 1475142118 7397260831 8112942410 9144593930 3207704745 8773372784 6773801374 4529532707 7762862521 3515289637 3532452471 8073815020 4914515817 1731790963 8366490946 1333833154 7603395655 1206139824 7913763842 9129412744 3047992494 3124105751 6301441104 9856503579 5766845305 8410652624 9899037749 0775773414 9941117098 8750061994 2789679802 1087952930 1082569591 1654377275 3746858671 9368258408 2213906911 2850485067 2080257565 3665502306 7269691003 1496795915 9882712811 6591351190 0581337424 2508758451 7803599486 5619081642 7309666453 3584019547 6865410714 0453613501 7093705217 4132845406 2914797470 9549810803 0339868569 3815357588 2935919343 7405080276 8115183685 4945935045 3128626349 0669376726 6915595674 6855019094 4931266152 9375177525 4069280353 0641333076 2921988493 4245403343 3807719594 5160122587 0822211429 7927093445 2856800240 6972512334 8842821187 3915815234 4478981180 6064739861 1345849767 3771447046 7016139390 5098359360 8254069796 1971436568 3604316888 8409075150 7504183484 1701880166 9586218764 7956688823 4829901189 1479409075 4927162947 0371717585 3258567655 3349754073 9010815571 4379970889 7382795143 4939649634 1525739636 9042317033 0227399889 3883603877 2181185477 0781681029 6935874592 8085100253 4305560683 3669169277 6274703158 1012580776 5088355777 4611377603 3757532862 7609575023 5980051015 0624455940 0883834670 6286993099 7386748565 9749573905 5101941027 2360057737 1480564833 0881074486 1690223078 5174913010 6360893105 5675079312 4624579709 1269337254 2763804529 0670795442 2936458011 2050460864 0893956379 6541406512 3696470911 3359722223 2895717627 7786957842 9395807664 1997642589 1989654677 0305490034 7079071872 7407857651 1953049921 2261205025 5716646111 1981502151 1879986884 0577460777 5987878921 4991921134 4935024478 4973820196 0010518666 6282880033 2458613891 3633563317 3103752356 8557090615 8956433513 6995784479 9677539305 2267557998 9770617581 8870758924 1028338603 3809613568 3809999208 9939953565 1909407236 5069938725 7088692083 5396801715 1623389945 5133513929 3836640517 7760116083 8497871495 8556910208 2365591735 1570771739 9457850508 2167575523 2070702736 0978969267 0334162032 6833740457 4117603397 3699861117 5318110267 9608767683 9184408816 1880546462 0490397848 5878472355 8436124352 6364198228 1862485281 8658470036 3860870159 3937785965 9757559462 4468054061 4297182600 2833756717 1421123374 6507447486 2048197062 1539698973 4277617428 8721077643 3463595852 1939349893 3112807545 7119986965 4216133349 5357658904 0709494974 7994018856 4793329888 4306511743 9595473453

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 ≡ 61 (mod 64) and therefore cannot be a square and N is prime.