Classification of moduli where relatively prime numbers squared are 1 I came across an interesting property of certain numbers with respect to modular arithmetic and I was wondering if anybody had any more information about them. Consider an integer $n$ such that if $\gcd(a,n)=1, a^2\equiv 1 (\textrm{mod } n)$. I've found a few numbers with this property: $2$ (trivially, though I suppose that $1$ is the most trivial case), $3$, $4$, $6$, $8$, $12$, and $24$. One might think there was a pattern, but unfortunately, $11^2\equiv 25 (\textrm{mod }48)$. 
An interesting fact about these numbers is that if $n$ is such a number with $n>2$ and $x\equiv -1 (\textrm{mod } n)$, then $n|\sigma(x)$ (complementary pairs of divisors sum to a multiple of $n$). Realistically, I assume that such numbers are few and finite- as $n$ grows, $p^2$ is more likely to be less than $n$, and hence incongruent to $p$ mod $n$. If anyone knows of any way to classify them, or a generalization of this property, I'd love to hear it. (Possibly with $x^2\equiv \pm 1$ instead of $1$? In that case, I can also include $5$ and $10$, though this property is still probably rare.)

So here is a way to show that these are all the numbers with the given property and which uses a small bit of machinery.
What we want to show is that if $n = 2^km$ with $m$ odd has this property then $k\leq 3$ and $m=3$ or $m=1$. To see this note that by the Chinese remainder theorem, it suffices to find those prime powers $p^r$ for which the units in $\mathbb{Z}/p^r\mathbb{Z}$ has the property. But these groups of units are cyclic of order $p^{r-1}(p-1)$ when $p$ is odd, so the only odd prime we can have is $3$ and we cannot have $3^2$ as a factor.
Similarly, the group of units of $\mathbb{Z}/2^k\mathbb{Z}$ has an element of order $2^{k-2}$ as long as $k\geq 2$ (for example the element $5$), and hence the largest possible power of $2$ is $2^3$.
