Show that if \(\displaystyle n\) is composite, \(\displaystyle n \neq 2p\) (for prime p), then there at least 4 different residues modulo n, whose squares equal 1.

To make this easy to follow, suppose we're dealing with \(\displaystyle \{0,1,\ldots,n-1\}\), the standard residue system modulo \(\displaystyle n\). Given any \(\displaystyle n\) composite, we're always guaranteed two residues with this property since \(\displaystyle 1^2\equiv 1\pmod{n}\) and \(\displaystyle (n-1)^2\equiv n^2-2n+1\equiv 1\pmod{n}\).

Let \(\displaystyle a\) be a residue modulo \(\displaystyle n\) (where \(\displaystyle n\neq 2p\)) with \(\displaystyle 1<a<n-1\) and let \(\displaystyle (a,n)=1\). Then \(\displaystyle a^{\varphi(n)}\equiv 1\pmod{n}\) by Euler's Theorem. Keeping in mind that \(\displaystyle 2\mid \varphi(n)\) when \(\displaystyle n>2\), we see that \(\displaystyle a^{\varphi(n)}\equiv \left(a^{\varphi(n)/2}\right)^2\equiv 1\pmod{n}\). Thus, \(\displaystyle a^{\varphi(n)/2}\) is a residue that satisfies this property. Consequently, \(\displaystyle -a^{\varphi(n)/2}\equiv n-a^{\varphi(n)/2}\pmod{n}\) is also another residue. This one generates a residue different from \(\displaystyle 1\) since we required \(\displaystyle n\neq 2p\) and it can't generate \(\displaystyle n-1\); if it did, then \(\displaystyle n-1\equiv n-a^{\varphi(n)/2}\pmod{n}\implies a^{\varphi(n)/2}\equiv 1\pmod{n}\), which isn't possible given the restrictions we made on the problem.

This shows that we are guaranteed four different residues modulo \(\displaystyle n\) with this property. We then allow for the possibility of more residues as we allow \(\displaystyle n\) to increase.

Does this make sense?