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

• nate808
In summary: Since M is a prime and P is not, it must be the case that (N!)^2 = 1 (mod P). But this is impossible, since (N!)^2 must be divisible by every prime except for 1 and M itself. Thus, (N!)^2 must be equal to 1 (mod P), or M must be equal to 1 (mod P). But this cannot be, since M is greater than 1 (mod P). Thus, M must be equal to 1 (mod P), or P must be a prime. But this cannot be, since P is not a prime. Thus, we have proven that there is a prime of the form 4n+3
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

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

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.

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

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

Last edited:
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.

What are Primes in 4n+1/3?

Primes in 4n+1/3 are a specific type of prime number that can be represented by the formula 4n+1/3, where n is any positive integer. These numbers have a unique property and are of interest to mathematicians and scientists.

How are Primes in 4n+1/3 different from regular primes?

Unlike regular primes, Primes in 4n+1/3 are always in the form of 4n+1/3. This means that they are always 1 more than a multiple of 4, making them a subset of regular primes.

What is the significance of Primes in 4n+1/3?

The significance of Primes in 4n+1/3 lies in their relationship with the distribution of primes and other mathematical properties. They have been used in various mathematical proofs and have connections to other areas of mathematics such as quadratic reciprocity and modular forms.

Can any number be expressed as 4n+1/3?

No, not all numbers can be expressed as 4n+1/3. Only a specific subset of prime numbers can be represented in this form. Other numbers may have different representations or may not have a specific formula at all.

How are Primes in 4n+1/3 used in real-world applications?

Primes in 4n+1/3 have various real-world applications, including in cryptography, where they are used to generate secure keys for encryption. They are also used in coding theory and error-correcting codes. Additionally, they have applications in physics and signal processing.

• Precalculus Mathematics Homework Help
Replies
4
Views
1K
• Precalculus Mathematics Homework Help
Replies
12
Views
1K
• Linear and Abstract Algebra
Replies
4
Views
1K
• Linear and Abstract Algebra
Replies
4
Views
1K
• Calculus and Beyond Homework Help
Replies
2
Views
3K
• Precalculus Mathematics Homework Help
Replies
2
Views
881
• Linear and Abstract Algebra
Replies
2
Views
759
• Linear and Abstract Algebra
Replies
11
Views
3K
• Linear and Abstract Algebra
Replies
7
Views
3K
• Calculus and Beyond Homework Help
Replies
10
Views
2K