The Art and Craft of Problem Solving

242 CHAPTER 7 NUMBER THEORY

Example 7.4.2 Find all solutions to the diophantine equation x^2 + y^2 = 1000003.

Solution: Consider the problem modulo (^4). The only quadratic residues in Z 4

are 0 and 1, because

02 =0, 1^2 =1, 2^2 =0, 3^2 =1 (mod 4).

Hence the sum x^2 + y^2 can only equal 0, 1 or 2 in Z 4. Since 1000003 = 3 (mod 4), we

conclude that there are no solutions. In general, x^2 + y^2 = n will have no solutions if

n=3 (mod 4). _

Now let's move on to a meatier problem: the complete theory of Pythagorean

triples.

Example 7.4.3 Find all solutions to

(4)

Solution: First, we make the basic simplifications. Without loss of generality,

we assume of course that all variables are positive. In addition, we will assume that

our solution is primitive, i.e., that the three variables share no common factor. Any

primitive solution will produce infinitely many non-primitive solutions by mUltiplying;

for example (3,4, 5) gives rise to (6,8,10), (9, 12,15), ....

In this particular case, the assumption of primitivity leads to something a bit

stronger. If d is a common divisor of x and y, then d^21 x^2 + y^2 ; in other words, d^21 z^2 so

dlz. Similar arguments show that if d is a common divisor of any two of the variables,

then d also divides the third. Therefore we can assume that our solution is not just

primitive, but relatively prime in pairs.

Next, a little parity analysis; i.e., let's look at things modulo 2. Always begin with

parity. You never know what you will discover. Let's consider some cases for the

parity of x and y.

• Both are even. This is impossible, since the variables are relatively prime in

pairs.

• Both are odd. This is also impossible. By the same reasoning used in Exam­

ple 7.4.2 above, if x and yare both odd, it will force z^2 = 2 (mod 4), which

cannot happen.

We conclude that if the solutions to (4) are primitive, then exactly one of x and y is

even. Without loss of generality, assume that x is even.

Now we proceed like a seasoned problem solver. Wishful thinking impels us to try

some of the tactics that worked earlier. Let's make the equation factor! The obvious

step is to rewrite i t as

(5)

In other words, the product of z -y and z + y is a perfect square. It would be nice to

conclude that each of z -y and z + y are also perfect squares, but this is not true in

general. For example, 62 = 3. 12.