252 CHAPTER 7 NUMBER THEORY
The small ticks are the integers from 0 to 29, while the long ticks are placed at the
locationsy'p, 2y'p, 3y'p, 4y'p, 5y'p.
Notice that both 2u = 34 = 5 (mod 29) and 5u = 85 = -2 (mod 29) work, yielding
respectively the solutions y = 2, x = 5 and y = 5, x = -2. But why did it work? In
general, we will be dropping dots onto the number line, and would like to see a dot
land either to the left of the first long tick, or to the right of the last long tick. The dots
will never land exactly on these ticks, since they correspond to irrational values. Weare assuming without loss of generality that u > .,;p. In general, there are t long ticks.
The sequence u, 2u, ... ,tu consists of distinct values modulo p (why?), so we will be
placing t different dots on the number line. There are three possibilities.
1. One of the dots lands to the left of the first long tick.
2. One of the dots lands to the right of the last long tick.
3. The dots don't land in either of the above locations.
In cases 1 or 2, we are immediately done. In case 3, we have t dots that lie in
t - 1 intervals (separated by long ticks). By the pigeonhole principle, one of these
intervals must contain two dots. Suppose mu and nu lie in one interval. This means
that (m - n)u will be an integer (perhaps negative), but smaller than .,;p in absolute
value. Since 1m -nl ::; t, we can just choose k:= 1 m - nl and we are guaranteed that
y = k and x = ku (when reduced modulo p) will both be less than .,;p. So we're done!
That was a fun application of the pigeonhole principle. All that remains is to provethat we can alway s obtain the square root of - 1. We have one tool available, something
proven earlier that seemed a curiosity then: Wilson 's theorem. Recall that Wilson'stheorem (Example 3.1.9 on page 68) said that if p is a prime, then (p - I)! = - 1
(mod p). A small dose of Gaussian pairing can reorganize (p - I)! into a perfect
square modulo p, provided that p = 1 (mod 4). In that case p - 1 will be a mUltiple
of 4, so the individual terms in (p - I)! can be arranged in an even number of pairs.
For example, let p = 13. We can then write
12! = (1· 12)(^2 ·11)(3·10)(4·9)(5·8)(6·7).
Each pair has the form k· (-k) modulo 13, so we have
12! = ( 12 )( 22 )( 32 )( 42 )( 52 )( 62 ) (mod 13),
and since there are an even number of minus signs in this product, the whole thing iscongruent to (6!)^2 modulo 13. Combining this with Wilson's theorem yields
(6!)^2 =-1 (mod 13).
The argument certainly generalizes to any prime p of the form 4k + 1. Not only have
we shown that the square root of - 1 exists, we can compute it explicitly. Our general
result is that