$a^{\frac{\varphi (n)}{2}} \equiv 1 \pmod n\,$ if $\,(a,n)=1$ and $\Bbb Z_n$ is non-cyclic (no primitive root) $a^{\frac{\varphi (n)}{2}} \equiv 1 \pmod n\,$ if $\,(a,n)=1$ and $\Bbb Z_n$ is non-cyclic (no primitive root)
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.)
 A: 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 $\,\rm d\!=\!2\,$ in $\rm\: d\:|\:M,N\:\Rightarrow\: lcm(M,N)\:|\:MN/d\ $ since
$$\rm d\:|\:gcd(M,N)\:\Rightarrow\:d\,lcm(M,N)\:|\:gcd(M,N)lcm(M,N) = MN$$
A: 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$.
