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
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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search