3) Find all the ordered pairs \( r, s \) of positive integers such that \( r^2 + s^2 = 999 \).
Proof. A positive integer \( n \) can be written as the sum of two squares iff all primes \( p \) dividing \( n \) of the form
\( p \equiv 3 \; (\text{mod} \; 4) \) appear in the prime power factorization of \( n \) an even number of times. But \( 999 = 3^2 \cdot 111 = 3^3 \cdot 37 \),
so \( 3 \) appears an odd number of times and 999 cannot be represented at all as the sum of two squares of integers.
A simpler approach is to note that for all \( z \in \mathbb{Z}, z^2 \equiv 0 \; (\text{mod} \; 4) \) or \( z^2 \equiv 1 \; (\text{mod} \; 4). \)
Therefore \( r^2 + s^2 \equiv 0, 1, 2 \; (\text{mod} \; 4). \) But \( 999 \equiv 3 \; (\text{mod} \; 4), \) so 999 cannot equal the sum of two squares.
QED.
Note: The first paragraph follows from Corollary 19 in §8.3 of Dummit & Foote.