Soon we will get Codeforces 4-digit contest 1000, as the educational round 45.

http://mirror.codeforces.com/contests/1000

Isn't it amazing. <3

We know that if n is prime, then:

{a^(n-1)} mod n = 1 [Fermat primality test]

Can anyone explain its mathematical proof?