a diophantine puzzle for abstract algebra students A Diophantine Puzzle We give an application of ring theoretic methods to study a classical problem: which primes p in Z are sums of two squares? Trial and error suggests that the answer is p = 2 = 1^2+1^2, and those p which are congruent to 1(mod 4), such as 5 = 1^2+2^2, 13 = 2^2+3^2, 17 = 1^2+4^2, 29 = 5^2+2^2, 37 = 6^2+1^2, 41 = 5^2+4^2, 53 = 2^2+7^2,....... Assume the elementary fact from number theory that x^2+1 has roots in Z/p for precisely such p. Can we make a link between these two problems? I.e. can we prove somehow that p is a sum of two squares iff X^2+1 has roots mod p? Consider the following argument: Notice that if p=a^2+b^2, then using complex numbers we get p = (a+bi)(a-bi), so p is no longer prime in the ring Z. Conversely, if p = (a+bi)(c+di) in Z then taking absolute values on both sides and squaring, we get p^2 = (a^2+b^2)(c^2+d^2), and by uniqueness of prime factorization in Z, there are only two prime factors on the right, both equal to p, hence p = a^2+b^2. Thus a prime p in Z is no longer prime in Z iff p is a sum of two squares. Now introduce (Z/p) as follows: Since Z/(p) isom to (Z/p) isom to (Z/p)[X]/(X^2+1), then p is a sum of two squares iff p not prime in Z iff (Z/p) is not a domain iff X^2+1 is not prime in (Z/p)[X] iff X^2+1 has roots mod p iff p = 2 or p cong to 1(mod 4). Ok? Now consider: Puzzle: If we use these ideas to analyze the equation X^2+5Y^2 = p, we seem to get that p = a^2+5b^2 for some a,b iff p is not prime in Z[sqrt(-5)] iff (Z/p)[sqrt(-5)] not a domain iff X^2+5 not prime in (Z/p)[X] iff X^2+5 has roots mod p. But what about p = 3? Then X = 1 is a root of X^2+5 (mod 3), but obviously X^2+5Y^2 = 3 has no integral solution. What gives?