Formulas for Primes

Date: 09/09/2002 at 23:44:49
From: Junny Tim
Subject: Prime numbers

1. Ancient mathematicians thought that the formula n^2 + n + 41
   always produced a prime number for any whole number n.

   How do I show that there is an infinite number of whole numbers 
   from which the above formula does NOT produce a prime number?

2. How do I explain why the formula n^2 + 8n + 15 NEVER produces 
   a prime number (assuming that n is a whole number)?

Date: 09/10/2002 at 15:06:44
From: Doctor Paul
Subject: Re: Prime numbers

This quadratic is obviously not prime for n = 41 since

   41^2 + 41 + 41 = 41 * (41 + 1 + 1)

I think you'll find that a similar method will work for any multiple 
of 41. And certainly there is an infinite number of multiples of 41.

> 2. How do I explain why the formula n^2 + 8n + 15 NEVER produces 
>    a prime number (assuming that n is a whole number )

   n^2 + 8*n + 15 = (n + 5) * (n + 3)

is always a nontrivial factorization unless n = -4 or n = -2 (in 
either of these cases, we get one of the factors equal to the integer 
one, and thus we have the trivial factorization x = x * 1 that cannot 
be used to tell us whether or not the number x is prime). But a whole 
number cannot be negative, so we don't have to deal with this problem 
after all.

I hope this helps. Please write back if you'd like to talk about this 
some more.

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

Date: 09/10/2002 at 20:26:28
From: Junny Tim
Subject: Prime numbers

I still have trouble understanding the problem.  I'm more of a visual 
learner. Is it possible for you to rephrase your answers in another 
way for me to understand? 

Thank you for your help and cooperation. I appreciate it. I found this 
site very helpful.

Date: 09/11/2002 at 12:27:10
From: Doctor Roy
Subject: Re: Prime numbers

Hi,

I'll be giving a slightly different answer from Dr. Paul.

For the first problem, we have:

  n^2 + n + 41

If we use n = 41, then n^2 is divisible by 41. n is divisible by 41
(since n *is* 41) and 41 is obviously divisible by 41. Since each part
of the expression (all of n^2, n, and 41) are divisible by 41, then
the entire sum must be divisible by 41.

Notice that we can use any multiple of 41. If we use n = 2*41, or 
3*41, etc., then n^2 and n are still divisible by 41, and the entire
expression is divisible by 41.

As for the second problem:

  n^2 + 8n + 15

There are two ways to see why the expression is never prime. The first
is what Dr. Paul explained.

  n^2 + 8n + 15 = (n+5)*(n+3)

This means that (n^2 + 8n + 15) is the product of two different
numbers, (n+5) and (n+3). This means that is n is positive, and we 
have two different numbers that divide the expression. For example, if 
n = 7, then:

  n^2 + 8n + 15 = 7^2 + 8*7 + 15 = 49 + 56 + 15 = 120

   (n+5) = (7 + 5) = 12
   (n+3) = (7 + 3) = 10

This means that 120 = 12*10, so we have a factorization. Since any
number that can be expressed as the product of two positive integers
(without either being 1) is composite, n^2 + 8n + 15 can never be 
prime.

There is one exception, of course. If either (n+5) or (n+3) = 1, then
the resulting expression could be prime. However, because n must be
negative for this to happen, we don't have to worry about it.

The other way to see why (n^2 + 8n + 15) can never be prime is that it
is always divisible by 3. Notice that 15 is divisible by 3, and you
can prove that (n^2 + 8n) is always divisible by 3 for any positive n.

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