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

### Prime Integer Proof

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

Hi.

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.

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/
```
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