Fermat pseudoprime
E530313
A Fermat pseudoprime is a composite number that nevertheless satisfies Fermat's little theorem for a given base, making it appear prime under that specific primality test.
All labels observed (1)
| Label | Occurrences |
|---|---|
| Fermat pseudoprime canonical | 2 |
How this entity was disambiguated
This entity first appeared as the object of triple T5570590 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: Fermat pseudoprime Context triple: [Fermat's little theorem, relatedConcept, Fermat pseudoprime]
-
A.
Fermat number
A Fermat number is a special type of integer of the form \(F_n = 2^{2^n} + 1\), studied in number theory for its intriguing properties related to primality and constructible polygons.
-
B.
Fermat's little theorem
Fermat's little theorem is a fundamental result in number theory that characterizes how prime numbers interact with integer powers modulo that prime, forming the basis for many modern cryptographic algorithms.
-
C.
Adleman–Pomerance–Rumely primality test
The Adleman–Pomerance–Rumely primality test is an early deterministic algorithm in computational number theory used to determine whether a given number is prime, notable for its theoretical importance in the development of modern primality testing methods.
-
D.
Blum integer
A Blum integer is a special type of composite number formed as the product of two distinct prime numbers each congruent to 3 modulo 4, widely used in cryptography and pseudorandom number generation.
-
E.
Ramanujan prime
A Ramanujan prime is a type of prime number that provides a bound guaranteeing the existence of a certain number of primes in intervals of the form (x/2, x], named after the mathematician Srinivasa Ramanujan.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: Fermat pseudoprime Target entity description: A Fermat pseudoprime is a composite number that nevertheless satisfies Fermat's little theorem for a given base, making it appear prime under that specific primality test.
-
A.
Fermat number
A Fermat number is a special type of integer of the form \(F_n = 2^{2^n} + 1\), studied in number theory for its intriguing properties related to primality and constructible polygons.
-
B.
Fermat's little theorem
Fermat's little theorem is a fundamental result in number theory that characterizes how prime numbers interact with integer powers modulo that prime, forming the basis for many modern cryptographic algorithms.
-
C.
Adleman–Pomerance–Rumely primality test
The Adleman–Pomerance–Rumely primality test is an early deterministic algorithm in computational number theory used to determine whether a given number is prime, notable for its theoretical importance in the development of modern primality testing methods.
-
D.
Blum integer
A Blum integer is a special type of composite number formed as the product of two distinct prime numbers each congruent to 3 modulo 4, widely used in cryptography and pseudorandom number generation.
-
E.
Ramanujan prime
A Ramanujan prime is a type of prime number that provides a bound guaranteeing the existence of a certain number of primes in intervals of the form (x/2, x], named after the mathematician Srinivasa Ramanujan.
- F. None of above. chosen
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
composite number
ⓘ
number theory concept ⓘ pseudoprime ⓘ |
| appearsAs | prime under Fermat primality test for a specific base ⓘ |
| appearsIn |
computational number theory literature
ⓘ
cryptographic security analyses ⓘ |
| contrastsWith |
Carmichael number that is pseudoprime to all coprime bases
ⓘ
prime number that satisfies Fermat's little theorem for all coprime bases ⓘ |
| definedAs | composite integer n such that a^n ≡ a (mod n) for some integer base a coprime to n ⓘ |
| dependsOn | choice of base a ⓘ |
| failsToBe | prime number ⓘ |
| field | number theory ⓘ |
| generalizationOf | base-specific pseudoprime concepts ⓘ |
| hasAlternativeName | Fermat liar for base a (for the base that makes it pass the test) ⓘ |
| hasBaseSpecificForm |
Fermat pseudoprime to base 10
ⓘ
Fermat pseudoprime to base 2 ⓘ Fermat pseudoprime to base 3 ⓘ Fermat pseudoprime to base 5 ⓘ Fermat pseudoprime to base a ⓘ |
| hasCardinalityProperty | infinitely many Fermat pseudoprimes are known for many bases ⓘ |
| hasExample |
1105
ⓘ
1729 ⓘ 2152302898747 ⓘ 2465 ⓘ 2821 ⓘ 3215031751 ⓘ 341 ⓘ 341550071728321 ⓘ 41041 ⓘ 561 ⓘ 645 ⓘ 6601 ⓘ 825265 ⓘ 8911 ⓘ |
| hasProperty | passes a base-a Fermat primality test despite being composite ⓘ |
| hasTestingIssue | can cause Fermat primality test to falsely label a composite as prime ⓘ |
| hasUnresolvedQuestion | distribution of Fermat pseudoprimes for various bases ⓘ |
| isSubsetOf | composite integers that pass some primality test ⓘ |
| namedAfter | Pierre de Fermat ⓘ |
| relatedTo |
Carmichael number
ⓘ
Fermat primality test ⓘ Miller–Rabin primality test ⓘ
linked to:
Miller primality test
probabilistic primality testing ⓘ strong pseudoprime ⓘ |
| requires | gcd(a,n) = 1 for the base a and integer n ⓘ |
| satisfies | Fermat's little theorem for a given base ⓘ |
| usedIn |
analysis of reliability of Fermat primality test
ⓘ
construction of counterexamples to naive primality tests ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Fermat pseudoprime Description of subject: A Fermat pseudoprime is a composite number that nevertheless satisfies Fermat's little theorem for a given base, making it appear prime under that specific primality test.
Referenced by (2)
Full triples — surface form annotated when it differs from this entity's canonical label.