- #1

- 56

- 0

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter nate808
- Start date

- #1

- 56

- 0

- #2

- 644

- 1

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

- #3

matt grime

Science Advisor

Homework Helper

- 9,395

- 4

- #4

- 56

- 0

- #5

- 1,056

- 0

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

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.

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

Last edited:

- #6

- 20

- 0

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.

Share:

- Replies
- 1

- Views
- 3K