From: rgep@pmms.cam.ac.uk (Richard Pinch)
Newsgroups: sci.math
Subject: Re: 27!+1 is prime?
Date: 2 Mar 1995 10:24:34 GMT

In article <3it7i3$hkt@jupiter.SJSU.EDU>, alperin@sjsumcs.sjsu.edu (Roger Alperin) writes:
|> My 1964 edition of Sierpinski's Elementary Theory of Numbers 
|> says that it is not known whether or not 27!+1 is prime.
|> Maple says that n!+1 is prime for n=27,37,41,73,77,...
|> Has anyone proved this.


Here's a proof that n = 27!+1 is prime, generated in a few minutes
using Pari/GP.

n-1 has distinct prime factors 2,3,5,7,11,13,17,19,23.  The following
table shows

q    c = 37^((n-1)/q) mod n        gcd(c-1,n) c^q mod n
2  10888869450418352160768000000	1 	1
3   9354010963973492916993512414 	1 	1
5   1351012516026499070653830762 	1 	1
7   8062813045304944797369771039 	1 	1
11  2463733209014077207278496857 	1 	1
13  6407268961794741702710273269 	1 	1
17  9053361352312001957951455964 	1 	1
19  8356926485141789229660494702 	1 	1
23  3827781173633570643166605750 	1 	1

which shows that 37 is an element of the multiplicative group of Z/n
of order divisible by n-1.  So the group has at least n-1 elements:
and that shows that n is prime.

Richard Pinch;	Queens' College, Cambridge