Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

Prime Test

Revision en2, by MRITuhin, 2018-02-27 12:37:03

We know that if n is prime, then:

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

Can anyone explain its mathematical proof?

Tags #math, #number theory, #primes

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English MRITuhin 2018-02-27 12:37:03 8 Tiny change: 'n{a^(n-1)}%n=1\n[Fermat' -> 'n{a^(n-1)} mod n = 1\n[Fermat'
en1 English MRITuhin 2018-02-26 09:31:04 131 Initial revision (published)