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