If $m=xy$ with coprime $x,y>2$, then $2| \varphi(x), \varphi(y)$, giving: \[a^\frac{\varphi(m)}{2}= a^{\varphi(x) \cdot \frac{\varphi(y)}{2}}\equiv 1^\frac{\varphi(y)}{2}=1 \mod x\] and \[a^\frac{\varphi(m)}{2}= a^{\varphi(y) \cdot \frac{\varphi(x)}{2}}\equiv 1^\frac{\varphi(x)}{2}=1 \mod y.\] After handling the easy case $m=2^{k}\geq 8$, this now gives our result because for all other $m$, there are primitive roots.

ZetaX wrote: After handling the easy case $ m = 2^{k}\geq 8$, this now gives our result because for all other $ m$, there are primitive roots. Is this something you can prove here or just a fact that you know?

It's near to trivial (and well known): As there is no primitive root, we have $ k \geq 3$. Trivial checking gives that $ a^2 \equiv 1 \mod 8$ and inductively we have $ a^{2^{r-2}} \equiv 1 \mod 2^r$ implying (by $ a^{2^{r-2}} =1+2^r b$) that $ a^{2^{r-1}} = (1+2^r b)^2 = 1+ 2^{r+1} b + 2^{2r} b \equiv 1 \mod 2^{r+1}$.

how do u have a=1+(2^r)b? for r = 3, that means a is 1 or 9 mod 16 (if we prove the r+1 case), but that missed the other residues in 16

There is simply a missing exponent.

we prove for any prime factor of $n$ that $||m||_p=k$ that $a^{ \frac{\varphi(m)}{2}}\equiv 1 \; \pmod{p^k}$ first of all it's easy to see that $\varphi(\frac{m}{p^k})$ is even because $\frac{m}{p^k} >2$ now let $x=\frac{\varphi(m)}{2} =\frac{\varphi(\frac{m}{p^k}) \times (p-1)p^{k-1}}{2} =\frac{\varphi(\frac{m}{p^k})}{2} \times (p-1)p^{k-1} \implies \varphi(p^k) \mid x \implies a^x \equiv 1 \mod p^k$ because $p$ was an arbitrary prime factor then $a^x \equiv 1 \mod m$