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.

  • 2
    $\begingroup$ Hint: First prove this for primes. $\endgroup$ – Prahlad Vaidyanathan Oct 13 '13 at 17:33
  • $\begingroup$ @PrahladVaidyanathan What do you mean? $\endgroup$ – Pedro Tamaroff Oct 13 '13 at 17:47
  • $\begingroup$ 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$. $\endgroup$ – marty cohen Oct 13 '13 at 17:55
  • $\begingroup$ 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$). $\endgroup$ – user8268 Oct 13 '13 at 17:58
  • $\begingroup$ See also A high-powered explanation for $\exp U(n)=2\iff n\mid24$? $\ \ $ $\endgroup$ – 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}$.

  • $\begingroup$ I cannot see why $(k,n)=1$. $\endgroup$ – Pedro Tamaroff Oct 18 '13 at 5:37
  • $\begingroup$ @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$. $\endgroup$ – N. S. Oct 18 '13 at 5:46
  • $\begingroup$ Yes, got it. This is a very elegant solution. $\endgroup$ – Pedro Tamaroff Oct 18 '13 at 5:48
  • $\begingroup$ @PedroTamaroff Ty :) $\endgroup$ – N. S. Oct 18 '13 at 5:49
  • $\begingroup$ @Pedro We can use an old idea of Stieltjes to eliminate CRT - see my answer. $\endgroup$ – 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

  • $\begingroup$ $\!\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 $\ $ $\endgroup$ – Bill Dubuque Jul 2 at 22:54

Let $x=2m+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$.

  • $\begingroup$ 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$. $\endgroup$ – Pedro Tamaroff Oct 13 '13 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.