Proving the Converse of Euler's Totient Theorem Euler's Totient Theorem states that if $n$ and $a$ are coprime positive integers, then $$a^{\varphi (n)} \equiv 1 \pmod{n}$$ Wikipedia claims that the converse of Euler's theorem is also true: if the above congruence is true, then $a$ and $n$ must be coprime. But is there any proof of this?

Suppose that for some $B$, $a^B=1 \mod n$. Then we have some integers $k,m$ and an equation of the form $a^Bk+mn=1$. This means that $a^B$ and $n$ are coprime. Then $a$ and $n$ must be coprime.