NT-B2-M02-P001 Table of Squares

It is enough to check residues \(0,1,\ldots,15\), but one can also separate even and odd numbers.

If the number is even, \(n=2k\), then \(n^2=4k^2\), and \(k^2\pmod4\) is \(0\) or \(1\), giving \(0\) or \(4\). If the number is odd, \(n=2k+1\), so \(n^2=4k(k+1)+1\); since \(k(k+1)\) is even, \(n^2\equiv1\) or \(9\pmod{16}\). Thus the possible residues are \(0,1,4,9\).

This is the starting table for modulo \(16\) problems.