The Art and Craft of Problem Solving

7.5 MISCELLANEOUS INSTRUCTIVE EXAMPLES 251

This is promising. Here is an outline of a possible "algorithm" for solving x^2 +
y^2 =p.

1. First find the square root of - 1 in Zp. Call it u.

2. Then we can factor x^2 + y^2 = (x - uy) (x + uy) (mod p), and consequently the

pairs y = k,x = uk, for k = 1 ,2, ... will solve the congruence

x^2 +l =0 (modp).

In other words, x^2 + y^2 will be a multiple of p.

3. If we are lucky, when we reduce the values of these solutions modulo p, we

may get a pair of x and y that are sufficiently small so that not only will x^2 + y^2

be a mUltiple of p, it will actually equal p.

There are two major hurdles. First, how do we know if we can always find a square

root of - 1 modulo p? And second, how do we ensure that the values of x and y will

be small enough so that x^2 + y^2 will equal p rather than, say, 37 p?

Do some experiments with primes under 50, and a calculator or computer if you

wish, to determine for which primes p will the square root of -1 exist modulo p. You

should discover that you can always find R in Zp if p = 1 (mod 4 ), but never if

p = 3 (mod 4).

Sure enough, it seems that it may be true that

x^2 = - 1 (mod p)

has a solution if and only if p = 1 (mod 4 ). But of course, numerical experiments

only suggest the truth. We still need to prove something.

For the time being, let's not worry about this, and just assume that we can find the

square root of - 1 modulo p whenever we need to. Let's return to the second hurdle.

We can produce infinitely many pairs (x,y) such that x^2 + y^2 is a multiple of p. All we
need to do is get the values small enough. Certainly, if x and yare both less than .jj5,

then x^2 + y^2 < 2 p, which forces x^2 + y^2 = p. That is helpful, for if u < yip, we are

immediately done. The pair y = 1 , x = u will do the trick.

On the other hand, what if u > .jj5 (notice that it cannot equal .jj5, since p is

prime and hence not a perfect square)? Let t := l.jj5 J. Then the problem is reduced

to showing that one of

±u, ±2u, ±3u, ... , ±tu,

when reduced modulo p, will be less than .jj5 in absolute value.

Let's try an example for p = 29. We have t : = l J29J = 5, and u = 17 (found by

trial and error; verify that it works!). Since u > t, we need to look at the sequence

u, 2u, 3u, 4u, 5u,

reduced modulo 29. Draw a picture:

I I I I I

o

2u

I I I

4u

-I

I

u

I I I I I

I

_ I I I I I I I

5u

r

I

�9