For the Fermat test it is stated that $a^{n-1} \equiv 1 \pmod n$ implies that $\gcd(a, n) = 1$ even when $n$ is not prime (the case for prime $n$ is obvious). I want to know why is this true.
If I can prove the above statement then it will prove this statement as follows.
Assume : If $d$ divides $n$ then $d^{n-1} \not\equiv 1 \pmod n$.
Let $\gcd(a, n) = d,\ a = cd,$ and so $\gcd(c, n) = 1$.
$a^{n - 1} \pmod n \equiv d^{n - 1} \pmod n \times c^{n - 1} \pmod n$
$c^{n - 1} \pmod n \equiv 1 \pmod n\ \ \ \ $ (I am not sure about this step when $n$ is not prime)
Thus, $a^{n - 1} \pmod n \equiv d^{n - 1} \pmod n$.
If $\gcd(a,n)\ne 1$, then there is a prime $p$ with $p|a$ and $p|n$. $a^{n-1}\equiv 1\mod n$ means $n|a^{n-1}-1$ and because of $p|n$ this implies $p|a^{n-1}-1$.
But we also have $p|a^{n-1}$ because of $p|a$. This is a contradiction because a prime can never divide two consecutive integers simultaneously.