Primes in the Form n^2 + 1Date: 04/06/2003 at 00:37:47 From: Melissa Jac Subject: Number Theory - Primes in the form n^2 + 1 Hi Doctors o' Mathematics! I am so stuck on this problem! Let n be a positive integer with n not equal to 1. Prove that if n^2 + 1 is a prime, then n^2 + 1 is expressible in the form 4k + 1 with k in the integers. Thanks, Melissa Date: 04/06/2003 at 09:56:29 From: Doctor Paul Subject: Re: Number Theory - Primes in the form n^2 + 1 Let's rephrase your question as follows: If n > 1 and n^2 + 1 is prime, prove that n^2 + 1 = 1 mod 4. The easiest way to approach a problem like this is to consider all possible cases. This may seem like a lot of work (after all - there is an infinite number of positive integers greater than one) but it really isn't so bad if you think about it the right way. Every integer must be either a multiple of four, one more than a multiple of four, two more than a multiple of four, or three more than a multiple of four. So there are four cases to consider: Case 1 If n = 0 mod 4 and n^2 + 1 is prime, then n^2 + 1 = 0^2 + 1 = 1 mod 4 and is hence expressible as one more than a multiple as four. An example: n = 4. Then n^2 + 1 = 17 which is prime. And 17 = 4*4 + 1. Case 2 If n = 1 mod 4 and n^2 + 1 is prime, then n^2 + 1 = 1^1 + 1 = 2 mod 4. Notice that an integer that is 2 mod 4 is even and will never be prime unless it is 2. Thus the only solution we have to worry about is n^2 + 1 = 2. This implies n = 1 or n = -1. Neither is possible; we were told at the outset that n > 1. Thus there is nothing to prove in this case since it cannot occur. Case 3 If n = 2 mod 4 and n^2 + 1 is prime, then n^2 + 1 = 2^2 + 1 = 4 + 1 = 5 = 1 mod 4 and is hence expressible as one more than a multiple of four. An example: n = 6. Then n^2 + 1 = 37 which is prime. And 37 = 4*9 + 1. Case 4 Finally, if n = 3 mod 4 and n^2 + 1 is prime, then n^2 + 1 = 9 + 1 = 10 = 2 mod 4. We addressed this in Case 2 above. That's all there is to it... 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: 04/06/2003 at 12:59:27 From: Melissa Jac Subject: Thank you (Number Theory - Primes in the form n^2+1) Thank you very much. I didn't expect such a prompt answer or one even at all. Really thank you! I search Doctor Math all the time for help when I get stuck and I think your service is great! Melissa |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/