Quick proof to showing that $p\equiv 1\pmod{4}$ implies $p$ is reducible in $\mathbb{Z}[i]$?

I want to show that for $p$ a prime, if $p\equiv 1\pmod{4}$, then $p$ is not irreducible in $\mathbb{Z}[i]$.

I know that $x^2\equiv -1\pmod{p}$ has a solution when $p\equiv 1\pmod{4}$, so $p\mid x^2+1$. I could then prove that $\mathbb{Z}[i]$ is a PID, so Euclid's lemma holds, and then see that $p\mid (x+i)$ or $p\mid (x-i)$, using the fact that $\mathbb{Z}[i]$ is a PID, so if $p$ is irreducible, then $p$ is prime. But then this gives a contradiction since $1/p$ is not an integer, so $(x\pm i)/p\notin\mathbb{Z}[i]$.

I could do all this, but it seems like a lot of effort for the result. Is there a slicker, more elegant proof that $p\equiv 1\pmod{4}$ implies $p$ is not irreducible in the Gaussian integers?

By the way, I'm using this to finally conclude Fermat's theorem on the sum of two squares, so I don't want to refer to that in this.

-
A prime is reducible in the Gaussian integers iff it's a sum of two natural squares. So see Proofs of Fermat's theorem on sums of two squares. –  Chris Eagle Oct 8 '11 at 22:19
Dear Travis, The argument you outline is the standard one, and I'm not sure you can make it any shorter, since proving the reducibility statement you ask about is tantamount to proving that $\mathbb Z[i]$ is a PID. Regards, –  Matt E Oct 9 '11 at 2:52

If you want to use the Gaussian integers then I don't think there's any way around the "long" chain of argument that involves showing it is a UFD. However, there are methods of proving Fermat's two-square theorem that make no mention of the Gaussian integers. (There had better be such a method since the Gaussian integers were introduced about 200 years after Fermat stated his two-square theorem and suggested it could be proved by descent. See Chapter 26 of Silverman's Friendly Introduction to Number Theory, 3rd ed., for a proof by descent.)

1. David's answer mentions an approach using equivalence of binary quadratic forms.

2. A second technique uses Minkowski's geometry of numbers (which is important in some basic theorems of algebraic number theory). You can read this in many textbooks on algebraic number theory, such as Section 7.2 of Stewart and Tall's "Algebraic Number Theory" (you don't need to know anything in the earlier part of the book). Or look at Section 5, Chapter 22 of Goldman's "The Queen of Mathematics: An Historically Motivated Guide to Number Theory".

3. Thue's lemma. See pp. 264--265 of Burton's "Elementary Number Theory" (7th ed.). The geometry of numbers and Thue's lemma are both closely related to the Pigeonhole principle.

4. Jacobi sums (Ireland & Rosen, p. 95). This requires knowing $({\mathbf Z}/p{\mathbf Z})^\times$ has an element of order 4 and leads to an explicit character sum which is a Gaussian integer of norm $p$. It doesn't require knowing the Gaussian integers have unique factorization.

5. Continued fractions. See C. D. Olds, "Continued Fractions", 132--133.

One advantage of the proof using unique factorization in the Gaussian integers is that it simultaneously gives you not just the existence of $a$ and $b$ such that $p = a^2 + b^2$ but also the uniqueness of $a$ and $b$ up to order and sign. Other techniques of proving the existence of $a$ and $b$ don't necessarily also explain why these integers are essentially unique (although the uniqueness aspect can be proved on its own too).

-

The first proof I ever saw of Fermat's theorem used the reduction theory of binary quadratic forms, i.e. expressions of the form $Q(x, y) = ax^2 + bxy + cz^2$ with $a,b,c \in \mathbf{Z}$. We say $Q$ represents $n$ if there are integers $x, y$ such that $Q(x, y) = n$. To $Q$ we can attach its discriminant, $b^2 - 4ac$; we're interested in forms whose discriminant is negative, which therefore do not represent any negative number.

The proof goes in two steps:

• the fact that -1 is a square mod p implies that p is represented by some binary quadratic form of discriminant -4;
• every binary quadratic form of discriminant -4 can be reduced to $x^2 + y^2$ by a change of variables.

Since changing variables doesn't alter the set of integers that a form represents, this shows that $x^2 + y^2$ represents $p$, i.e. $p$ is a sum of two squares. There is an account of this proof here (quite compressed, but not as much so as the one I just gave :-) ).

You may not like this since it proves Fermat's theorem without explicitly mentioning $\mathbf{Z}[i]$ at all, but you can of course deduce the criterion for irreducibility in $\mathbf{Z}[i]$ from Fermat's theorem.

-

Here's one way, I suppose it's somewhat slick:

If $p\equiv 1\bmod 4$, then $G=(\mathbb{Z}/p\mathbb{Z})^\times$ is a cyclic group of order $p-1$. Because $4\mid p-1$ and $G$ is cyclic, there is an element $a\in G$ of order $4$. Thus, in $\mathbb{Z}[i]/(p)$, there are more than 2 solutions to the equation $x^2+1=0$, namely $$\pm a,\pm i\in \mathbb{Z}[i]/(p)$$ which implies that $\mathbb{Z}[i]/(p)$ is not an integral domain, which implies that $p$ is not prime. Because $\mathbb{Z}[i]$ is a PID, this implies that $p$ is not irreducible.

-
My link in the comments gives three proofs that don't use $\mathbb{Z}[i]$ at all (apart from the trivial last step "$p$ is a sum of two squares implies $p$ is reducible in $\mathbb{Z}[i]$"). –  Chris Eagle Oct 8 '11 at 22:33
Thanks, this is pretty nice. –  Travis Bickle Oct 8 '11 at 22:41
@Zev That seems to be equivalent to what Travis wrote in his question. Why do you think it is different? Note: I mistakenly upvoted Travis's above comment when I went to click on "add comment" (slow mobile browser, sigh). –  Bill Dubuque Oct 8 '11 at 23:05
@Bill: Hmm, now that you point it out I do see that it is essentially equivalent, though I suppose there is a minor difference in that the approach in my answer is direct, instead of by contradiction (a trivial matter, to be sure). +1 to your comment intentionally :) –  Zev Chonoles Oct 8 '11 at 23:11

As far as i know the shortest proof is the one given in this thread of mathoverflow : http://mathoverflow.net/questions/31113/zagiers-one-sentence-proof-of-fermats-theorem

-