## 4n + 3 primes

**Moderators:** gmalivuk, Moderators General, Prelates

### 4n + 3 primes

I've been reading Douglas Hoftstadter's I Am a Strange Loop, and he makes the following statement: "Not only are primes of the form 4n + 3 never the sum of two squares (proving this is easy) [...]"

I don't have much of a math background, so this is a bit vexing. Could somebody please give me a little hint as to how to go about proving that 4n + 3 primes are never the sum of two squares? What sort of special property do the sums of squares have that I can test for?

Thanks!

I don't have much of a math background, so this is a bit vexing. Could somebody please give me a little hint as to how to go about proving that 4n + 3 primes are never the sum of two squares? What sort of special property do the sums of squares have that I can test for?

Thanks!

### Re: 4n + 3 primes

Suppose 4n + 3 was the sum of two squares. Clearly one has to be odd and the other even, since otherwise their sum would be even. Therefore, one will be of the form 2m and the other of the form 2n + 1. If you square these and add them, you get 4m

^{2}+ 4n^{2}+ 4n + 1, which is not of the form 4n + 3.This is a placeholder until I think of something more creative to put here.

### Re: 4n + 3 primes

Sums of two squares are precisely those numbers of the form n

^{2}p_{1}p_{2}...p_{k}, where n is an integer and each p_{i}is either 2 or a prime one more than a multiple of 4.(∫|p|

Thanks, skeptical scientist, for knowing symbols and giving them to me.

^{2})(∫|q|^{2}) ≥ (∫|pq|)^{2}Thanks, skeptical scientist, for knowing symbols and giving them to me.

- gmalivuk
- GNU Terry Pratchett
**Posts:**26739**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

### Re: 4n + 3 primes

Sure, but it's not as though that fact itself is nearly as easy to prove as what Robin S just posted...

### Re: 4n + 3 primes

Of course. He asked for properties of sums of two squares, and so I gave a characterization of them. I wasn't intending my comment to be a second proof of Hofstadter's so much as a follow-up comment after the main question had been answered.

(∫|p|

Thanks, skeptical scientist, for knowing symbols and giving them to me.

^{2})(∫|q|^{2}) ≥ (∫|pq|)^{2}Thanks, skeptical scientist, for knowing symbols and giving them to me.

### Re: 4n + 3 primes

A square is equal to either 0 or 1, mod 4.

**Spoiler:**

SargeZT wrote:Oh dear no, I love penguins. They're my favorite animal ever besides cows.

The reason I would kill penguins would be, no one ever, ever fucking kills penguins.

- greeniguana00
**Posts:**113**Joined:**Sun Mar 30, 2008 12:09 am UTC**Location:**Albany, NY, USA

### Re: 4n + 3 primes

Following up with what Robin S. posted:

**Spoiler:**

Goodnight, g♥♥dnight! There's something magnificent about good night with two disemboweled hearts in it, or at least it seems that way when you're so happy.

### Re: 4n + 3 primes

Cauchy wrote:Sums of two squares are precisely those numbers of the form n^{2}p_{1}p_{2}...p_{k}, where n is an integer and each p_{i}is either 2 or a prime one more than a multiple of 4.

Why is that?

SargeZT wrote:Oh dear no, I love penguins. They're my favorite animal ever besides cows.

The reason I would kill penguins would be, no one ever, ever fucking kills penguins.

### Re: 4n + 3 primes

Here's a sketch of a proof. It's probably not the simplest proof, and it uses some advanced ideas. Maybe someone else can provide a simpler one.

Consider the ring Z[i] = {a+bi | a,b in Z}. The norm function N, where N(a+bi)=(a+bi)(a-bi)=a

How does the factorization of n in Z relate to that in Z[i]? Essentially, some primes split into two conjugate primes (for example, 5=(1+2i)*(1-2i)), and some primes stay prime. The above condition then simply says that n is a sum of two squares if and only if the exponents of the primes that stay prime are all even in the factorization of n.

We've seen that 3 (mod 4) primes stay prime, so all we need to show is that 1 (mod 4) primes split. Modulo p, (p-1)! is the product of all the units mod p. Pair each up with its inverse, and you're left with (p-1)!=(1)*(-1)=-1 (mod p). But if g is a generator modulo p, -1=(p-1)!=g

So, the primes that split are precisely 2 and the primes that are 1 mod 4, and the primes that stay prime are precisely the primes that are 3 mod 4. So, the numbers that can be written as a sum of two squares are the numbers whose prime factorization has an even exponent on each 3 mod 4 prime, which are numbers of the form n

Consider the ring Z[i] = {a+bi | a,b in Z}. The norm function N, where N(a+bi)=(a+bi)(a-bi)=a

^{2}+b^{2}, is multiplicative. An integer can be written as a sum of two squares if and only if it is the norm of something. This occurs if and only if it can be factored into (a+bi)*(a-bi). Z[i] is a principal ideal domain (this takes some proving), so it has unique prime factorization, and therefore n can be written as the sum of two squares if and only if the multiplicity of a prime P in the factorization of n is the same as that of P* (by which I mean the conjugate of P), and if P=P*, this multiplicity is even.How does the factorization of n in Z relate to that in Z[i]? Essentially, some primes split into two conjugate primes (for example, 5=(1+2i)*(1-2i)), and some primes stay prime. The above condition then simply says that n is a sum of two squares if and only if the exponents of the primes that stay prime are all even in the factorization of n.

We've seen that 3 (mod 4) primes stay prime, so all we need to show is that 1 (mod 4) primes split. Modulo p, (p-1)! is the product of all the units mod p. Pair each up with its inverse, and you're left with (p-1)!=(1)*(-1)=-1 (mod p). But if g is a generator modulo p, -1=(p-1)!=g

^{(p-1)*p/2}(mod p). For odd p, this is a square if and only if p is 1 mod 4. Thus, if p is 1 mod 4, -1 is a square mod p, say -1=r^{2}. Now we consider the lattice of points x+yi such that x=ry (mod p). We note that this is an ideal of Z[i] with index p, so it must be a prime ideal (generated by, say, a+bi), of norm p. Thus p=(a+bi)(a-bi), so p splits.So, the primes that split are precisely 2 and the primes that are 1 mod 4, and the primes that stay prime are precisely the primes that are 3 mod 4. So, the numbers that can be written as a sum of two squares are the numbers whose prime factorization has an even exponent on each 3 mod 4 prime, which are numbers of the form n

^{2}p_{1}p_{2}...p_{k}, where the p_{i}are 1 mod 4, or 2.Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

### Re: 4n + 3 primes

To show that you need an even power for every prime q that's 3 mod 4, we observe that if a

To see that every number of this form is a sum of two squares, we first notice that if m and n are the sums of two squares, then so is mn. This is because mn = (a

The proof I know to show that every such prime is the sum of two squares is long and relies on infinite descent. You can see a bunch of different proofs, including mine (Euler's proof) and antonfire's (Dedekind's first proof), here:

http://en.wikipedia.org/wiki/Proofs_of_ ... wo_squares

After reading that page, I'm rather partial to Dedekind's second and Zagier's.

^{2}+ b^{2}= 0 mod q, then b^{2}= (-1)a^{2}mod q. Let r be a primitive root mod q, and assume for sake of contradiction that we had that a = r^{k}for some k; then, (-1)a^{2}= r^{(q-1)/4}r^{2k}= r^{2k + (q-1)/4}= b^{2}. However, 2k + (q-1)/4 is odd, since q is 3 mod 4, so r^{2k + (q-1)/4}can't be a square, a contradiction. Our conclusion is that a is not r^{k}for any k, which leaves us with a being 0, and hence b being 0. The corollary is that if a^2 + b^2 = n and q|n where q is a prime that's 3 mod 4, then q|a and q|b, and hence q^2|n. Dividing through by q^2 and repeating gives us that the highest power of q that divides n is an even power of q, so every number n that's the sum of two squares must be of the form k^2p_{1}p_{2}...p_{m}, where each p_{i}is 2 or a prime that's 1 mod 4.To see that every number of this form is a sum of two squares, we first notice that if m and n are the sums of two squares, then so is mn. This is because mn = (a

^{2}+ b^{2})(c^{2}+ d^{2}) = a^{2}c^{2}+ b^{2}c^{2}+ a^{2}d^{2}+ b^{2}d^{2}= a^{2}c^{2}+ 2abcd + b^{2}d^{2}+ a^{2}d^{2}- 2abcd + b^{2}c^{2}= (ac + bd)^{2}+ (ad - bc)^{2}. Easily, k^2 is the sum of two squares (k^2 + 0^2 = k^2) and 2 is the sum of two squares (1^2 + 1^2 = 2), so it suffices to show that each prime p that is 1 mod 4 is the sum of two squares.The proof I know to show that every such prime is the sum of two squares is long and relies on infinite descent. You can see a bunch of different proofs, including mine (Euler's proof) and antonfire's (Dedekind's first proof), here:

http://en.wikipedia.org/wiki/Proofs_of_ ... wo_squares

After reading that page, I'm rather partial to Dedekind's second and Zagier's.

(∫|p|

Thanks, skeptical scientist, for knowing symbols and giving them to me.

^{2})(∫|q|^{2}) ≥ (∫|pq|)^{2}Thanks, skeptical scientist, for knowing symbols and giving them to me.

### Re: 4n + 3 primes

I found a different way to prove this bit. I'm not sure if it's better or worse.antonfire wrote:Modulo p, (p-1)! is the product of all the units mod p. Pair each up with its inverse, and you're left with (p-1)!=(1)*(-1)=-1 (mod p). But if g is a generator modulo p, -1=(p-1)!=g(p-1)*p/2 (mod p). For odd p, this is a square if and only if p is 1 mod 4. Thus, if p is 1 mod 4, -1 is a square mod p, say -1=r2.

Primes of the form 4k+1 have a cyclic unit group of size 4k, so the fourth powers make up a fourth of the group, so since each fourth power has at most 4 fourth roots, it has exactly 4 fourth roots. In particular, 1 has 4 fourth roots, and since no more than 2 of them square to 1, the other two must square to -1, so -1 is a square mod p.

More generally, the number of n'th roots of unity is exactly the index of the n'th powers in the unit group, which is just gcd(n,p-1). -1 is a perfect n'th power, iff there are twice as many 2n'th roots of unity as n'th roots of unity, iff 2*gcd(n,p-1)=gcd(2n,p-1), iff p-1 is divisible by more powers of 2 than n, in other words: -1 is a perfect 2

^{k}m'th power iff p=1 (mod 2

^{k+1})

Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

### Re: 4n + 3 primes

Letting g be a primitive root mod p, we see that -1 = g

^{(p-1)/2}mod p, so the status of -1 is determined solely by the factors of (p-1)/2. In particular, when p is 1 mod 4, (p-1)/2 is even, so -1 is a square mod p.^{2})(∫|q|

^{2}) ≥ (∫|pq|)

^{2}

Thanks, skeptical scientist, for knowing symbols and giving them to me.

### Who is online

Users browsing this forum: No registered users and 14 guests