Let $n \ge 2$ and $\gcd (a, n) = 1$. Prove the following:
If $a^k \not \equiv 1 \pmod n$ for $1 \le k \le \frac{\phi (n)}{2}$ then the order of $a \pmod n$ is $\phi (n)$.
The order $k$ exists because $\gcd(a,n)=1$, and is a factor of $\phi(n)$. That is, for some positive integer $j$, we have
$$ k = \frac{\phi(n)}{j} $$
Let's consider two cases for $j$, namely $j \ge 2$ and $j=1$.
For $j \ge 2$ we have $k \le \frac{\phi(n)}{2}$, which we're given means $a^k \not \equiv 1 \pmod n$.
For the case $j=1$ we have $k=\phi(n)$. By Euler's Theorem this means $a^k \equiv 1 \pmod n$.
Because $\phi(n)$ is the least positive $k$ such that $a^k \equiv 1 \pmod n$, we conclude the order of $a \pmod n$ is $\phi (n)$.