Prime Numbers and n^2-n+41

Date: 07/23/2003 at 00:56:08
From: John
Subject: Prime numbers

I wonder if you could explain the way n^2 - n + 41 works to produce a 
prime number for every integer value, and why it fails when n = 41 
(specific explanation).

Date: 07/25/2003 at 19:37:39
From: Doctor Mike
Subject: Re: Prime numbers
  
John, 

I have not verified that n^2 - n + 41 is a prime for each n up to 40. 
But if that is true you should be able to do the verification with a 
calculator in a few minutes. 
  
As for why it fails when n = 41, we only need to examine the 
expression for that value:
  
       41^2 - 41 + 41

That simplifies to 41 squared, which clearly is not prime.
  
I've seen this before. It seems to be an example of why you need to do 
BOTH parts of a proof by Mathematical Induction.
  
To prove an infinite number of statements "S(n)" for every positive 
integer n, you do two steps:

   Step 1 -- Prove that S(1) is true.
   Step 2 -- Prove that if S(k) is true then S(k+1) is 
             true, where the only thing you know about k
             is that k is some positive integer.
  
I like to think of this as similar to setting up a long line of 
dominos in a row. Then I can knock them all down in 2 steps. Step 1 is 
to knock over the first one. Then step 2 is to wait for gravity and 
the potential energy stored in the set-up of the system to do the 
rest. The first one knocks over the second, the second knocks over
the third, and so on.  
  
The idea behind Mathematical Induction is that if you "get the process 
started" by proving that the first statement is true, and then "keep 
the process going" by proving that any statement being true guarantees 
that the next is true, then all of the statements have to be true.  
  
The analogy with dominos breaks down here because nobody so far has 
arranged an infinite number of dominos. But maybe you get the idea of 
the similarity up to a point.
  
The temptation with Mathematical Induction sometimes is that if you 
prove the statement is true for a whole bunch of statements at the 
beginning, then the "step 2" Induction Step can be skipped. Sort of a 
"Gee it must be true by the law of averages" thing. Your example 
apparently shows that even if the first forty statements are true, the 
very next one may not be. 
  
Hope this helps, and was not a lot more than you wanted.

- Doctor Mike, The Math Forum
  http://mathforum.org/dr.math/