Fermat's theorem

Question

In Fermat's little theorem $k^{p-1}$ is congruent to $1\pmod p$. Condition is that $p$ must be a prime number. Can anyone tell why it is so? What I have understood is that if $p$ is not a prime, then writing down all the integers between $1$ to $p-1$, there would be an integer which would be a factor of $p$, therefore we can't find the inverse.

Answer 1

Obviously you can't have $k^{n-1} \equiv 1 \mod n$ if $k$ and $n$ have a factor in common. On the other hand, there are numbers $n$ that are not primes, but $k^{n-1} \equiv 1 \mod n$ for all $k$ that have no common factor with $n$ (i.e. are relatively prime to $n$). These are called Carmichael numbers, and the smallest is $561$.