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?
On
Assume throughout that $(a, n) \not = 1$.
Lemma: the map $\mathbb{Z}_n \to \mathbb{Z}_n$ by $m \mapsto a m \pmod{n}$ sends some nonzero number to zero.
Indeed, $ax + ny = 1$ has no solutions in $x, y$, by reducing both sides mod $(a, n)$. Therefore since the map is not surjective and is a map from a finite set to itself, it must not be injective either; say $a m_1 = a m_2$ but $m_1 \not = m_2$. Then $a (m_1 - m_2) = 0$.
Theorem: $a^{\phi(n)} \not \equiv 1 \pmod{n}$.
Proof: Define the set $I = \{ i: 1 \leq i < n, (i, n) = 1 \}$. Let its product (the product of all its members) be $X$. Then $aI = \{ ai : i \in I \}$ has product $a^{\phi(n)} X$; that must be zero, because by the lemma, some $ai = 0$.
But $(X, n) = 1$, because a product of things coprime to $n$ cannot share a factor with $n$. Therefore $a^{\phi(n)}$ cannot also be 1, because that would make $0 = a^{\phi(n)} X = 1 \times X = X$ where $X$ is nonzero.
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.