The Art and Craft of Problem Solving

250 CHAPTER 7 NUMBER THEORY

Sums of Two Squares

We shall end the chapter with an exploration of the diophantine equation

Y-+i =n.

We won't produce a complete theory here (see [30] for a very readable exposition),

but we will consider the case where n is a prime p. Our exploration will use several

old strategic and tactical ideas, including the pigeonhole principle, Gaussian pairing,

and drawing pictures. The narrative will meander a bit, but please read it slowly and

carefully, because it is a model of how many different problem-solving techniques

come together in the solution of a hard problem.

First recall that Y-+ i = p will have no solutions if p == 3 (mod 4) (Example 7.4.2

on page 242). The case p = 2 is pretty boring. So all that remains to investigate are

primes that are congruent to I modulo 4.

7.5.8 Find solutions to.x2 + y2 = p, for the cases p = 5, 13, 17,29,37,41.

By now you are probably ready to guess that x2 + y2 = p will always have a solu­

tion if p == 1 (mod 4). One approach is to ponder some of the experiments we just did,

and see if we can deduce the solution "scientifically," rather than with trial-and-error.

Let's try p = 13. We know that one solution (the only solution, if we don't count sign

and permuting the variables) is x = 3, y = 2. But how do we "solve"

Y- +i=13?

This is a diophantine equation, so we should try factoring. "But it doesn't factor," you

say. Sure it does! We can write

(x+yi)(x-yi) = 13,

where i is of course equal to the square root of - 1. The only problem, and it is a huge

one, is that i is not an integer.

But let's stay loose, bend the rules a bit, and make the problem easier. It is true

that the square root of - 1 is not an integer, but what if we looked at the problem in

Z 13? Notice that

52 = 25 == - 1 (mod 13).

In other words, i "makes sense" modulo 13. The square root of - 1 is equal to 5 modulo

13.

If we look at our diophantine equation modulo 13, it becomes

x^2 +i == 0 (mod 13),

but the left-hand side now factors beautifully. Observe that we can now write

x 2 +i == (x- 5 y)(x+ 5 y) (mod 13),

and therefore we can make x2 + y2 congruent to 0 modulo 13 as long as x == ±5y

(mod 13). For example, y = 1 , x = 5 is a solution (and sure enough, .x2 + y2 = 26 == 0

(mod 13). Another solution is y = 2, x = 10, in which case .x2 + y2 = 104, which is

also a multiple of 13. Yet another solution is y = 3, x = 15. If we reduce this modulo

13, it is equivalent to the solution y = 3, x = 2 and this satisfies.x2 + y2 = 13.