# Question about non cyclic group of order $n$ with Euler function

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

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

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