The sequence of squares of non-zero elements is palindromic as we proved all such sequences must be. But unlike sequences of squares in fields, there are some repetitions besides the required plus/minus pairs, which means some numbers have more than two square roots. For example, 1 has four square roots, ±1 and ±4. The table of squares for Z₁₀, on the other hand, doesn’t have any repetitions from 0 to 5 and so no numbers have more than two square roots (mod 10).

After working out the tables of squares for Z₂₀ through Z₃₀, we discovered that there were no repetitions of the squares from 0 to n/2 for Z₂₂, Z₂₃, Z₂₆, and Z₂₉, while there were repetitions for Z₂₀, Z₂₁, Z₂₄, Z₂₅, Z₂₇, Z₂₈, and Z₃₀. Examining this we conjectured that

• The tables of squares for Z_n have no repetitions from 0 to n/2 if n is either prime or twice an odd prime.

The first rule is illustrated by the fact that Z₁₀ has no repetitions from 0 to 5 while Z₁₅ has repetitions with both 1² = 1 and 4² =1, and both 2² = 4 and 7² = 4. Of course, 10 is twice a prime while 15 is not. We had proved that there couldn’t be any repetitions for Z_p with p prime earlier, since such Z_p are fields. That it also worked for Z_2p, which aren’t fields, was a little surprising. Trying to understand why this should be true, we then looked at when repetitions occurred in the other cases. For example, in Z₁₅ we have repetitions for 1 and 4 and for 2 and 7. After some thought, it was noted that 4 + 1 = 5 and 4 - 1 = 3, and 3 ´ 5 = 15. Similarly, 7 + 2 = 9 and 7 - 2 = 5, and 5 ´ 9 = 45 = 3 ´ 15. After a little bit of algebra, we observed that a² = b² (mod n) if and only if a² - b² = 0 (mod n) which happens if and only if (a + b)(a - b) = 0 (mod n). From this relationship we can determine a number of things as illustrated in the next several examples.

Example: Find a and b with a ¹ ±b but a² = b² (mod 253).

We first factor 253 to get 253 = 11 ´ 23. So we look for a and b with a + b = 23 and a - b = 11. Doing the algebra, we get a = (23 + 11)/2 = 17 and b = (23 - 11)/2 = 6. We check 17² = 289 = 36 = 6² (mod 253).

Example: Factor 10573 given the hint that 406² = 79² (mod 10573).

From the given, we can conclude that (406 + 79) ´ (406 - 79) = 0 (mod 10573). We check that 485 ´ 327 = 158595, and, dividing by 10573, we get 108595 = 15 ´ 10573, so 485 ´ 327 = 15 ´ 10573. Now we factor 485 = 5 ´ 97 and 327 = 3 ´ 109 (this is easier than factoring 10573 since the numbers are much smaller). Plugging these factors into our previous equation we get 5 ´ 97 ´ 3 ´ 109 = 15 ´ 10573, and canceling out 15 from each side leaves us with the factorization of 10573 = 97 ´ 109.

These are very useful examples, for they suggest how looking for repetitions of squares can lead to factoring large numbers, and, in fact, these ideas are used in various practical algorithms for factoring. Factoring numbers is the key to breaking RSA public key encryption so such applications are quite important. We will study them in the next lectures. But we still have to finish the question that started our considerations of these ideas in this lecture, why are there no repetitions for Z_2p?

Theorem: If 0 £  a,b £  p (with a ¹  b), then a² ¹  b² (mod 2p).

Proof: Suppose a² = b² (mod 2p). Then (a + b)(a - b) = 0 (mod 2p), which means (a + b)(a - b) = y ´ 2 ´ p for some y. Since p is a prime, in order for p to be a factor of the right-hand side it must be a factor of one of the terms on the left-hand side. Due to the restriction that 0 £ a,b £ p, it follows that a + b = p. This implies that a - b = 2 ´ y. Now when we use algebra to solve for a and b, we get a = (p + 2y)/2 and b = (p - 2y)/2. But since p is odd and 2y is even, neither a nor b are integers, so there can be no such a, b pair in Z_2p.

We haven’t proved that there always will be repetitions for the other cases, but that isn’t hard, just tedious. Using the techniques of the first example you can always find a repetition. You just have to go through the details to check that by appropriat e choices of factors you can always get a and b to turn out to be integers rather than half-integers.