Why are there infinitely many primes of the form 4n+1?

[nate808]

I have heard a lot of talk about primes in the form of 4n+3 being infinite, but no one can seem to prove that 4n+1 is infinte. Why is this? Also, if someone disproved it, wouldn't that mean that all primes after a certain number had to be in the form of 4n+3

 

[TenaliRaman]

Nice way to get the homework done!
If its not, then too bad, it seemed like a good way to get the homework done :(

Anyways, do you know Dirichlet Theorem? I guess you dont, check this out,
http://mathworld.wolfram.com/DirichletsTheorem.html

This certainly shows that there infinitely many primes of the form 4n+1. Now can you show that this is true with elementary number theory?

-- AI

 

[matt grime]

it is easy to prove without appeal to dirichelt's theorem that there are infinitely many primes of the form 4n+3, and the standard proof that there infinitely many primes may be used. the case of 4n+1 is harder but certainly can be proved (without appeal to dirichlet's theorem), it may help to consider the sums of squares and do some research on that.

 

[nate808]

unfortunately for you, tenaliraman, it is not an easy way to get homework done since i haven't gone back to school yet, but thanks for the response

 

[robert Ihnot]

I got into that sometime ago on PF on its own thead: Infinitively many primes of the form 3n+1. It can be shown by considering quadratic residues. the thread was started by bOmbOnika, january 25, 2005. Here is my reply:

bOmbOnika: Assume there is a finitely # of primes of the form 3n+1
let P = product of those primes.. which is also of the form 3A+1 for some A.
Let N = (2p)^2 + 3.

I have an idea that may work. I am going to use the form (2P)^2 +3, granting that the capital P in the second line above is the small p in the third.

The form 3n+1 would represent the product of primes of the form 3k+1, and so we look at (6N+2)^2+3 = Q=36N^2+24N+7 ==7 Mod 12. (which is a reduction since we could have used 24, and in fact since the form is actually 6k+1 for the primes since 2 is the only even prime, we could do better.) But anyway, we use the form Q=12K+7, which is of the form 3X+1, so it can not be prime, or we have a contradiction.

Now all primes but 2 are of the form 4k+1 or 4k+3. Suppose Q has a prime factor q of the form 4k+1. Then we have:

(2P)^2 +3 == 0 Mod q. This gives (2P)^2 ==-3 Mod q, and since -1 is a quadratic reside of q, we have a U such that (U)^2==3 Mod q.

Thus by the law of quadratic reciproicity, we have an X such that X^2 =q Mod 3. But 1 is the only quadratic residue Mod 3, so in this case we are through since we have q==1 Mod 3.

Thus a prime factor q is of the form 4k+3 and of the form 3k+2. Modulo 12 the forms are 12k+1, 12k+5, 12k+7, 12k+11, since 2 or 3 could not divide Q.
But the only form available of both the forms 4k+3 and 3k+2, is 12k+11.

But the products and powers of primes involving -1 Mod 12, are only +-1Mod 12, so they can not equal Q==7 Mod 12.

Well, if that works, it involves understanding that -1 is a quadratic residue for primes of the form 4k+1 and the Law of Quadratic Reciprocity. Thus, maybe, that is why the form (2P)^2+3 was involved.

This was kind of clumsy and detailed, and Shmoe (then said,) Suppose you have a prime that divides N=(2P)^2+3, say p. You know that p is not 2 and that it's congruent to 2 mod 3. I assume you're familiar with quadratic reciprocity at this point. Use what you know about the legendre symbol to determine if -3 is a Quadratic Residue mod q.

Next, use the special form of N and the fact that p divides it to come to a contradiction

 

[CTS]

Take the primes of the form 4n+3 (n >= 1) and assume there are only finitely many. Put them in a list p1, p2, ..., pk. Consider N = 4*p1*p2*...*pk + 3. Clearly N must have a prime factor of the form 4n+3. But this prime was not in our original list; dividing N by any of the primes in our list leaves a remainder of 3. Thus our original assumption must have been incorrect and there are infinitely many primes of the form 4n+3.

Take a positive integer N. Let M = (N!)^2 + 1. Consider the smallest prime factor of M, called P. Note P is greater than N. We have M = 0 (mod P), or (N!)^2 = -1 (mod P). Now we raise both sides to the (P-1)/2-th power: (N!)^(P-1) = (-1)^((P-1)/2) (mod P). But by Fermat's Little Theorem, (N!)^(P-1) = 1 (mod P). So (-1)^((P-1)/2) = 1 mod P. Thus (P-1)/2 is even, say (P-1)/2 = 2n. Then P = 4n +1. So given any integer N, we can find a prime P > N of the form 4n+1. There must be infinitely many primes of the form 4n+1.