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

### Primes of the Form 4n+3

```
Date: 11/09/1999 at 11:14:45
From: Jessica Troise
Subject: Abstract Math I

I need to prove that there are infinitely many primes of the form 4n+3
where n is an element of the natural numbers. I'm having real problems
knowing how to start this problem.
```

```
Date: 11/09/1999 at 11:56:35
From: Doctor Wilkinson
Subject: Re: Abstract Math I

Hi, Jessica,

Take the proof that there are an infinite number of primes as a model.
In that proof, you suppose that

p_1, p_2, ..., p_n

are all the primes. You then multiply them all together and add 1. The
result is not divisible by any of p_1, p_2, ..., p_n because when you
divide it by any of those you get a remainder of 1. Therefore it must
be divisible by some other prime.

Suppose we try to do something similar. So suppose that

p_1, p_2, ..., p_k

are all the primes of the form 4n+3. Now all these primes are odd, so
we probably won't get anywhere taking their product and adding 1,
since that will give us an even number. But we probably want to make
something out of p_1, p_2, ..., p_k and try to copy the argument from
the other proof.

Now the next part of the argument should say that whatever we get has
to be divisible by a prime of the form 4n+3. That's not true of just
any number, but it is true of numbers of the form 4n+3, because such a
number first of all doesn't have 2 as a prime factor, and if you
multiply two numbers of the form 4n+1 together, you always get another
number of the form 4n + 1. Just multiply out (4m+1)(4n+1) and see what
happens.

Now suppose we multiply all the numbers

p_1, p_2, ..., p_k

together. Then you can work out that you'll get something of the form
4n+1 if n is even, and something of the form 4n+3 if n is odd. In
the first case, if you add 2 you'll get something of the form 4n+3:

p_1*p_2*...*p_k + 2 = 4x + 3

Now you can easily show that this number is not divisible by any of
p_1, ..., p_k, since if you divide you get a remainder of 2. So you
should be able to push through the argument in this case. Can you see
what to do in the other case?

- Doctor Wilkinson, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Number Theory
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