Let $n \ge 2$ and $\gcd (a, n) = 1$. Disprove the following:
If $a^{\frac{\phi(n)}{2}} \not \equiv 1 \pmod n$ then the order of $a \pmod n$ is $\phi(n)$.
We'll disprove the statement with a counter-example.
Let's set $a=6, n=7$. We the confirm that
- $n = 7 \ge 2$
- $\gcd(a,n)=\gcd(6.7)=1$
- $a^{\frac{\phi(n)}{2}} \equiv 6^{\frac{6}{2}} \equiv 6 \not \equiv 1 \pmod n$
We note the order of $6 \pmod 7$ is 2, which is not $\phi(n)=\phi(7)=6$.
This counter-example disproves the given statement.