Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School 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