If n is such that every element $(\mathbb{Z}/n\mathbb{Z})^{\times}$ is a root of $x^2-1$. Prove that $n$ divides 24. I have a hard time formulating proofs.  For this problem, I  can see that if $n$ is equal to $8,$ this statement is true.  $(\mathbb{Z}/8\mathbb{Z})^{\times}$ includes elements:  $1,3,5,7$, and all of these are roots of $1-x^2 \pmod 8.$  And obviously $8$ divides $24.$

But how do I prove this without depending on number calculations and only using theorems?  Help Please?  I need a step by step walk through of how to do this proof and what theorems would be appropriate to use.
Suppose that $n=2^\ell 3^{m}p_1^{e_1}\cdots p_r^{e_r}$. We know that $$(\Bbb Z/n\Bbb Z)^\times\simeq (\Bbb Z/2^\ell\Bbb Z)^\times\times (\Bbb Z/3^{m}\Bbb Z)^\times\times (\Bbb Z/p_1^{e_1}\Bbb Z)^\times\times \cdots \times (\Bbb Z/p_r^{e_r}\Bbb Z)^\times$$

Suppose $p&gt;3$. We know $(\Bbb Z/p_r^{e_r}\Bbb Z)^\times$ is cyclic of order $\geqslant 4$, so $x^2=1$ for each $x$ is impossible. Thus we necessarily need $n=2^\ell 3^m$, that is $$(\Bbb Z/n\Bbb Z)^\times\simeq (\Bbb Z/2^\ell\Bbb Z)^\times\times (\Bbb Z/3^{m}\Bbb Z)^\times$$

Suppose $m&gt;1$. Since $(\Bbb Z/3^{m}\Bbb Z)^\times$ is cyclic of order $\geqslant 6$ we cannot have $m&gt;1$. Thus we have

$$(\Bbb Z/n\Bbb Z)^\times\simeq (\Bbb Z/2^\ell\Bbb Z)^\times\times (\Bbb Z/3^{m}\Bbb Z)^\times$$
with $m=0,1$. It remains to show $\ell=0,1,2,3$. Finally, if $\ell \geqslant 3$, $$(\Bbb Z/2^\ell\Bbb Z)^\times\simeq C_2\times C_{2^{\ell-2}}$$

If $\ell &gt;3$ we have $2^{\ell-2}\geqslant 4$, incompatible with $x^2=1$. Thus you know that $n$ must be of the form $n=2^\ell 3^m$ with $\ell=0,1,2,3$ and $m=0,1$.
Let $x=2m+1$.

$x^2-1=(x+1)(x-1)=(2m+2)(2m)=2^2m(m+1)$.

$m(m+1)$ is divisible by $6$ except when $m \equiv 1 $ or $4$$(mod 6)$, and $x^2-1$ is a multiple of $24$ except for those cases. Let's call the cases in which $m(m+1)$is divisible by 6 as Case I and others as Case II.

$2^2m(m+1)$ must be divisible by $n$ for arbitrary $m$. The periodicity of appearance of factors $2$ and $3$ in $m(m+1)$ needs to be discussed here since they are the factors which frequently appear in $m(m+1)$. If there's no such periodicity, not every odd elements will be divided by $n$. 

Case I:

When $m=0$, $2^2m(m+1)\equiv 0(mod n)$.

When $m=2$, $2^2m(m+1)\equiv 24(mod n)$.

When $m=3$, $2^2m(m+1)\equiv 48(mod n)$.

When $m=5$, $2^2m(m+1)\equiv120(mod n)$.

Case II:

When $m=1$, $2^2m(m+1)\equiv8(mod n)$.

When $m=4$, $2^2m(m+1)\equiv80(mod n)$.

If for every element of $(\mathbb{Z}/n\mathbb{Z})^*$, $x^2-1$ is divisible by $n$, then n must be a divisor of $8$ and divide $24$.