# 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
• – Bill Dubuque Jul 1 at 20:50

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
• @Pedro We can use an old idea of Stieltjes to eliminate CRT - see my answer. – Bill Dubuque Jul 2 at 2:08

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

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

$$\,5\nmid n\Rightarrow\,n\mid \color{#c00}{24}\!=\! 5^2\!-\!1,\,$$ else $$\,5\mid n\! =\! {2^{\large j}k},\, 2\nmid k, \,$$ & $$\,(2\!+\!5k)^{\large 2}\!\not\equiv 1\bmod{5}\,$$ so is $$\not\equiv 1\bmod n\$$ QED

• $\!\large \gcd(\color{#0a0}2^{\Large j}\color{#c00}k,\,\color{#0a0}2\!+\!5\color{#c00}k)=1\,$ isn't ad-hoc: it's Stieltjes' twist on Euclid's prime generation $\$ – Bill Dubuque Jul 2 at 22:54

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