We begin by discussing a method of computing $a^d\mod n$, called the repeated squaring method, which is efficient enough to require only a handheld calculator using the following example.

Example. Let us compute the least residue of $848^{187}\mod 1189$ by using only a handheld calculator. First we convert 187 to the base 2:
\begin{align*} 187&=(10111011)_2\\ &=1\cdot 2^7+0\cdot 2^6+1\cdot 2^5+1\cdot 2^4+1\cdot 2^3+0\cdot 2^2+1\cdot 2+1\\ &=128+32+16+8+2+1 \end{align*}
Let $a=848$ and $n=1189$.
$$\begin{array}{|c|c|}
\hline
k & a^k\mod n\\
\hline
1 & 848\\
\hline
2 & 848^2=719104\equiv 948\mod 1189\\
\hline
4 & 948^2=898704\equiv 1009\mod 1189\\
\hline
8 & 1009^2= 1018081\equiv 297\mod 1189\\
\hline
16 & 297^2=88209\equiv 223\mod 1189\\
\hline
32 & 223^2=49729\equiv 980\mod 1189\\
\hline
64 & 980^2=960400\equiv 877\mod 1189\\
\hline
128 & 877^2=769129\equiv 1035\mod 1189\\
\hline
\end{array}$$
Hence,
\begin{align*} 848^{187}&=848^{128+32+16+8+2+1}\\ &=848^{128}\cdot 848^{32}\cdot 848^{16}\cdot 848^8\cdot 848^2\cdot 848\\ &\equiv 1035\cdot 980\cdot 223\cdot 297\cdot 948\cdot 848\mod 1189\\ &\equiv 190\mod 1189 \end{align*}

Here is our first primality test. Let us recall Fermat Little Theorem: If $n$ is a prime and $n\not|a$, then $a^{n-1}\equiv 1\mod n$. The contrapositive of the above statement can serve as a primality test: if $a^{n-1}\not\equiv 1\mod n$, then $n$ is not a prime or $n|a$.

Example. Let us show that $33$ is not a prime using the above primality test. (Of course it is not prime because $33=3\cdot 11$.) $33\not|2$ and
\begin{align*} 2^{33-1}&=2^{32}\\ &=(2^5)^62^2\\ &=(32)^62^2\\ &\equiv(-1)^62^2\mod 33\\ &\equiv 4\mod 33 \end{align*}
Thus, $33$ is not a prime.

Here is another primality test.

Theorem. If the integer $n>1$ has no prime divisor less than or equal to $\sqrt{n}$, then $n$ is prime.

Proof. Suppose that $n$ is a composite number. Then $n=d_1d_2$ for some $d_1>1$ and $d_2>1$. Suppose that all prime divisors are greater than $\sqrt{n}$. Then $d_1>\sqrt{n}$ and $d_2>\sqrt{n}$. But $n=d_1d_2>(\sqrt{n})^2=n$, which is impossible. This proves the theorem. If $d_1\leq\sqrt{n}$, then $d_1$ is either prime or else has a prime divisor less than or equal to $\sqrt{n}$.

Question: Is the statement “If $2^{n-1}\equiv 1\mod n$ then $n$ is a prime.” true? The ancient Chinese believed so, but there is a counterexample. $2^{340}\equiv 1\mod 341$. But, $341=11\cdot 31$ (this is left as an exercise), so it is not a prime.

Definition. We call $n$ a pseudoprime if $2^{n-1}\equiv 1\mod n$ but $n$ is composite. More generally, a composite number $n$ such that $a^{n-1}\equiv 1\mod n$ is called a pseudoprime to base $a$.

The smallest pseudoprime is $341$, and it was not discovered until 1819. Bases other than $2$ can be used to identify composite numbers. For example,
$$3^{340}\equiv 56\mod 341$$
Thus, $341$ is not a prime number. These pseudoprimes are rarer then primes. Ever rarer are pseudoprimes to multiples bases. It is known, for example, that there are only 1770 integers below $25\cdot 10^9$ that are simultaneously pseudoprimes to the bases $2$, $3$, $5$ and $7$. So, the primality of numbers less than $25\cdot 10^9$ can be determined by testing Fermat’s congruence $a^{n-1}\equiv 1\mod n$ with these four bases, then comparing any number passing all 4 tests with a list of the 1770 exceptions. If the number is not any of those 1770 exceptions, it must be a prime.

Next we discuss Mersenne numbers and Fermat numbers, and primality tests those numbers.

Definition. If $k$ is a positive integer, we call $M_k=2^k-1$ a Mersenne number.

$$\begin{array}{|c|c|c|}
\hline
k & M_k=2^k-1 & \mbox{prime?}\\
\hline
1 & 1 & \mbox{N}\\
\hline
2 & 3 & \mbox{Y}\\
\hline
3 & 7 & \mbox{Y}\\
\hline
4 & 15=3\cdot 5 & \mbox{N}\\
\hline
5 & 31 & \mbox{Y}\\
\hline
6 & 63=9\cdot 7 & \mbox{N}\\
\hline
7 & 127 & \mbox{Y}\\
\hline
8 & 255=3\cdot 5\cdot 7 & \mbox{N}\\
\hline
9 & 511=7\cdot 73 & \mbox{N}\\
\hline
10 & 1023=3\cdot 11\cdot 31 & \mbox{N}\\
\hline
\end{array}$$
From this table, one may expect that $M_k$ is prime when $k$ is prime. However, $M_{11}=2047=23\cdot 89$ is not a prime.

Theorem.
If $d|k$, then $M_d|M_k$, so if $M_k$ is prime, then $k$ is prime.

Proof. Since $d|k$, $k=dd_1$ for some $d_1\in\mathbb{Z}$.
$$M_k=2^k-1=2^{dd_1}-1=(2^d-1)(2^{(d(d_1-1)}+2^{(d(d_1-2)}+\cdots+2^d+1)$$

$$\begin{array}{|c|c|c|}
\hline
k & 2^k+1 & \mbox{prime?}\\
\hline
1 & 3 & \mbox{Y}\\
\hline
2 & 5 & \mbox{Y}\\
\hline
3 & 9=3\cdot 3 & \mbox{N}\\
\hline
4 & 17 & \mbox{Y}\\
\hline
5 & 33=3\cdot 11 & \mbox{N}\\
\hline
6 & 65=5\cdot 13 & \mbox{N}\\
\hline
7 & 129=3\cdot 43 & \mbox{N}\\
\hline
8 & 257 & \mbox{Y}\\
\hline
9 & 513=3\cdot 3\cdot 3\cdot 19 & \mbox{N}\\
\hline
10 & 1025=5\cdot 5\cdot 41 & \mbox{N}\\
\hline
\end{array}$$

Theorem. If $k$, $a$, and $b$ are positive integers such that $k=ab$, where $a$ is odd, then
$$2^b+1|2^k+1$$
In particular, if $2^k+1$ is prime, then $k$ is $0$ or a power of $2$.

Proof. Under the assumption, we want to show that
$$2^k+1\equiv 0\mod 2^b+1$$
or
$$2^k\equiv -1\mod 2^b+1$$
Since, $2^b\equiv -1\mod 2^b+1$,
$$2^k=2^{ab}=(2^b)^a\equiv (-1)^a\mod 2^b+1\equiv -1\mod 2^b+1$$
If $k>0$ is not a power of $2$, then we can take $a>1$ so that
$$1<2^b+1<2^k+1$$
This means that $2^k+1$ has a positive divisor other than 1 and itself.

Definition. $F_r=2^{2^r}+1$ is called a Fermat number.

Example. $F_0=3$, $F_1=5$, $F_2=17$, $F_3=257$, $F_4=65537$ are primes, so Fermat conjectured that Fermat numbers are prime. But $F_5=2^{32}+1$ is not a prime. It is divisible by $641$. $641$ can be written
\begin{align*} 641&=640+1=2^7\cdot 5+1\\ 641&=625+16=5^4+2^4 \end{align*}
Thus, we have $2^7\cdot 5\equiv -1\mod 641$ and $2^4\equiv -5^4\mod 641$.
Now,
\begin{align*} F_5&=2^{32}+1\\ &=(2^7)^4\cdot 2^4+1\\ &\equiv(2^7)^4(-5^4)+1\mod 641\\ &\equiv -(2^7\cdot 5)^4+1\mod 641\\ &\equiv 0\mod 641 \end{align*}
No other Fermat numbers that are prime have been found yet.

One may expect that for any composite number $n$, there exists a base $a$ for which Fermat’s theorem can be used to show that $n$ is composite. However, there are composite numbers called Carmichael numbers, which are pseudo primes to every base. That is, $n$ is composite, but $a^{n-1}\equiv 1\mod n$, whenever $(a,n)=1$. The smallest Carmichael number is $561=3\cdot 11\cdot 17$. It was proved in 1994 that there are infinitely many Carmichael numbers.

There is a primality test just for Mersenne numbers. It is called the Lucas-Lehmer test. Define a sequence $S_1,S_2,\cdots$ by
\begin{align*} S_1&=4,\\ S_n&=S_{n-1}-2\ \mbox{for}\ n>1. \end{align*}
For example, $S_2=4^2-2=14$, $S_3=14^2-2=194$. Then the Lucas-Lehmer test is

Theorem. If $p$ is an odd prime then $M_p=2^p-1$ is prime if and only if $S_{p-1}\equiv 0\mod M_p$.

For example, take $p=7$ and show that $M_p=2^7-1=127$ is a prime.
\begin{align*} S_3&=194\equiv 67\mod 127\\ S_4&\equiv 67^2-2\mod 127\equiv 42\mod 127\\ S_5&\equiv 42^2-2\mod 127\equiv 111\mod 127\\ S_6&\equiv 111^2-2\mod 127\equiv 0\mod 127. \end{align*}

There is also a primality test just for Fermat numbers. It is called Pépin’s test.

Theorem. If $n>0$, the Fermat number $F_n=2^{2^n}+1$ is prime if and only if $3^{\frac{F_n-1}{2}}\equiv -1\mod F_n$.

Example. Use Pépin’s test to show that $F_3=257$ is prime.

Solution. $3^{\frac{257-1}{2}}=3^{128}=3^{2^7}$.
\begin{align*} 3^2&=9\\ 3^4&=9^2=81\\ 3^8&=81^2\equiv 136\mod 257\\ 3^{16}&\equiv 136^2\mod 257\equiv 249\mod 257\\ 3^{32}&\equiv 249^2\mod 257\equiv 64\mod 257\\ 3^{64}&\equiv 64^2\mod 257\equiv 241\mod 257\\ 3^{128}&\equiv 241^2\mod 257\equiv 256\mod 257\equiv -1\mod 257 \end{align*}