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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.