Why must the $gcd((N-1)!,N)=1$ in order to factor out $(N-1)!$ from both sides of $a^{N-1}(N-1)! \equiv (N-1)! \pmod N $?

Question

I'm trying to gain the intuition of why must the $gcd((N-1)!,N)=1$ in order to factor out $(N-1)!$ from $a^{N-1}(N-1)! \equiv (N-1)! \pmod N $?

Answer 1

Consider what the congruence means; it means precisely that $N$ divides $$a^{N-1}(N-1)!-(N-1)!=(N-1)!(a^{N-1}-1).$$ You want to factor out $(N-1)!$, i.e. to conclude that $N$ divides $a^{N-1}-1$. Do you see what the problem is if $\gcd((N-1)!,N)\neq1$?