2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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).$$ $\endgroup$ – Glenn Jun 12 '12 at 15:20
  • $\begingroup$ @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$. $\endgroup$ – Arturo Magidin Jun 12 '12 at 16:14
1
$\begingroup$

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

$\endgroup$

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.