Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: cotpi 67 - Composite factorial plus one
Replies: 7   Last Post: Mar 10, 2013 4:19 PM

 Messages: [ Previous | Next ]
 Mark Brader Posts: 88 Registered: 12/10/04
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, aleph-null.

Wilson's theorem states that if p is prime, then (p-1)! + 1 is
divisible by p. If x > 3, then (x-1)! + 1 > x. Therefore the
desired property holds for all numbers n > 4 where n-1 is prime,
and there are aleph-null of those.

Wilson's theorem follows from the fact that in modulo p arithmetic,
for prime p, the integers from 1 to p-1 form an Abelian group under
multiplication. Therefore, modulo p, the value (p-1)! 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 p-1
elements, we can cancel out any pairs that are mutual inverses.
Therefore, modulo p, (p-1)! 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 m-1 is a multiple of p. But m is in the range 1 to p-1,
so the only possibilities are m-1 = 0 and m+1 = p. In other
words, m = 1 or m = p-1. Since we have an even number of factors,
both must occur.

Therefore (p-1)! = 1(p-1) = p-1 modulo p
(p-1)! + 1 = p = 0 modulo p

Or in other words, (p-1)! + 1 is a multiple of p. QED.

By the way, if n is composite and n > 4, (n-1)! (and not (n-1)! + 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."

Date Subject Author
3/7/13 cotpi