Prime Numbers and n^2-n+41Date: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/