Often known as Fermat's theorem, which runs the risk of confusing it with Wiles' theorem. This little fact from number theory was proved by Fermat.
Theorem. Let p be a prime number, and let a be any integer. Then ap = a (modulo p).
Like the similar
Wilson's theorem, the
proof of Fermat's little theorem is not too difficult, but a bit hard to grasp at first.
The proof originally on the linked node used algebra, and was very different from the proof below, which uses combinatorics. It's based on multiplying the fact that the integers modulo p are a (finite) field. Unfortunately there's an editorial decision to avoid proofs on separate nodes from their theorems. As I believe the proof doesn't belong here (it has nothing to do with how the theorem is applied, which is the usual motive for linking over here), I cannot paste it below. You should be able to reconstruct the proof from the description above; if desperate, /msg me and I'll answer privately.
As an example, take p=5 and a=4. Then 45 = 1024 is clearly 4 modulo 5 (it ends with a 4 or 9 digit).