Congruence of a power of an integer modulo a relatively prime number

Question

I'm a complete noob in number theory, and I came across this (probably very elementary) statement: if for all $m\in \mathbb Z/n$ with $\gcd(m,n)=1$ there is some integer $k$ such that $$m^k\equiv 1\mod n,$$ then $k$ must be even. I ask for some help with the proof: I thought about writing explicitly $$m^{2k'+1}-1=nz, \quad z\in \mathbb Z $$ and tried to get a contradiction but I haven't so far managed.