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.

Solution 1:

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}$.

Solution 2:

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$.

Solution 3:

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$.

Solution 4:

$\,\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}^{k\ \rm odd}, \,$ & $\,(\color{#0a0}2\!+\!5\color{#c00}k)^{\large 2}\!\not\equiv 1\bmod{5}\,$ so $\not\equiv 1\bmod n.\, $ $\small\bf QED$