Prove for non prime $n$ there exists $m \in \mathbb{Z}/n\mathbb{Z} \setminus \{0\}: m^{n-1} \neq 1 \mod n$

Question

How would I go about proving:

For every non-prime $n \in \mathbb N$ there exists $m \in \mathbb Z / n\mathbb Z \setminus \{0\}$ with $m^{n-1} \not\equiv 1 \mod n$.

I already proved the other way around (straight forward using Euler-Fermat), but am stuck at this point.

Answer 1

Pick $m$ a nontrivial divisor of $n$, and let $k:=n/m$. Suppose that $m^{n-1}\equiv 1(\mod n)$. Then $k\equiv k\cdot 1\equiv km^{n-1}\equiv nm^{n-2}\equiv 0(\mod n)$, contradiction, since $0<k<n$.

Answer 2

I think it makes sense that we need to use the fact that $n$ is composite somehow. So what is the one thing we know about composite numbers: they have nontrivial diviors! So choose $m$ to be a divisor of $n$ different from $1$. Now is it possible for $ma\equiv 1\pmod n$ for any $a\in\Bbb Z/n\Bbb Z$?