Prime Integer Proof

Date: 03/24/2002 at 15:23:44
From: Shane
Subject: Prime Integer Proof

Hi. 

Please help me prove that if p is a prime number greater than or 
equal to 5, then there exists an integer k such that p = sqrt(24k+1). 
I would greatly appreciate any possible help in finding a solution. 
Thanks.

Date: 03/24/2002 at 15:41:39
From: Doctor Paul
Subject: Re: Prime Integer Proof

Your question is equivalent to proving:

   if p is a prime >= 5, then p^2 = 1 mod 24

Here is how to prove it. First notice that whenever p >= 5 is prime, 

   p = 1 mod 6 or p = 5 mod 6.

For a proof of this, look here:

   Primes Greater Than/Less Than Multiples of Six
   http://mathforum.org/dr.math/problems/riley.01.18.02.html   

Now, if p = 1 mod 6, then we have one of four cases:

(a) p = 1 mod 24
(b) p = 7 mod 24
(c) p = 13 mod 24
(d) p = 19 mod 24

In all of these cases, p^2 = 1 mod 24.

On the other hand, if p = 5 mod 6, then we have one of four cases:

(a) p = 5 mod 24
(b) p = 11 mod 24
(c) p = 17 mod 24
(d) p = 23 mod 24

and in all of these cases, p^2 = 1 mod 24.

This completes the proof.

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: 03/25/2002 at 13:54:50
From: Shane
Subject: Prime Integer Proof

Thank you very much for your help with this problem, but you must 
forgive me, because I am still not completely clear about the sequence 
of steps that you took to find a solution. The reason for this may be 
that I am not very familiar with mod, other than computer programs. Is 
there another approach to a solution?

Thanks again.

Date: 03/25/2002 at 16:54:17
From: Doctor Peterson
Subject: Re: Prime Integer Proof

Hi, Shane.

Here is a way to prove this using basic algebra, based on Dr. Paul's 
approach.

First, notice that any number at all can be written as one of 6k, 
6k+1, 6k+2, 6k+3, 6k+4, and 6k+5. But

    6k             is divisible by 6
    6k+2 = 2(3k+1) is divisible by 2
    6k+3 = 3(2k+1) is divisible by 3
    6k+4 = 2(3k+2) is divisible by 2

Therefore, only 6k+1 and 6k+5 can be prime. The only exception is if 
the number itself is 2 or 3; these are the only multiples of 2 or 3 
that are prime. So if p >= 5, we won't hit these exceptions. Also, we 
can write 6k+5 as 6k-1 by just increasing the value of k by 1:

    6k+5 = 6k+6-1 = 6(k+1)-1

So we can say that any prime p >= 5 can be written as 6k +/- 1 for 
some k. (You could do the rest of the work just as well using 6k + 5, 
but I find this neater.)

Now just square p:

    p^2 = (6k +/- 1)^2 = 36k^2 +/- 12k + 1

        = 12k(3k +/- 1) + 1

This is very close to what we want, which is that

    p^2 = 24k + 1

for some k. So look at what we are multiplying by 12. If k is even, 
then 12k is a multiple of 24; if k is odd, 3k +/- 1 is even, and 12 
times that is a multiple of 24. To put this another way (using the 
plus sign; you can repeat this for the minus sign):

    if k is even, then k = 2a for some integer a, and

        p^2 = 12k(3k + 1) + 1 = 24a(6a + 1) + 1

            = 24b + 1  where  b = a(6a + 1)

    if k is odd, then k = 2a+1 for some integer a, and

        p^2 = 12k(3k + 1) + 1 = 12(2a+1)(6a + 3 + 1) + 1

            = 12(2a+1)(6a + 4) + 1

            = 24(2a+1)(3a + 2) + 1

            = 24b + 1  where  b = (2a+1)(3a + 2)

So now we have shown that

    p^2 = 24k + 1  for some integer k

so

    p = sqrt(24k + 1)  for some integer k

If you are going to do much of this sort of number theory, it would be 
a good idea to familiarize yourself with modular arithmetic, because 
it saves a lot of this sort of algebra. Take Dr. Paul's proof slowly, 
read the link he gave you, and do just what he said (try squaring the 
numbers he listed), and you will find it is not really as difficult as 
you think.

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