We must have a wonderful gradient background here because square number remainder patterns are beautiful. When you square integers and reduce them modulo n, you don’t just get a random number. Insead, square numbers follow predictable patterns. These are called quadratic residues. Note the examples presented below.
| Modulus | Possible square remainders |
|---|---|
| 2 | 0, 1 |
| 3 | 0, 1 |
| 4 | 0, 1 |
| 5 | 0, 1, 4 |
| 6 | 0, 1, 3, 4 |
| 7 | 0, 1, 2, 4 |
| 8 | 0, 1, 4 |
| 9 | 0, 1, 4, 7 |
| 10 | 0, 1, 4, 5, 6, 9 |
Does it make sense? To help with your understanding, let’s pick a number and break it down. Modulo by 10 should be obvious- just find the ones digit- so let’s work with the digit 9.
| Number | Square | Remainder modulo 9 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 2 | 4 | 4 |
| 3 | 9 | 0 |
| 4 | 16 | 7 |
| 5 | 25 | 7 |
| 6 | 36 | 0 |
| 7 | 49 | 4 |
| 8 | 64 | 1 |
We see that the possible remainders, arranged from least to greatest, are 0, 2, 4 and 7. Now, fill out the same table with a different modulus. I would suggest 3, 6, 7 or 8 because they’re more challenging than numbers like 5 and 10.
In summary, these patterns are very useful for math, especially contest math and number theory related questions. These patterns lead to greater concepts such as the Legendre Symbol, and quadratic reciprocity.
