The small theorem of Fermat.

     For any prime number p and a, co-prime with it, the number a ^p-1-1 is divisible by p.

     Proof. Let's consider numbers a, 2a, ... , (p-1)a. Let's notice, that all of them give different remainders when devided into p. Really, if, for example, ma and na, where 0 < n < m < p, give equal remainders when devided into p, then ma-na = (m-n)a, must be divisible by p. However, this is impossible, as a isn't divisible by p according to the condition (a and p are co-prime), and difference m-n is less than p. Consequently, these numbers give all possible non-zero remainders when divided into p. Therefore, their product a ^p-1 (p-1)! gives the same remainder when divided into p, as (p-1)!, that is, the difference

a ^p-1 (p-1)! - (p-1)! = (p-1)! (a ^p-1-1)

is divisible by p, as it's obvious that (p-1)! is co-prime with p, from this follows, that a ^p-1-1 is divisible by p, what was to be proved.