Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Primes in the Form n^2 + 1

Date: 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
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/