A beautiful but unpractical primality test

Wilson's theorem is the statement that an integer p is prime if and only if it divides (p-1)!+1. (Here, (p-1)! denotes the factorial of p-1, the product of all the integers from 1 to p-1.) The result was known to Leibniz, but it was only published in 1770 by Waring, who named it after his former student John Wilson who had rediscovered it.

Factoring n!±1 into primes

A related lesser-known result is that p is prime if and only if it divides  (p-2)!-1.  This is a special case  (for k=2)  of a generalized version of Wilson's theorem, which states that an integer p greater than or equal to some positive integer  k  is prime if and only if it divides  (k-1)!(p-k)!-(-1)^k.  This general statement can be seen to be a corollary of Wilson's Theorem itself  (which is the special case  k=1):  It suffices to observe that,  modulo p,  the largest factors of  (p-1)!  (namely, p-1, p-2, ... p-k+1,  assuming p ≥ k)  can be replaced by  -1, -2, ... -(k-1),  so that  (p-1)!  and  -(-1)^k(k-1)!(p-k)!  are actually equal modulo p.

For any prime p of the form  4m+3,  the generalized Wilson's theorem with  k=2m+2  says that  p  divides  (2m+1)!²-1  and is thus a factor of either  (2m+1)!-1  or  (2m+1)!+1  (see A265643).  We have "trivial factors" of numbers of the type  n!±1  only in then and in the case of  (p-1)!+1  and  (p-2)!-1.  Other prime factors of  n!±1  may be quite difficult to obtain,  as a casual inspection of the factorizations below will suggest.

  0!+1 = 2
  1!+1 = 2
  2!+1 = 3
  3!+1 = 7
  4!+1 = 52
  5!+1 = 112
  6!+1 = 7 ´ 103
  7!+1 = 712
  8!+1 = 61 ´ 661
  9!+1 = 19 ´ 71 ´ 269
 10!+1 = 11 ´ 329891
 11!+1 = 39916801
 12!+1 = 132 ´ 2834329
 13!+1 = 83 ´ 75024347
 14!+1 = 23 ´ 3790360487
 15!+1 = 59 ´ 479 ´ 46271341
 16!+1 = 17 ´ 61 ´ 137 ´ 139 ´ 1059511
 17!+1 = 661 ´ 537913 ´ 1000357
 18!+1 = 19 ´ 23 ´ 29 ´ 61 ´ 67 ´ 123610951
 19!+1 = 71 ´ 1713311273363831
 20!+1 = 20639383 ´ 117876683047
 21!+1 = 43 ´ 439429 ´ 2703875815783
 22!+1 = 23 ´ 521 ´ 93799610095769647
 23!+1 = 472 ´ 79 ´ 148139754736864591
 24!+1 = 811 ´ 765041185860961084291
 25!+1 = 401 ´ 38681321803817920159601
 26!+1 = 1697 ´ 237649652991517758152033
 27!+1 = 10888869450418352160768000001
 28!+1 = 29 ´ 10513391193507374500051862069
 29!+1 = 14557 ´ 218568437 ´ 2778942057555023489
 30!+1 = 31 ´ 12421 ´ 82561 ´ 1080941 ´ 7719068319927551
 31!+1 = 257 ´ 95101 ´ 3038779 ´ 110714485281307653167
 32!+1 = 2281 ´ 652931 ´ 61146083 ´ 2889419049474073777
 33!+1 = 67 ´ 50989 ´ 175433 ´ 143446529 ´ 101002716748738111
 34!+1 = 67411 ´ 4379593820587205958191075783529691
 35!+1 = 137 ´ 379 ´ 17839 ´ 340825649 ´ 32731815563800396289317
 36!+1 = 37 ´ 83 ´ 739 ´ 1483 ´ 165202043 ´ 669043459524628666916941
 37!+1 = 13763753091226345046315979581580902400000001
 38!+1 = 37280713718589679646221 ´ 14029308060317546154181
 39!+1 = 79 ´ 57554485363 ´ 30705821478100704367 ´ 146102648914939
 40!+1 = 41 ´ 59 ´ 277 ´ 217823 ´ 16558103 ´ 142410167827 ´ 2370686450613664429
 41!+1 = 33452526613163807108170062053440751665152000000001
 42!+1 = 43 ´ 70552493296669 ´ 463124113000222170026612414799459103
 43!+1 = 59 ´ 17939 ´ 21154320865805720609 ´ 2698344166510526940628578689
 44!+1 = 694763 ´ 9245226412016162109253 ´ 413852053257739876455072359
 45!+1 = 293 ´ 19789544034049 ´ 20630438210640397406279590400959696408493
 46!+1 = 47 ´ 435777793891607546778854755077304349 ´ 268662306503771535067
 47!+1 = 6007711 ´ 168070783 ´ 8515115894538293 ´ 30079854505971876191439276989
 48!+1 = 12893 ´ 962841510318473021861652760984516795045488742315811680757
 49!+1 = 1021 ´ 18503 ´ 7374967 ´ 3119969417 ´ 1399350666311484138193855597641025027693
 50!+1 = 149 ´ 3989 ´ 74195127103 ´ 6854870037011 ´ 100612041036938568804690996722352077
 51!+1 = 71 ´ 103 ´ 733 ´ 6874997 ´ 1098482930441153 ´ 38315956787932342928312981705927301809
 52!+1 = 53 ´ 24324571 ´ 102410729 ´ 610916528722361633211914873895453040312819385683663
 53!+1 = 9293 ´ 604781 ´ 4757108478032284831087 ´ 159892145824643749201959875233364609431
 54!+1 = 12318573951317236818169524329 ´ 18739482203989776313317892180295929612279769
 55!+1 = 79 ´ 160713966502003492733735453766664771640257228499359959016149873417721519
 56!+1 = 55921523591 ´ 34952079265361 ´ 6906986766519639105975269 ´ 52665729267391392637197179
 57!+1 = 6323 ´ 281345933294341 ´ 22781366449491833749436362099116893397662110046451717211007
 58!+1 = 59 ´ 1307 ´ 6317 ´ 4825397681959307284906438227649931194311387678100884795994191194421581
 59!+1 = 16567 ´ 8371045967627804414676104286858779884463262918614561027393088364831291120903
 60!+1 = 61 ´ 9817 ´ 2217171747715476312877 ´ 6267103793993243547285077748231038650731526237293398449
 61!+1 = 71 ´ 227 ´ 48795702665964504883 ´ 645414773564183033631788833426015066505798100758905144895791
 62!+1 = 6379 ´ 159138408328588807223026973 ´ 31000504511542092799005276648266961921468949729097323103
 63!+1 = 71 ´ 127 ´ 307 ´ 27500136871811311 ´ 26043636362337781302384310751994209467129440344704898500142621789
 64!+1 = 233 ´ 197576287 ´ 2756297915923095827221902140191122066448397728619813809969808497099669771849031
 65!+1 = 131 ´ 393517 ´ 80075971917165875585023393357 ´ 1997989681645398106846922380418145629618627948611363859
 66!+1 = 67 ´ 1061 ´ 18057624081136493013373 ´ 42607422767369562012435736497443 ´ 9952636204265093307383973691627657
 67!+1 = 309013 ´ 2087801 ´ 33161533 ´ 1704702278407371646375511238271849674158844998975781824666286808091671232969
 68!+1 = 4139 ´ 21388313 ´ 29434193 ´ 14843936037776927 ´ 64118704648885617584727091302889567756607068720311652835617813
 69!+1 = 83 ´ 4721 ´ 1550701 ´ 750680431 ´ 122508808173429896519927 ´ 3062276674867051896364411333357375603321849491783785711
... ...
  n!+1 is prime for n = 0, 1, 2, 3, 11, 27, 37, 41, 73, 77, 116, 154, 320, 340, 399, 427,
                        872, 1477, 6380, 26951, 110059, 150209 ... ... A002981


  0!-1 = 0
  1!-1 = 0
  2!-1 = 1
  3!-1 = 5
  4!-1 = 23
  5!-1 = 7 ´ 17
  6!-1 = 719
  7!-1 = 5039
  8!-1 = 23 ´ 1753
  9!-1 = 112 ´ 2999
 10!-1 = 29 ´ 125131
 11!-1 = 13 ´ 17 ´ 23 ´ 7853
 12!-1 = 479001599
 13!-1 = 1733 ´ 3593203
 14!-1 = 87178291199
 15!-1 = 17 ´ 31 ´ 31 ´ 53 ´ 1510259
 16!-1 = 3041 ´ 6880233439
 17!-1 = 19 ´ 73 ´ 256443711677
 18!-1 = 59 ´ 226663 ´ 478749547
 19!-1 = 653 ´ 2383907 ´ 78143369
 20!-1 = 124769 ´ 19499250680671
 21!-1 = 23 ´ 89 ´ 5171 ´ 4826713612027
 22!-1 = 109 ´ 60656047 ´ 170006681813
 23!-1 = 51871 ´ 498390560021687969
 24!-1 = 625793187653 ´ 991459181683
 25!-1 = 149 ´ 907 ´ 114776274341482621993
 26!-1 = 20431 ´ 19739193437746837432529
 27!-1 = 29 ´ 375478256910977660716137931
 28!-1 = 239 ´ 156967 ´ 7798078091 ´ 1042190196053
 29!-1 = 31 ´ 59 ´ 311 ´ 26156201 ´ 594278556271609021
 30!-1 = 265252859812191058636308479999999
 31!-1 = 787 ´ 992078233 ´ 10531763920894209415469
 32!-1 = 263130836933693530167218012159999999
 33!-1 = 8683317618811886495518194401279999999
 34!-1 = 10398560889846739639 ´ 28391697867333973241
 35!-1 = 37 ´ 71 ´ 3933440413546305645095794190149676437
 36!-1 = 155166770881 ´ 2397377509874128534536693708479
 37!-1 = 53 ´ 439 ´ 1477897 ´ 6154980127 ´ 65031782905798661084563
 38!-1 = 523022617466601111760007224100074291199999999
 39!-1 = 41 ´ 10949 ´ 99563 ´ 456382297346497242065582795509270897
 40!-1 = 9190813196017748117 ´ 88775091588350692405196340547
 41!-1 = 43 ´ 83 ´ 1040629 ´ 9007130444054254388333146158506038994899
 42!-1 = 61 ´ 59167 ´ 2168466907 ´ 179521319669577538815789355998017711
 43!-1 = 97 ´ 607 ´ 857 ´ 883 ´ 12829 ´ 1298793158431 ´ 81378920130420431538741649
 44!-1 = 61 ´ 1249 ´ 44189 ´ 789574111709935122272126584166271486133485319
 45!-1 = 47 ´ 8968109 ´ 29695723986343 ´ 320577203500987 ´ 29811688252483929593
 46!-1 = 83 ´ 6089 ´ 81701 ´ 10576808395865566718629 ´ 12599799004296237004505413
 47!-1 = 340777 ´ 758922232166983630476717487252989432881907031252461287
 48!-1 = 67 ´ 967 ´ 9820729 ´ 19510292675860209956429673079405264165083328290779
 49!-1 = 823 ´ 3739397 ´ 197653021455862028208110725148879567449727922627417829
 50!-1 = 3282689 ´ 9264993790673858548163596419296731686851127709314075137791
 51!-1 = 53 ´ 90247 ´ 287282678119 ´ 19967303570082360959561 ´ 56533717390894655271258971
 52!-1 = 61 ´ 9931 ´ 167381 ´ 315037 ´ 2524979485348891286379813822180999833635163328006337
 53!-1 = 97 ´ 107 ´ 34968116649159559 ´ 11778676866714840823122457847931873025136902779259
 54!-1 = 307 ´ 601 ´ 1297 ´ 30695366231 ´ 54106663006768609 ´ 580820088638435297220258151537490539
 55!-1 = 73 ´ 39619 ´ 277914269 ´ 148257413069 ´ 160494745883 ´ 663844342902787254323647363449542479
 56!-1 = 467 ´ 49033 ´ 1044371 ´ 6910291 ´ 4302414531215375138314576976741865404375389726537406069
 57!-1 = 59 ´ 15307 ´ 60821 ´ 197933 ´ 12154743613 ´ 306678926193685478942992979832598544037870118812547
 58!-1 = 3413 ´ 3181931 ´ 1134403433 ´ 951628008911 ´ 200497883843496861869458421995720554049114966991
 59!-1 = 61 ´ 2273493746650653044884246224924416497473817652011269385915103195740327868852459
... ...
  n!-1 is prime for n = 3, 4, 6, 7, 12 14, 30, 32, 33, 38, 94, 166, 324, 379, 469, 546,
                        974, 1963, 3507, 3610, 6917, 21480, 34790, 94550, 103040, 147855, 208003 ... A002982

References