Expressing Primes as Sums of Two Squares: From Fermat's Theorem to Practical Algorithms

The intersection of number theory and computation often reveals fascinating tensions between mathematical elegance and practical efficiency. A recent discussion sparked by Elon Musk's post about Grok's list of beautiful theorems brought attention to Fermat's theorem on primes expressible as sums of two squares—a result that, while theoretically profound, presents interesting computational challenges when we attempt to actually find the representations.

Fermat's Theorem and Its Computational Implications

Fermat's theorem states that an odd prime p can be written as the sum of two squares if and only if p ≡ 1 (mod 4). The "only if" direction is straightforward: squares modulo 4 are either 0 or 1, so the sum of two squares can only be 0, 1, or 2 modulo 4, never 3. This immediately rules out primes of the form 4k + 3.

However, the "if" direction—proving that every prime of the form 4k + 1 can indeed be expressed as a sum of two squares—requires more sophisticated number-theoretic machinery. This asymmetry between the two directions is typical in mathematics: existence proofs often require deeper insight than impossibility proofs.

Gauss's Elegant but Impractical Formula

Carl Friedrich Gauss, whose contributions to number theory remain foundational, provided a formula for finding the two squares whose sum equals a prime p ≡ 1 (mod 4). Stan Wagon, in his 1990 paper "The Euclidean Algorithm Strikes Again," presented this formula and candidly noted its computational uselessness.

The formula itself is beautiful in its simplicity, but Wagon's assessment highlights a crucial distinction in mathematics: a result can be theoretically elegant while being practically infeasible. The computational complexity of Gauss's approach grows prohibitively with the size of p, making it unsuitable for actual computation even with modern hardware.

The Computational Bottleneck

The primary obstacle in implementing Gauss's formula lies in the factorial calculations required. Computing (p-1)! modulo p involves O(p) multiplications, and the intermediate values grow factorially large. While modular arithmetic can keep numbers manageable by reducing modulo p at each step, the fundamental O(p) complexity remains.

This raises an interesting question: could there be an identity analogous to Wilson's theorem that would allow faster computation of the necessary factorials modulo p? Wilson's theorem provides an efficient way to compute (n-1)! mod n, but no such shortcut appears to exist for the specific factorials needed in Gauss's formula. The search for such an identity remains an open problem in computational number theory.

Wagon's Practical Algorithm

Recognizing the limitations of Gauss's formula, Wagon developed an algorithm that dramatically improves computational efficiency. The key insight is to replace the factorial-heavy approach with operations that scale much more favorably with the size of p.

Wagon's algorithm relies on two main components: finding a quadratic non-residue modulo p and applying the Euclidean algorithm. A quadratic non-residue is a number c such that c ≠ x² (mod p) for any x—in other words, it's not a perfect square modulo p. Since exactly half the numbers between 1 and p-1 are quadratic non-residues, finding one typically requires only a few random attempts.

The Euclidean algorithm component is particularly clever. By leveraging properties of greatest common divisors in modular arithmetic, Wagon's approach reduces the problem to a series of divisions and remainders, operations that are computationally efficient even for very large numbers.

The overall complexity of Wagon's algorithm is dramatically better than O(p), making it feasible to express even large primes as sums of two squares. This represents a classic example of how algorithmic thinking can transform a theoretically interesting but practically useless result into a computationally viable tool.

The Beauty of Mathematical Algorithms

This progression—from Fermat's theorem to Gauss's formula to Wagon's algorithm—illustrates a fundamental aspect of mathematical beauty. The initial theorem captures a deep truth about the structure of prime numbers. Gauss's formula reveals an elegant connection between factorials and quadratic residues. And Wagon's algorithm demonstrates how computational constraints can drive mathematical innovation.

The journey from theory to practice in this case mirrors broader patterns in mathematics and computer science. Many beautiful theoretical results find their true value only when paired with efficient algorithms that make them computationally tractable. The interplay between abstract mathematical insight and concrete computational implementation continues to drive progress in number theory and its applications.

For those interested in exploring these ideas further, Wagon's original paper provides a detailed exposition of the algorithm, while standard texts on computational number theory offer broader context about the role of such results in cryptography and other applications. The quest to express primes as sums of two squares, while seemingly abstract, connects to fundamental questions about the nature of numbers and the limits of computation.