Fermat's Little Theorem

(Pierre de Fermat was born on 17th August 1601 in Montauban, France and he died on 12th January 1665 in Castres, France).
Fermat makes some other theorems which I am not going to discuss here, I just explain this theorem that has been used a lot to prove primality.

If P is prime then: B ^ P = B (mod P) <=> B ^ (P-1) = 1 (mod P)
B is a value defined in 1 < B < (P-1), and B is coprime with P (any value from 1 to P-1 are coprime with P).

All prime numbers will pass this test, but unfortunately some composite numbers can also pass this test. If a value failed this test then the value is certain to be composite, so this Fermat prime test is to check whether a given number is composite or not. If a number passed the test then a further test is required to check primality of the number.

Example (1): Number to test for primality: 7
2^7 = 2 (mod 7) => passed the test
3^7 = 3 (mod 7) => passed the test
4^7 = 4 (mod 7) => passed the test
5^7 = 5 (mod 7) => passed the test
So, seven (7) is a prime number because we have tested all possible B

Example (2): Number to test for primality: 9
4^9 = 1 (mod 9) => failed the test
5^9 = 8 (mod 9) => failed the test
6^9 = 0 (mod 9) => failed the test and since the result is ZERO (0) it means 6 and 9 has a common factor, GCD(6, 9) = 3.
So, nine (9) is NOT a prime number, any number that failed the test is a confirmation that P is not prime.

Other bigger values can't be tested many times with different values of B (1 < B < (P-1)) because it consumes too much time, so after several times and it still passed the test we just use other algorithm to determine the primality or just simply ASSUME it is a prime.