Fermat's Little Theorem

Fermat's Little Theorem states, if \(p\) is a prime number and \(a\) is an integer, \(a^p\equiv a\) (mod \(p\)). The theorem itself is used and is very helpful when testing numbers to see if they are not prime. It can be easy to see whether a small number is not prime however, with big numbers it can be difficult. One of the most important things to note is that the theorem does not tell whether a number is prime but it does show if a number is not prime. Therefore, the famous theorem also states that if \(p\) does not divide \(a\), then \(a^{p-1}\equiv\) \(1\) (mod \(p\)). 

Although this is known as Fermat's Theorem, surprisingly this was not proven by Fermat. Fermat decided not to prove it because the amount of pages and work it would take to complete it. Euler was the first mathematician to have a proof published in 1749. A picture of the proof is shown below. 
We can now look at an example, let's say \(a=3\) and \(p=7\), using Fermat's Theorem we should get that \(3^{7-1}\equiv1\) (mod \(7\)) which then simplifies to \(3^6\equiv1\) (mod \(7\)). When computing this we will end up with \(\frac{729}{7}\), which does come out to have a remainder of \(1\). This theorem does show to be true for all prime numbers however, it is not only true for prime numbers. There are special cases where the theorem works for a number that is not prime, if the non-prime number happens to satisfy the theorem then the number is known as a pseudoprime. Let's see an example: if we have \(4^{14}\equiv1\) (mod \(15\)), we can see that the number \(15\) is not prime because it is divisible by \(3\) and \(5\), next we want to see if the statement is true. Let's write \(4^{14}\) as \(\left(4^2\right)^7\) \(\equiv1\) (mod \(15\)). We can see that we will have \(16\) (mod \(15\)), giving us a remainder of \(1\) therefore, we can raise \(1^7\) and get that the remainder is \(1\) making our statement true, the number \(15\) is in fact a pseudoprime because it satisfies Fermat's theorem without being a prime number.