Consider six consecutive positive integers. Show that there is a prime number that divides exactly one of them.

First note the following Theorems:

Theorem 1 (Bertrand's Postulate):
For n>1 there is always a prime number p such that n<p<2n.
Proof:
The theorem is given at mathworld.wolfram.com, hence it must be true. QED.

Theorem 2 (Extension of Bertrand's Postulate):
If a>n, then the numbers a,a+1,..,a+n-1 contain a prime divisor p such that p>n.
Proof:
Same as for Theorem 1. QED. (Isn't it interesting how easily some tough theorems are proven?)

Steve Herman Theorem:
For n>1, there is a prime number that divides exactly one of any n consecutive positive integers.
Proof:
Let a,a+1,..,a+n-1 be the n consecutive numbers.
Case 1:
Say a>n. Then we know from Theorem 2 that one of our n numbers has a prime divisor p with p>n. Because of p>n, p cannot divide two of our n consecutive numbers, hence it divides exactly one of them.
Case 2:
Say a<=n. From Theorem 1 we know that there is a prime number p such that

(A) [(a+n-1)/2]<p<a+n-1

Here [x] denotes the largest integer such that [x]<=x. Thanks to a<=n, we have [(a+n-1)/2]>=[(2a-1)/2]>=[(2a-2)/2]=a-1. From (A) follows p>=a. Together with the right hand side of (A) we have

(B) a<=p<=a+n-1

i.e. p is a prime number contained in our sequence of n consecutive numbers. Now we are almost done, we only need to show that p is large enough, such that it cannot divide any other number in our sequence. That's easy, because we know from (A) that p>=(a+n)/2. Therefore 2p>=a+n, i.e. there can be no multiple of p that is smaller than a+n and therefore p cannot divide any other number in our sequence. Done.

--------------------------------------------------------

Of course all the hard work in the above proof has been done by much smarter people and I am merely bringing the harvest in. I have to believe there must be a simpler proof along the lines of Steve's argumentation, especially the handwaving part. Well, no time for that now.

Edited on September 10, 2006, 6:28 am

Edited on September 10, 2006, 8:28 am

Edited on September 10, 2006, 8:55 am

Posted by JLo on 2006-09-10 06:28:02