Question

Show that 12 is no pseudoprime because it fails some Fermat test.

Short answer

The above problem can be solved using the Fermat’s Little Theorem which says that if n is a prime number, then for every ‘a’ , $1<a<n-1$, i.e. $a^{n-1}=1\left(Modn\right)$.

Step-by-step solution

Defining the Fermat’s Theorem

According to Fermat’s Little Theorem,

If n is a prime number, then for every $\mathbf{a}\mathbf{,}\mathbf{1}\mathbf{<}\mathbf{a}\mathbf{<}\mathbf{n}\mathbf{-}\mathbf{1}$,

$a^{n-1}=1\left(Modn\right)$

or

$a^{n-1} \% n=1$.

Checking the number with the condition

Let us consider 12 as a prime number and check for Fermat’s Theorem.

Hence According to the Condition,

$$\begin{gathered} 2^{11} \% 12\ne 1 \\ {3}^{11} \% 12\ne 1 \\ {4}^{11} \% 12\ne 1 \\ \dots \dots \dots \dots \dots \dots \dots \\ \dots \dots \dots \dots \dots \dots \dots \\ {11}^{11} \% 12\ne 1 \end{gathered}$$

The number 12 does not satisfy the condition of Fermat’s Little theorem i.e.

$a^{n-1}=1\left(Modn\right)$

Since the number 12 fails Fermat’s test it is not a pseudoprime.

Pseudoprime is a probable-prime i.e., not actually prime but which is composite.