The Math Forum

Search All of the Math Forum:

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

Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   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
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

> 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." | "That's all right; I have two proofs."

My text in this article is in the public domain.

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.