Non-Pseudoprimality in Composite Numbers
Let \( n > 1 \) be an odd composite number, and consider the numbers coprime to \( n \) in the range \( 1 < a < n \), where $$ \gcd(n, a) = 1 $$ If \( n \) is not a pseudoprime to a given integer \( a \), then it fails to be a pseudoprime for at least half of the numbers in that range that are also coprime to \( n \).
In other words, if a composite number \( n \) does not behave like a pseudoprime for some base \( a \) that is coprime to \( n \), then it will also fail to do so for at least half of the other bases \( b \) in the interval \( 1 < b < n \) that are coprime to \( n \).
This puts a significant limitation on the use of pseudoprimes in primality testing—i.e., in identifying prime numbers—since there is no guarantee that \( n \) will exhibit pseudoprime behavior in most bases.
Note. This is why more advanced primality tests, such as the Miller-Rabin or the Baillie-PSW test, use multiple bases to minimize false positives.
A Practical Example
Consider \( n = 91 \), an odd composite number. Indeed, \( 91 = 7 \cdot 13 \).
The divisors of \( 91 \) are \( 1, 7, 13, 91 \). Therefore, the numbers coprime to \( 91 \) are those that are not multiples of \( 7 \) or \( 13 \).
Using Euler’s totient function, we find that there are 72 numbers coprime to 91 in the range from 1 to 91:
$$ \phi(91) = 91 \cdot \left(1 - \frac{1}{7}\right) \cdot \left(1 - \frac{1}{13}\right) = 91 \cdot \frac{6}{7} \cdot \frac{12}{13} = 72 $$
So, there are 72 potential bases \( a \) to test with Fermat’s theorem to determine whether 91 behaves as a pseudoprime.
$$ \gcd(n, a) = 1 $$
The full list of numbers coprime to 91 is:
1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 27, 29, 30, 31, 32, 33, 34, 36, 37, 38, 40, 41, 43, 44, 45, 46, 47, 48, 50, 51, 53, 54, 55, 57, 58, 59, 60, 61, 62, 64, 66, 67, 68, 69, 71, 72, 73, 74, 75, 76, 79, 80, 81, 82, 83, 85, 86, 87, 88, 89, 90
Now, let’s check one particular base, say \( a = 2 \), using Fermat’s Little Theorem:
$$ a^{n-1} \not\equiv 1 \pmod{n} $$
$$ 2^{90} \not\equiv 1 \pmod{91} $$
This confirms that \( n = 91 \) is not a pseudoprime in base \( a = 2 \).
Since \( n = 91 \) fails the pseudoprime condition for \( a = 2 \), it must also fail in at least half of the bases \( 1 < a < 91 \) that are coprime to \( 91 \).
Given that there are \( \phi(91) = 72 \) bases coprime to \( 91 \), at least \( 36 \) of them will not recognize \( 91 \) as a pseudoprime.
| base | Fermat's Theorem | Pseudoprime base for 91 |
|---|---|---|
| \( a = 2 \) | \( 2^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 3 \) | \( 3^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 4 \) | \( 4^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 5 \) | \( 5^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 6 \) | \( 6^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 8 \) | \( 8^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 9 \) | \( 9^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 10 \) | \( 10^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 11 \) | \( 11^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 12 \) | \( 12^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 15 \) | \( 15^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 16 \) | \( 16^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 17 \) | \( 17^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 18 \) | \( 18^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 19 \) | \( 19^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 20 \) | \( 20^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 22 \) | \( 22^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 23 \) | \( 23^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 24 \) | \( 24^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 25 \) | \( 25^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 27 \) | \( 27^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 29 \) | \( 29^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 30 \) | \( 30^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 31 \) | \( 31^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 32 \) | \( 32^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 33 \) | \( 33^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 34 \) | \( 34^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 36 \) | \( 36^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 37 \) | \( 37^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 38 \) | \( 38^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 40 \) | \( 40^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 41 \) | \( 41^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 43 \) | \( 43^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 44 \) | \( 44^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 45 \) | \( 45^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 46 \) | \( 46^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 47 \) | \( 47^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 48 \) | \( 48^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 50 \) | \( 50^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 51 \) | \( 51^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 53 \) | \( 53^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 54 \) | \( 54^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 55 \) | \( 55^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 57 \) | \( 57^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 58 \) | \( 58^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 59 \) | \( 59^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 60 \) | \( 60^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 61 \) | \( 61^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 62 \) | \( 62^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 64 \) | \( 64^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 66 \) | \( 66^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 67 \) | \( 67^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 68 \) | \( 68^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 69 \) | \( 69^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 71 \) | \( 71^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 72 \) | \( 72^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 73 \) | \( 73^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 74 \) | \( 74^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 75 \) | \( 75^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 76 \) | \( 76^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 79 \) | \( 79^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 80 \) | \( 80^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 81 \) | \( 81^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 82 \) | \( 82^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 83 \) | \( 83^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 85 \) | \( 85^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 86 \) | \( 86^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 87 \) | \( 87^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 88 \) | \( 88^{90} \equiv 1 \pmod{91} \) | ✅ yes |
| \( a = 89 \) | \( 89^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 90 \) | \( 90^{90} \equiv 1 \pmod{91} \) | ✅ yes |
This example illustrates that not all bases coprime to \( 91 \) make \( 91 \) a pseudoprime.
In fact, at least half of the bases coprime to \( 91 \) fail to satisfy the pseudoprimality condition.
The Proof
Consider the multiplicative group \( \mathbb{U}(\mathbb{Z}_n) \), which consists of all integers \( b \) in the range \( 1 \leq b < n \) that are coprime to \( n \).
\[ \mathbb{U}(\mathbb{Z}_n) = \{ b \in \mathbb{Z}_n \mid \gcd(b, n) = 1 \} \]
The size of \( \mathbb{U}(\mathbb{Z}_n) \) is given by Euler’s totient function \( \phi(n) \).
Now, let \( P \) be the subset of \( \mathbb{U}(\mathbb{Z}_n) \) containing all bases \( b \) for which \( n \) behaves as a pseudoprime:
\[ P = \{ b \in \mathbb{U}(\mathbb{Z}_n) \mid n \text{ is a pseudoprime in base } b \} \]
Our goal is to prove that if \( n \) is not a pseudoprime in base \( a \), then at least half of the elements in \( \mathbb{U}(\mathbb{Z}_n) \) do not belong to \( P \).
Note. A number \( n \) is a pseudoprime in base \( b \) if it satisfies: $$ b^{n-1} \equiv 1 \pmod{n} $$ If \( n \) is not a pseudoprime for some \( a \in \mathbb{U}(\mathbb{Z}_n) \), then: $$ a^{n-1} \not\equiv 1 \pmod{n} $$
Now, take an element \( a \in \mathbb{U}(\mathbb{Z}_n) \) such that \( a^{n-1} \not\equiv 1 \pmod{n} \), meaning \( a \notin P \).
Next, define a function that maps any \( b \in P \) to the product \( ab \mod n \):
$$ f : b \in P \mapsto ab \in \mathbb{U}(\mathbb{Z}_n) $$
Since \( a \) is invertible modulo \( n \), this function is a permutation of \( \mathbb{U}(\mathbb{Z}_n) \).
If \( b \in P \), then by definition, \( b^{n-1} \equiv 1 \pmod{n} \).
To check whether \( ab \in P \), consider:
$$ (ab)^{n-1} = a^{n-1} b^{n-1} $$
Since \( b \in P \), we know that \( b^{n-1} \equiv 1 \pmod{n} \), so:
$$ (ab)^{n-1} \equiv a^{n-1} \pmod{n} $$
By assumption, \( a^{n-1} \not\equiv 1 \pmod{n} \), which means \( ab \notin P \).
This shows that the function \( f \) maps each \( b \in P \) to an element \( ab \notin P \).
Since \( f \) takes every element of \( P \) and moves it outside \( P \), the number of elements in \( P \) can be at most half of those in \( \mathbb{U}(\mathbb{Z}_n) \):
$$ |P| \leq \frac{\phi(n)}{2} $$
Note. The function \( f(b) = ab \) ensures that no element of \( P \) is mapped to another element in \( P \). Since \( f \) is a permutation of the entire group \( \mathbb{U}(\mathbb{Z}_n) \), it follows that at least half of the elements must be outside \( P \). Thus, if \( \mathbb{U}(\mathbb{Z}_n) \) has \( \phi(n) \) elements, then \( |P| \leq \frac{\phi(n)}{2} \).
In conclusion, at least half of the elements in \( \mathbb{U}(\mathbb{Z}_n) \) do not belong to \( P \).
In other words, there are at least \( \frac{\phi(n)}{2} \) integers \( b \) for which \( n \) is not a pseudoprime in base \( b \). This completes the proof.
