There is a theorem of Euler which regularly turns up on lists of "most beautiful theorems of all time." It concerns odd primes which can be represented as the sums of two squares. You can easily find examples of such primes. 5 is one, because it is 4+1, and 4 and 1 are squares. 7 is not one, however. There aren't many squares you can use, because 3^2=9 is already bigger than 7. You only get to use 4 and 1, and these only produce 2, 5, and 8, of which only 5 is an odd prime, as we already noted. (The only even prime, 2, is also a sum of squares, notice!)
You can see one thing quickly if you take the equation x^2+y^2=p, thought of as an equation for x and y, given p, and reduce it mod 4. Since p is an odd prime, it is either 1 or 3 (mod 4). But the only squares (mod 4) are 0 and 1. Thus x^2 and y^2 are each 0 or 1 (mod 4). They could add to 1, if one of them is 0 and one of them is 1, but they could not add to 3. Thus it is impossible for a prime p which is 3 (mod 4) to be a sum of squares! That is consistent with what we noticed first: 7, which is 3 (mod 4) is not a sum of squares. On the other hand 5, which is 1 (mod 4), IS a sum of squares.
Thus the only possible odd primes p which could be sums of squares are the ones which are 1 (mod 4). Of those, which ones actually are sums of squares? A little experimentation seems to show that it is hard to find one which is NOT a sum of squares. And, as Euler proved, in fact EVERY prime which is 1 (mod 4) is a sum of squares, and in an essentially unique way. Thus, 5=4+1, 13=4+9, 17=16+1, 29=25+4, 37=36+1, 41=25+16, etc. Somehow the squares are there to make every one of these primes!
This theorem is a statement about the integers, but it can be proved using modular arithmetic (integers mod p). Let p be a prime which is 1 (mod 4). If we reduce the equation x^2+y^2=p modulo p, we find x^2+y^2=0 (mod p). The basic idea is to solve for x and y in Zp, where arithmetic is more versatile, and then to find among those solutions one that solves the original problem in Z. The way to do that is to find a solution in Zp* in which x and y are each less than the square root of p. If the squares add to 0 (mod p), it means they add to a multiple of p. But if x^2 and y^2 are each greater than zero and less than p, what multiple of p could it be? Only p itself!
Thus we are really only going to be looking at a small part of Zp*: 1, 2, 3, ..., m, where m is the first integer greater than the square root of p. Note that m^2 > p. This will be important later. Now we solve x^2+y^2=0 in Zp:
Multiply through by the inverse of y^2 in Zp* (we will notate this as "dividing" by y^2):
Now, as we noted recently, -1 has a square root in Zp* precisely when p=1 (mod 4). [Recall the reason: Zp* is cyclic, so let a be a generator. The element -1 is a square root of 1=a^(p-1), so -1=a^(p-1)/2. The exponent (p-1)/2 is even exactly when p=1 (mod 4).] Thus we can take square roots on both sides and find
where k is a square root of -1. Now multiply through by y and bring everything to one side:
As noted before, we are especially looking for solutions x and y which are small. In fact, consider evaluating x-ky (mod p) for x and y in the range 1, 2, ..., m. With each evaluation we get some number in Zp, and there are only p such numbers, but there are m^2 different evaluations, and as we noted earlier, m^2 > p. Thus some number in Zp must occur more than once, because there are more places to fill, in a table of evaluations, than there are different numbers to go into the table. This is sometimes called "the pigeonhole principle." Thus, for two different choices (x,y) and (x',y'), we get the same evaluation:
Bringing everything to one side we find
and this is the solution in Zp* that we were after. The quantities (x-x') and (y-y') are integers less (in magnitude) than the square root of p, and their squares add to 0 (mod p), i.e. they add to p in the regular integers.
Here are two examples: take p = 5. Then, since the square root of 5 is 2.236..., we have m=3. Also, a square root of -1 in Z5* is k=2. So we evaluate x-2y in Z5, letting each of x and y take the values 1, 2, 3:
| y x -> | 1 | 2 | 3 |
| 1 | 4 | 0 | 1 |
| 2 | 2 | 3 | 4 |
| 3 | 0 | 1 | 2 |
We notice that there is a 0, i.e., a solution, for x=2, y=1, and this is in fact a solution of the original problem: 2^2+1^2=5. There is also a 0, i.e., a solution, for x=1, y=3, but this is only a solution in Z5, not a solution to the original problem, since 1^2+3^2=1+9=10=0 (mod 5), but the sum of squares is 10, not 5. The first solution worked because x and y were both strictly less than 3. Now the proof of the theorem guarantees that there will always be a solution, like x=2, y=1 above, but it relies on a repetition in the table (the pigeonhole principle). Here, since there are 9 evaluations and only 5 different values, there must be a repetition, and we see, for example, that (x,y)=(1,1) and (x',y')=(3,2) both give the same value 4. Hence x'-x=2 and y'-y=1 must be a solution to the original problem. This illustrates how the general proof works, and why there must be a 0 in a suitable place in the table.
2nd example: p=13. Now m=4, k=5. We evaluate x-5y in Z13* for x, y = 1, 2, 3, 4:
| y x -> | 1 | 2 | 3 | 4 |
| 1 | 9 | 10 | 11 | 12 |
| 2 | 4 | 5 | 6 | 7 |
| 3 | 12 | 0 | 1 | 2 |
| 4 | 7 | 8 | 9 | 10 |
We notice that there is a solution at x=2, y=3, and of course it is true that 4+9=13. But the reason there must be a solution is that with 13 values to go into 16 places in the table, there must be repetitions (pigeonhole principle). In fact, the value 7 occurs twice, for example, with (x,y)=(4,2), and with (x',y')=(1,4). Therefore x-x'=3 and y-y'=-2 is a solution. Since squaring -2 gives the same thing as squaring 2, we recover the solution in the usual form (3,2), although this computation does point out that (3,-2) is also a way to represent 13 as the sum of two squares, 3^2 +(-2)^2.
This example could also have noted that 10 occurs twice, with (x,y)=(4,4) and (x',y')=(2,1). Therefore there is a solution (x-x')=2, (y-y')=3, etc. But it is always, in effect, the same solution: the squares are 4 and 9, in either order. That is the only way to do it.
Do a 3rd example, with p=17. Since 17 = 1 (mod 4), it should work the same way. Determine m, find k (a square root of -1 in Z17*), etc. Fill in the table of x-ky, point out the solution, and why there must be a solution, using the pigeonhole principle.