Base-Two Fermat Pseudoprime Checker

Check whether n is composite and 2^(n−1)≡1 (mod n), using exact modular arithmetic and trial primality testing limited to n≤10¹².

Description

A base-two Fermat pseudoprime is a composite integer that passes the base-two Fermat congruence.

A base-two Fermat pseudoprime is a composite integer that passes the base-two Fermat congruence. This demonstrates why a single Fermat test cannot establish primality.^[1]

The tool returns isPseudoprime. The indexing and output conventions below determine how to read these values.

When to use Base-Two Fermat Pseudoprime Checker

Use this for the following task: Check whether n is composite and 2^(n−1)≡1 (mod n), using exact modular arithmetic and trial primality testing limited to n≤10¹². Use the input and output conventions below to reproduce the intended mathematical quantity.

How to use Base-Two Fermat Pseudoprime Checker and understand its results

Choose the required indexes, integers or sequence entries. Preserve decimal-string encodings where the field table specifies strings.
Enter n according to the field table, then run the tool.
Read isPseudoprime. A true flag means the candidate meets the stated property; false means it does not.
If the flag is false, review the candidate and definition. A well-formed nonmember is different from a rejected input.

Input field	Meaning	Value type and bounds	Requirement
n	Positive integer (primality resource limit 10^12)	integer; minimum 1; maximum 1000000000000	Required

Exclude small numbers, even numbers and primes, then use exact BigInt repeated-squaring modular exponentiation on the remaining candidate.

pseudoprime ⇔ composite(n) AND 2^(n−1) mod n=1

The symbols and boundary conditions refer to the supplied fields and the implementation described above.

Output field	Meaning	Value type
isPseudoprime	Whether n is a base-two Fermat pseudoprime	boolean

json

{
  "input": {
    "n": 341
  },
  "output": {
    "isPseudoprime": true
  }
}

Limitations and assumptions

The candidate is at most 10¹². This checks ordinary base-two Fermat pseudoprimality rather than strong pseudoprimality or all possible bases.

Use the declared integer bounds and string formats. Large exact outputs remain decimal strings; numerical approximations use ordinary floating-point arithmetic. A rejected input is different from a valid zero count or false membership flag.

Alternative or Complementary methods

Choose Carmichael Number Checker when you need its operation: Check the composite, square-free, and p−1-divides-n−1 conditions of Korselt’s criterion for a Carmichael number; trial division is limited to n≤10¹². Choose Wieferich Prime Checker for the complementary operation: Check whether p is prime and 2^(p−1)≡1 (mod p²) with exact modular arithmetic; primality testing is limited to p≤10¹².

Background reference: OEIS A001567.

References

OEIS A001567 — OEIS Foundation

Similar or alternative tools

Carmichael Number Checker
Check the composite, square-free, and p−1-divides-n−1 conditions of Korselt’s criterion for a Carmichael number; trial division is limited to n≤10¹².
Wieferich Prime Checker
Check whether p is prime and 2^(p−1)≡1 (mod p²) with exact modular arithmetic; primality testing is limited to p≤10¹².