
Re: cotpi 67  Composite factorial plus one
Posted:
Mar 8, 2013 1:13 AM


> How many positive integers n are there such that n! + 1 is > composite?
Infinitely many, or to be more specific, alephnull.
Wilson's theorem states that if p is prime, then (p1)! + 1 is divisible by p. If x > 3, then (x1)! + 1 > x. Therefore the desired property holds for all numbers n > 4 where n1 is prime, and there are alephnull of those.
Wilson's theorem follows from the fact that in modulo p arithmetic, for prime p, the integers from 1 to p1 form an Abelian group under multiplication. Therefore, modulo p, the value (p1)! is simply the product of all the elements of the group. If p > 2, p must be odd and therefore this is a product of an even number of factors. (If p = 2, the theorem is obviously true.)
One or more elements in any group are their own inverses; the rest, if there are any, form pairs that are inverses of each others. Since the group is Abelian, in considering the produce of all p1 elements, we can cancel out any pairs that are mutual inverses. Therefore, modulo p, (p1)! just equals the product of all those elements that are their own inverses. And since the other elements were in pairs, there are an even number of these.
For those elements m, we therefore have:
m^2 = 1 modulo p m^2  1 = 0 modulo p (m + 1)(m  1) = 0 modulo p
Returning to standard arithmetic, this means that (m + 1)(m  1) is a multiple of p. But p is prime, so this means that either m+1 or m1 is a multiple of p. But m is in the range 1 to p1, so the only possibilities are m1 = 0 and m+1 = p. In other words, m = 1 or m = p1. Since we have an even number of factors, both must occur.
Therefore (p1)! = 1(p1) = p1 modulo p (p1)! + 1 = p = 0 modulo p
Or in other words, (p1)! + 1 is a multiple of p. QED.
By the way, if n is composite and n > 4, (n1)! (and not (n1)! + 1) is divisible by n.  Mark Brader, Toronto  "Professor, I think I have a counterexample." msb@vex.net  "That's all right; I have two proofs."
My text in this article is in the public domain.

