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