The Fermat test is based on a result from number theory known as Fermat’s little theorem.

According to Fermat’s little theorem, if n is a prime number and d is any positive integer less than n, then d raised to the nth power is congruent to d modulo n.

If two numbers have the same remainder when divided by n then they are said to be congruent modulo n. d modulo n is simply the remainder of a number d when divided by n.

For example, 34 is congruent to 16 (modulo 3) as
34 modulo 3 = 1 and 16 modulo 3 = 1.

#### Fermat test for primality

1. For a given number n, pick a random positive number d such that d <; n.
2. Calculate (d^n) modulo n.
3. d modulo n is always going to be d as we always pick d that satisfies the condition d <; n.
4. If the result of (d^n) modulo n is not equal to d, then d is certainly not prime.
5. If the result of (d^n) modulo n is equal to d, then the chances are good that n is prime.
6. Pick another random d that satisfies the condition d < n and repeat the above steps.

Note: The examples in this post use Swift 4.1

We need a function to calculate the exponential of a number modulo another number.