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.  
 A: Case 1: $5 \nmid n$.
Then $5^2 \equiv 1 \pmod n$ and hence $n|24$.
Case 2: $5 \mid n$. Let $n=5^am$ with $\gcd(5,m)=1$. By the Chinese Remainder Theorem, we can find some $k$ so that
$$\begin{cases} k \equiv 1 \pmod{m} \\
k \equiv 2 \pmod{5} \end{cases}$$
Then $\gcd(k,n)=1$ and hence 
$$k^2 \equiv 1 \pmod{n}$$
As $5\mid n$ we get that 
$$k^2 \equiv 1 \pmod{5}$$
But this contradicts $k \equiv 2 \pmod{5}$.
A: 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>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>1$. Since $(\Bbb Z/3^{m}\Bbb Z)^\times$ is cyclic of order $\geqslant 6$ we cannot have $m>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 >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$.
A: An algebraic approach is as follows:
Let us prove first the assertion for $n$ power of a prime. So suppose $\mathbb{Z/p^eZ}$ is such that for all $x\in(\mathbb{Z/p^eZ})^*$, $x^2-1=0$, then all the elements of the group $(\mathbb{Z/p^eZ})^*$ have order $2$, then by the First Sylow Theorem $(\mathbb{Z/p^eZ})^*$ has order $2^n$ for some $n$. Thus $\varphi(p^e)=p^{e-1}(p-1)=2^n$; Euler's totient function.
Now I claim that we must have that $p=2,3$. For suppose not, then $[p^e-2]^2=[p^{2e}-4p^e+4]=[4],$ with $4<p$, however, as  $p^e-2$ must be invertible in $\mathbb{Z/p^e}$; $e=1$, this is a contradiction. So we can only have $p=2$ with $e=0,1,2,3$ or $p=3$ with $e=0,1$
Now, let $n$ be such that the property holds for $(\mathbb{Z/nZ})^*$. Let $n=p_1^{e_1}\cdots p_n^{e_n}$ be its prime factorization,then $$(\mathbb{Z/nZ})^*\simeq((\mathbb{Z/p_1^{e_1}Z}))^*\times\cdots\times(\mathbb{Z/p_m^{e_m}Z})^*,$$
and so the property must also hold for $(\mathbb{Z/p_i^{e_i}Z})^*$, hence $m\leq 2$ with $p_1,p_2\in\{2,3\}$, $e_1=0,1,2,3$ and $e_2=0,1$.
A: $\,\overbrace{{\rm if}\,\ 5\!\nmid\! n\,\ {\rm then}\,\ n\,|\, \color{#90f}{24}\!=\! 5^2\!-\!1}^{\large \text{by hypothesis}},\,$ else $\,5\!\mid\! n =\!\! \overbrace{\color{#0a0}2^{\large j}\color{#c00}k}^{\large {\rm odd}\  \color{#c00}k}\!, \,$ &  $\,(\color{#0a0}2\!+\!5\color{#c00}k)^{\large 2}\!\not\equiv 1\bmod{5},\,$ so  $\not\equiv 1\bmod n.\, $ $\small\bf QED$
A: If $x^2 = 1$ for every element of an abelian group, then it must have a very particular structure.
The answers to this question describe the structure of $(\mathbb{Z} / n \mathbb{Z})^\times$. 
A: 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$.
