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

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search