Pseudoprime Numbers

A composite number $ n $ (i.e., not a prime) is called a pseudoprime to base $ a $ if it satisfies the following condition: $$ a^{n-1} \equiv 1 \pmod{n} $$ where $ a $ is an integer that is relatively prime to $ n $, meaning that $ \text{GCD}(a, n) = 1 $.

In other words, pseudoprimes are numbers that "pretend" to be prime based on Fermat’s theorem—but they actually aren’t.

For this reason, they are also known as Fermat pseudoprimes.

According to Fermat’s Little Theorem, a number is likely to be prime if:

$$ a^n \equiv a \pmod n $$

However, if the base $ a $ is relatively prime to $ n $ (i.e., they share no common divisors other than 1), then $ n $ is composite, not prime.

In this case, we can divide both sides of the equation by $ a $:

$$ \frac{a^n}{a} = a^{n-1} $$

$$ \frac{a}{a} = 1 $$

which simplifies to:

$$ a^{n-1} \equiv 1 \pmod n $$

For prime numbers, this condition holds for all bases $ a $.

A pseudoprime, however, is a composite number that happens to satisfy this condition for certain values of $ a $.

Note: A number can be pseudoprime only for specific bases. For example, $ n = 341 $ is a composite number ($ 341 = 11 \times 31 $) and is pseudoprime to base 2 but not to base 3.

Most pseudoprimes are odd. Even pseudoprimes (such as 4) do exist, but they are rare.

A Practical Example
Additional Notes

A Practical Example

Consider the composite number:

$$ n = 91 $$

It can be factored as $ n = 91 = 7 \times 13 $, meaning it’s not prime.

However, $ n = 91 $ satisfies Fermat’s theorem:

$$ a^{n-1} \equiv 1 \pmod{n} $$

$$ a^{91-1} \equiv 1 \pmod{91} $$

$$ a^{90} \equiv 1 \pmod{91} $$

Now, let’s test base $ a = 3 $:

$$ 3^{90} \equiv 1 \pmod{91} $$

To verify this, we compute:

$$ 3^{90} \mod 91 $$

Using modular exponentiation:

$$ 3^1 \mod 91 = 3 $$

$$ 3^2 \mod 91 = 9 $$

$$ 3^4 \mod 91 = 81 $$

$$ 3^8 \mod 91 = (3^4 \times 3^4) \mod 91 = (81 \times 81) \mod 91 = 9 $$

$$ 3^{16} \mod 91 = (3^8 \times 3^8) \mod 91 = (9 \times 9) \mod 91 = 81 $$

$$ 3^{32} \mod 91 = (3^{16} \times 3^{16}) \mod 91 = (81 \times 81) \mod 91 = 9 $$

$$ 3^{64} \mod 91 = (3^{32} \times 3^{32}) \mod 91 = (9 \times 9) \mod 91 = 81 $$

Since $ 3^{90} = 3^{64} \times 3^{16} \times 3^8 \times 3^2 $, we compute:

$$ 3^{90} \mod 91 = (3^{64} \times 3^{16} \times 3^8 \times 3^2) \mod 91 $$

$$ 3^{90} \mod 91 = (81 \times 81 \times 9 \times 9) \mod 91 $$

Since $ 81 \times 9 \mod 91 = 1 $, we get:

$$ 3^{90} \mod 91 = (1 \times 1) \mod 91 $$

$$ 3^{90} \mod 91 = 1 \mod 91 = 1 $$

Thus, the equivalence holds:

$$ 3^{90} \equiv 1 \pmod{91} $$

So, the composite number $ n = 91 $ is pseudoprime to base $ a = 3 $.

Note: The same number $ n = 91 $ may not be pseudoprime for other bases. For example, $ n = 91 $ is not pseudoprime to base $ a = 2 $:

$$ 2^{90} \not\equiv 1 \pmod{91} $$

Additional Notes

Some further insights into pseudoprime numbers:

Multiplicative Properties of Pseudoprimes
If $ n $ is an odd composite number that is pseudoprime to two bases $ b_1 $ and $ b_2 $, then it is also pseudoprime to their product $ b_1 b_2 $, as well as to $ b_1 b_2^{-1} $, where $ b_2^{-1} $ is the modular inverse of $ b_2 $ modulo $ n $.
Note: This property highlights the multiplicative structure of pseudoprimes, allowing new pseudoprimes to be derived from known ones.
Non-Pseudoprimality in Composite Numbers
Given an odd composite number $ n > 1 $ and an integer $ a $ such that $ 1 < a < n $ and $ \gcd(n, a) = 1 $ (meaning $ a $ is coprime to $ n $), if $ n $ is not a pseudoprime in base $ a $, then it will also fail to be a pseudoprime for at least half of the integers $ b $ where $ 1 < b < n $ and $ \gcd(n, b) = 1 $ (i.e., $ b $ is also coprime to $ n $).
Note. This property underscores the fact that if a composite number $ n $ does not satisfy the pseudoprimality condition for some coprime base $ a $, it is likely to fail for at least half of all other coprime bases as well.
Multiplicative Property of Bases in Euler Pseudoprimes
If an odd composite number is an Euler pseudoprime for two bases $ b_1 $ and $ b_2 $, then it remains an Euler pseudoprime for both their product, $ b_1 b_2 $, and for $ b_1 $ multiplied by the modular inverse of $ b_2 $ modulo $ n $.

And so on.