Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $n >1$ such that $(\mathbb{Z}/n \mathbb{Z})^\times $ is not cyclic. Then show that for each $a \in \mathbb Z$ with $\gcd(a,n)=1$ we have $a^{\frac{\varphi (n)}{2}} \equiv 1 \mod n$. (Here $\varphi$ is the Euler function.)

I cannot find a solution to this problem, been trying for a long time.

(Remark: it is clear that $\varphi (n ) $ is even.)

share|cite|improve this question

Since the unit group of $(\mathbb{Z}/n\mathbb{Z})$ is not cyclic, then $n$ is not prime, an odd prime power, twice an odd prime power, or $4$.

If $n$ is a power of $2$, $n=2^{m}$, with $m\gt 2$, then $(\mathbb{Z}/n\mathbb{Z})^{\times}$ is isomorphic to $C_2\times C_{2^{m-2}}$, which has exponent $2^{m-2}$. Since $\phi(n) = 2^{m-1}$ is a multiple, the conclusion follows.

Otherwise, there are primes $p\lt q$ that divide $n$. Write $n$ as $p^a q^b r$, where $\gcd(p,r)=\gcd(q,r)=1$. Then $\phi(n) = (p-1)p^{a-1}(q-1)q^{b-1}\phi(r)$. Thus, $$(\mathbb{Z}/n\mathbb{Z})^{\times} \cong (\mathbb{Z}/p^a\mathbb{Z})^{\times}\times (\mathbb{Z}/q^b\mathbb{Z})^{\times}\times (\mathbb{Z}/r\mathbb{Z})^{\times}.$$ Now, if both $p$ and $q$ are odd, then $\phi(p^a)$ and $\phi(p^b)$ both divide $\phi(n)/2$; so does $\phi(r)$, so the group is of exponent $\phi(n)/2$.

If $p=2$ and $a=1$, then $r$ is odd and greater than $1$, so both $(q-1)q^{b-1}$ and $\phi(r)$ are divisors of $\phi(n)/2$. If $p=2$ and $a\gt 1$, then $2^{a-1}$ divides $\phi(n)$, and $\phi(q)$ and $\phi(r)$ are both divisors of $\phi(n)/2$, and the exponent of $(\mathbb{Z}/2^{a}\mathbb{Z})^{\times}$ is $2^{a-2}$, which is also a divisor of $\phi(n)/2$. So $(\mathbb{Z}/n\mathbb{Z})^{\times}$ is of exponent $\phi(n)/2$.

share|cite|improve this answer
I don't see how you always conclude so quickly what the exponent is. E.g. in your last step, why does it follow the exponent of $(\mathbb Z / n \mathbb Z)^\times$ is $\varphi(n)/2$? I think $$ \exp (\mathbb Z / n \mathbb Z)^\times = \mbox{gcm}( \exp(\mathbb Z / 2^a \mathbb Z)^\times , \exp (\mathbb Z / q^b \mathbb Z)^\times, \exp(\mathbb Z / r \mathbb Z)^\times).$$ – Glenn Jun 12 '12 at 15:20
@Glenn: I think you mean "lcm" (least common multiple), not "gcm". The reason is that $(\mathbb{Z}/n\mathbb{Z})^{\times}$ consists of at least two nontrivial factors, each of which has order divisible by $2$. So $\phi(n)=xyz$ with $x$ and $y$ even; that means that $x$ divides $\frac{xyz}{2}$ and so does $y$. – Arturo Magidin Jun 12 '12 at 16:14

Hint $\rm\ \ (m,n)=1\:\Rightarrow\phi(mn) = \phi(m)\phi(n),\:$ with both factors even for $\rm\:m,n > 2,\:$ hence

$$\rm (a,mn)= 1\:\Rightarrow\:\begin{eqnarray}\rm\: a^{\phi(m)} &\equiv&\rm 1\:\ (mod\ m) \\ \rm a^{\phi(n)} &\equiv&\rm 1\:\ (mod\ n)\end{eqnarray} \:\Rightarrow\:a^{\phi(mn)/2}\equiv a^{\phi(m)\phi(n)/2}\equiv 1\:\ (mod\ mn)$$

by CRT and $\rm\: mod\ m\!:\ (a^{\phi(m)})^{\phi(n)/2} \equiv 1^{\phi(n)/2}\equiv 1,\:$ by $\rm\:2\:|\:\phi(n).\:$ Ditto $\rm\:mod\ n,\:$ by symmetry.

The essence is simply this: $\rm\: 2\:|\:M,N\:\Rightarrow\: lcm(M,N)\:|\:MN/2\ $ since

$$\rm 2\:|\:gcd(M,N)\:\Rightarrow\:2\,lcm(M,N)\:|\:gcd(M,N)lcm(M,N) = MN$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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