4n + 3 primes

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

jwwells
Posts: 180
Joined: Thu Sep 21, 2006 4:47 am UTC

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!

Robin S
Posts: 3579
Joined: Wed Jun 27, 2007 7:02 pm UTC
Location: London, UK
Contact:

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 4m2 + 4n2 + 4n + 1, which is not of the form 4n + 3.
This is a placeholder until I think of something more creative to put here.

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: 4n + 3 primes

Sums of two squares are precisely those numbers of the form n2p1p2...pk, where n is an integer and each pi is either 2 or a prime one more than a multiple of 4.
(∫|p|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...
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

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|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

Pathway
Leon Sumbitches...?
Posts: 647
Joined: Sun Oct 15, 2006 5:59 pm UTC

Re: 4n + 3 primes

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

Spoiler:
If n is even, n = 2s for some integer s. Then n2 = 4s2. That means n2 = 0 mod 4.

If n is odd, n = 2s + 1 for some integer s. Then n2 = 4s2 + 4s + 1 = 1 mod 4.

Since n is either even or odd, this takes care of all possible n.

Now, 4n+3 = 3 mod 4. There's no way to add two integers that are 0 or 1 mod 4 and get 3. 0+0 = 0 mod 4, 0+1 = 1 + 0 = 1 mod 4, and 1 + 1 = 2 mod 4. Those are all the cases, and none of them gives you 3.
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:
Assume m, n, and x are integers.

If
4m^2 + 4n^2 + 4n + 1 = 4x + 3
then
4m^2 + 4n^2 + 4n - 2 = 4x
and
m^2 + n^2 + n - 1/2 = x
and
m^2 + n^2 + n - x = 1/2

The squares of integers are integers, and the sum and difference of integers is an integer, and 1/2 is not an integer, so there are no integer values of m, n, and x that work.
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.

jwwells
Posts: 180
Joined: Thu Sep 21, 2006 4:47 am UTC

Re: 4n + 3 primes

Thanks a lot!

Pathway
Leon Sumbitches...?
Posts: 647
Joined: Sun Oct 15, 2006 5:59 pm UTC

Re: 4n + 3 primes

Cauchy wrote:Sums of two squares are precisely those numbers of the form n2p1p2...pk, where n is an integer and each pi 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.

antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

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)=a2+b2, 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=r2. 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 n2p1p2...pk, where the pi 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?

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

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 a2 + b2 = 0 mod q, then b2 = (-1)a2 mod q. Let r be a primitive root mod q, and assume for sake of contradiction that we had that a = rk for some k; then, (-1)a2 = r(q-1)/4r2k = r2k + (q-1)/4 = b2. However, 2k + (q-1)/4 is odd, since q is 3 mod 4, so r2k + (q-1)/4 can't be a square, a contradiction. Our conclusion is that a is not rk 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^2p1p2...pm, where each pi 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 = (a2 + b2)(c2 + d2) = a2c2 + b2c2 + a2d2 + b2d2 = a2c2 + 2abcd + b2d2 + a2d2 - 2abcd + b2c2 = (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|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: 4n + 3 primes

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.
I found a different way to prove this bit. I'm not sure if it's better or worse.

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 2km'th power iff p=1 (mod 2k+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?

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

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.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.