If n is such that every element $(\mathbb{Z}/n\mathbb{Z})^{*}$ 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 it true. Such that $(\mathbb{Z}/8\mathbb{Z})^{*}$ includes elements: 1,3,5,7 and all of these are roots of $1-x^2$ in mod 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 though of how to do this proof and what theorems would be appropriate to use.

• Hint: First prove this for primes. – Prahlad Vaidyanathan Oct 13 '13 at 17:33
• @PrahladVaidyanathan What do you mean? – Pedro Tamaroff Oct 13 '13 at 17:47
• Is this what you are saying: If, for each integer $k$ such that $0 \le k < n$ and $k$ and $n$ are relatively prime, $k$ divides $k^2-1$, then $n$ divides $24$. – marty cohen Oct 13 '13 at 17:55
• More extensive hint: Chinese remainder theorem + the fact that $(\mathbb Z/p^k\mathbb Z)^*$ is cyclic for any prime $p>2$. Finally that it fails for 16 (to treat the case $p=2$). – user8268 Oct 13 '13 at 17:58

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

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

• I cannot see why $(k,n)=1$. – Pedro Tamaroff Oct 18 '13 at 5:37
• @PedroTamaroff $(k,m)=1$ from the first relation and $5 \nmid k$ from the second relation. Thus, $(k,m)=1$ and $(k,5^a)=1 \Rightarrow (k, 5^am)=1$.... Or, if you prefer if $p$ is a prime dividing $k$, the first relation tells you it cannot divide $m$, while second tells you $p \neq 5$. – N. S. Oct 18 '13 at 5:46
• Yes, got it. This is a very elegant solution. – Pedro Tamaroff Oct 18 '13 at 5:48
• @PedroTamaroff Ty :) – N. S. Oct 18 '13 at 5:49

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]=,$ 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$.

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

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. • That is not correct. (\Bbb Z/12\Bbb Z)^\times also enters in the picture, say, since 1^2=5^2=7^2=11^2=1. – Pedro Tamaroff Oct 13 '13 at 18:04 HINT:$$(6a\pm1)^2=36a^2\pm12a+1=24a^2+24\frac{a(a\pm1)}2+1\equiv1\pmod{24}$\$