I love this theorem. Proving it was, for a while, my equivalent to "counting sheep" when I couldn't sleep.
The approach I used was the one that works through the Gaussian integers, which relies mainly on the facts:
-- Both the Gaussian integers and the usual integers are Euclidean domains, and hence in particular are unique factorization domains.
-- Integer primes congruent to 1 or 2 (mod 4) are the norms of Gaussian primes.
-- Integer primes congruent to 3 (mod 4) just are Gaussian primes.
There are various ways to show that integer primes congruent to 1 (mod 4) are non-prime in the Gaussian integers. My currently favored approach is to show that x^2 + 1 is reducible in the ring of polynomials over Zp (the finite field of size p), which follows quickly from the fact that x^p - x factors completely over that field, which in turn follows immediately from Fermat's Little Theorem.
And Fermat's Little Theorem can be quickly proved by induction.
The approach I used was the one that works through the Gaussian integers, which relies mainly on the facts:
-- Both the Gaussian integers and the usual integers are Euclidean domains, and hence in particular are unique factorization domains. -- Integer primes congruent to 1 or 2 (mod 4) are the norms of Gaussian primes. -- Integer primes congruent to 3 (mod 4) just are Gaussian primes.
There are various ways to show that integer primes congruent to 1 (mod 4) are non-prime in the Gaussian integers. My currently favored approach is to show that x^2 + 1 is reducible in the ring of polynomials over Zp (the finite field of size p), which follows quickly from the fact that x^p - x factors completely over that field, which in turn follows immediately from Fermat's Little Theorem.
And Fermat's Little Theorem can be quickly proved by induction.