Proof of the Compositeness Theorem

Date: 04/10/2005 at 16:44:25
From: Lori
Subject: no primes in the interval

I have determined that there are no prime numbers in the interval   
[n! + 2, n! + n], but I am trying to make sense of why.  Is there a
theorem that explains why this works?

My only thought is that whatever n is, it is always going to be a 
factor of the numbers in the interval.  Am I on the right track?

Date: 04/11/2005 at 09:06:35
From: Doctor Ricky
Subject: Re: no primes in the interval

Hi Lori,

Thanks for writing Dr. Math!

The property you noticed is informally known as the "compositeness 
theorem."  And as you have seen, it would make sense to be called 
that, since the theorem states that there are no prime numbers in the 
interval [n! + 2, n! + n].

To understand why this property holds true for all n > 2, consider the 
expansion of n!.

  n! = 1*2*3*...*(n-1)*n

Since n! is the product of all numbers less than or equal to n, if we 
add any of those numbers to n!, we can factor out a common term.

  n! + 3 = [1*2*3*4*...*(n-1)*n] + 3 = 3[(1*2*4*...*(n-1)*n) + 1].

Therefore, in our example, since we can factor a 3 out from both n! 
and 3, then 3 is a factor of both and therefore n! + 3 is composite.  
We can duplicate this factoring argument for every integer we add from 
2 up to n.

This is not to say that n! + 1 isn't composite (note 4! + 1 = 25 is 
composite), but since the primality or compositeness of n! + 1 can 
only be considered on a case-by-case basis for each n, it is easier 
just to say that all the integers in the interval [n! + 2, n! + n] 
are composite.

We can also extend this theorem to find specific sizes of consecutive 
composite integers.  For example, say we want to find an interval of 
1000 consecutive composite integers.  By our compositeness theorem, we 
know that the interval:

  [1001! + 2, 1001! + 1001]

will contain exactly 1000 composite integers, all in arithmetic 
progression!

I hope this helps, but if you have any more questions, feel free to 
write Dr. Math!
 
- Doctor Ricky, The Math Forum
  http://mathforum.org/dr.math/