The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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 

I hope this helps, but if you have any more questions, feel free to 
write Dr. Math!
- Doctor Ricky, The Math Forum 
Associated Topics:
College Number Theory

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.