Let $a_{1},a_{2},\ldots,a_{{\phi(n)}}$ be all positive integers less than $n$ which are coprime to $n$. Since $\text{gcd}(a,n)=1$, then the set $aa_{1},aa_{2},\ldots,aa_{{\phi(n)}}$ are each congruent to one of the integers $a_{1},a_{2},\ldots,a_{{\phi(n)}}$ in some order. Taking the product of these congruences, we get

hence

Since $\text{gcd}(a_{1}a_{2}\cdots a_{{\phi(n)}},n)=1$, we can divide both sides by $a_{1}a_{2}\cdots a_{{\phi(n)}}$, and the desired result follows.