A pseudoprime is a composite number that passes a prime test it was not supposed to pass. It looks prime to a limited test, but it still has nontrivial factors. This makes pseudoprimes useful for understanding the difference between a probable prime and a proven prime.
Definition
A pseudoprime is a composite whole number that satisfies a condition shared by primes under a particular primality test. The word does not mean “almost prime” in the factorization sense. It means the number fools a specific test.
What Makes a Number a Pseudoprime?
Prime tests often use patterns that every prime must satisfy. A composite number may sometimes satisfy the same pattern by coincidence. When that happens, the test gives a false prime-like result.
The term is always tied to the test being used. A number can be a pseudoprime for one test, but fail another test. That is why careful primality testing separates candidate numbers from numbers that have actually been proved prime.
Math Note
A pseudoprime is still composite. It has more than two positive divisors, even if a test based on modular arithmetic makes it appear prime.
Simple Examples of Pseudoprimes
Many introductory examples come from Fermat-style tests. Fermat’s test checks whether a number behaves like a prime in a modular exponent calculation. Some composite numbers pass that check for certain bases.
341
341 = 11 × 31. It is composite, but it passes the base-2 Fermat test.
561
561 = 3 × 11 × 17. It is the smallest Carmichael number, a special kind of Fermat pseudoprime.
2047
2047 = 23 × 89. It can look prime under some base-2 tests, even though it has factors.
Why Pseudoprimes Fool Some Prime Tests
A primality test may check a necessary condition for primes without checking every possible factor. If a composite number passes that condition, it can survive the test even though a factorization would expose it.
Fermat Test Pattern
an − 1 ≡ 1 mod n
For many prime numbers n and bases a not divisible by n, this congruence holds. Some composite values of n also satisfy it for a chosen base a. Those composite values are Fermat pseudoprimes to that base.
This is not a flaw in the idea of prime numbers. It is a limit of using one test condition as if it were a full proof.
Types of Pseudoprimes
Different tests create different pseudoprime categories. The same composite number may pass one test and fail another.
| Type | What It Means | Typical Test Context | Example |
|---|---|---|---|
| Fermat Pseudoprime | A composite number that passes Fermat’s congruence for a chosen base. | Fermat primality test | 341 to base 2 |
| Carmichael Number | A composite number that passes Fermat’s test for every coprime base. | Fermat tests using several bases | 561 |
| Euler Pseudoprime | A composite number that passes an Euler-style modular test. | Euler primality tests | Depends on the base |
| Strong Pseudoprime | A composite number that passes a stronger test condition for a selected base. | Miller-Rabin style testing | 2047 to base 2 |
Pseudoprime vs Prime vs Composite
A prime number has exactly two positive divisors: 1 and itself. A composite number has more than two positive divisors. A pseudoprime belongs to the composite side, even when it passes a test that many primes pass.
Prime Number
A whole number greater than 1 with exactly two positive divisors.
Composite Number
A whole number greater than 1 with more than two positive divisors.
Pseudoprime
A composite number that passes a selected prime-like test.
Prime Candidates Are Not Proven Primes
A number may be called a prime candidate when it has passed early filters. For example, it may not be divisible by 2, 3, or 5, or it may pass a modular test. That does not prove primality.
The same idea appears in the common 6n − 1 and 6n + 1 pattern. Every prime greater than 3 can be written in one of those forms, but many composite numbers also have those forms. For example, 25 = 6 × 4 + 1, yet 25 is composite.
Common Mistake
Passing a prime test does not always mean a number is prime. A test may show that a number is a strong candidate, while a proof or factorization is still needed to remove doubt.
How Pseudoprimes Affect Primality Testing
Pseudoprimes explain why modern primality testing often uses several checks instead of only one simple rule. Trial division can prove that a small number is composite by finding a factor. For larger numbers, modular tests can quickly reject many composites, but a single base may not catch every case.
The square root idea still matters. If a composite number n has a factor pair, at least one factor is less than or equal to √n. For small and medium-sized numbers, checking possible divisors up to √n gives a direct proof. For very large numbers, faster tests are often used before or alongside proof methods.
Check a Number Directly
To test a specific whole number, use the prime number checker. A checker can quickly label many numbers as prime, composite, or neither, while pseudoprimes show why the method behind the result matters.
Test a Prime Candidate
Enter a whole number and check whether it is prime, composite, or neither.
Why Carmichael Numbers Matter
Carmichael numbers are among the best-known pseudoprimes because they defeat a simple version of Fermat testing for every base that is coprime to the number. The smallest one is 561.
This makes Carmichael numbers a useful warning: repeating a weak test with several bases can still miss some composite numbers. Stronger tests reduce that risk by using stricter modular conditions.
Careful Language
A pseudoprime is not proof that prime tests are useless. It shows that a test must be matched to the level of certainty needed. In elementary number theory, factorization gives the clearest proof for small numbers.
Related Concepts
FAQ About Pseudoprimes
Is a pseudoprime actually prime?
No. A pseudoprime is composite. It only behaves like a prime under a particular test.
Why are pseudoprimes called false primes?
They are sometimes described that way because they pass a prime-like test while still having factors other than 1 and themselves.
What is the smallest Fermat pseudoprime to base 2?
The smallest commonly used example is 341, because 341 = 11 × 31 and it passes the base-2 Fermat test.
What is the smallest Carmichael number?
The smallest Carmichael number is 561. It factors as 3 × 11 × 17.
Can a number be a pseudoprime for one base but not another?
Yes. Many pseudoprime labels depend on the chosen base. A composite number may pass a test for one base and fail for a different base.
Do pseudoprimes make prime checkers unreliable?
Not by themselves. A well-designed checker can combine factor checks, stronger tests, and special handling for small values such as 0, 1, and 2. Pseudoprimes mainly show why the test method matters.