Lucas primality test

Supply an odd integer n, a proposed Lucas witness, and the complete prime factorization of n minus one. The calculator validates the factorization itself, evaluates the required modular powers and greatest common divisors, and certifies n only when every condition of Lucas's theorem succeeds. Decimal strings preserve exact integers throughout, including values beyond JavaScript's ordinary safe-number range.

Prepare a complete certificate

Start with the odd integer you want to certify and factor n minus one completely. Enter n and every prime factor as a canonical decimal string, because strings preserve exact values all the way to the 64-bit limit. Each factor appears once with its positive exponent. For example, n = 29 has n minus one = 28 = 2 squared times 7, so the factor list contains 2 with exponent 2 and 7 with exponent 1. You must also provide a base a satisfying 1 < a < n. This base is the proposed Lucas witness. The checker deliberately requires the witness instead of searching for one: a certificate verification is fast, bounded, and repeatable, while a search can have an input-dependent running time. If you do not yet have a witness, try small bases with a separate primitive-root tool, then submit the resulting certificate here. Whitespace, signs, leading zeroes, floating-point notation, duplicate primes, composite factors, and missing factors are rejected rather than silently normalized, making the certificate suitable for audit logs and automated pipelines.

Understand the two Lucas conditions

The first calculation checks that a raised to n minus one is congruent to 1 modulo n. This is the familiar Fermat condition, but it cannot establish primality by itself because pseudoprimes can pass it. The decisive second stage uses every distinct prime q dividing n minus one. For each q, the checker computes a raised to (n minus one) divided by q modulo n, subtracts one, and verifies that the result has greatest common divisor 1 with n. Passing all these checks proves that the multiplicative order of a modulo n is exactly n minus one. An element modulo n cannot have that order unless n is prime, which is the core of Lucas's theorem. The returned check records expose the modular residue and gcd for each distinct q, while the exponent remains visible as part of the validated factorization. Modular exponentiation uses repeated squaring with exact BigInt arithmetic, so the calculation never depends on floating-point rounding, random bases, a network service, or probabilistic confidence.

Interpret failures and successful output

A successful response is a primality certificate result, not merely a probable-prime label. It repeats n, identifies the accepted witness, reports the Fermat residue, and lists one successful gcd check for each distinct factor of n minus one. Store the original input alongside this response when another system needs to reproduce the proof. Failures are intentionally specific. If the powered factors do not multiply to n minus one exactly, the factorization is incomplete or otherwise incorrect. If a listed factor is composite, or the same prime appears twice, the factorization is malformed even when its raw product happens to match. A failure of either modular condition means the supplied base is not a Lucas witness; it does not by itself distinguish a composite n from a prime paired with an unsuitable base. Try a mathematically justified alternative witness if primality is still expected. Inputs are limited to odd integers from 3 through 2^64 minus 1, allowing deterministic validation of the listed prime factors before the Lucas certificate is evaluated. The API price is $0.002 per request.