Its converse is Lehmer's theorem, and when a positive integer satisfies it for all choice of bases, that integer is called a Carmichael number.  
One way to prove it is to use the invertibility of the natural number group up to its order ensured by Bezout's identity, and apply Lagrange's theorem.  Another proof of it uses induction on the binomial theorem, and one of its corollaries can be stated in terms of a 2k factorial term in relation to minus one.  One of its consequences is Hannam's lemma, and a generalization of it using the totient function is known as Euler's theorem.  Its converse is Lehmer's theorem, and when a positive integer satisfies it for all choice of bases, that integer is called a Carmichael number.  Directly implying Wilson's theorem, FTP name this theorem originally stated without proof, which states that a to the p mod p equals a mod p, for prime p, the result of a French mathematician also known for his "last" theorem.
One way to prove it is to use the invertibility of the natural number group up to its order ensured by Bezout's identity, and apply Lagrange's theorem.  
{Fermat}'s {little} theorem