Proth primality test

It first verifies that k is positive and odd, n is positive, and k is smaller than 2^n. It then computes the required modular power exactly with integer arithmetic. A successful congruence is a proof that the Proth number is prime; an unsuccessful witness is reported honestly as inconclusive unless it reveals a factor.

Enter a genuine Proth number and a witness

A Proth number has the precise form N = k × 2^n + 1, where k is a positive odd integer, n is a positive integer, and k is strictly less than 2^n. All of those conditions matter. This calculator accepts k and the witness as decimal text so large values stay exact instead of being rounded by ordinary floating-point input. Enter n as an integer from 1 through 10,000. The calculator constructs N rather than asking you to supply it separately, which prevents a mismatch between a claimed number and its defining parameters. It also checks that the witness lies strictly between 1 and N. Inputs with an even k, a nonpositive value, or k greater than or equal to 2^n are rejected as non-Proth inputs instead of being passed through a theorem whose assumptions do not apply. The returned number, exponent, witness, and residue are decimal strings where necessary, making the calculation auditable and safe to copy into another exact-arithmetic tool.

Understand what the congruence proves

For a valid Proth number N, Proth's theorem says that N is prime if there is an integer a for which a^((N−1)/2) is congruent to −1 modulo N. The supplied witness is a, and the calculator evaluates that modular power by repeated squaring without constructing the enormous ordinary power first. In the output, `residue` is the least nonnegative residue and `passes_test` is true exactly when it equals N−1, the modular representation of −1. In that case, `prime_proven` is true and the verdict is `prime`; this is a deterministic certificate under the already validated Proth conditions, not a probable-prime guess. The output includes the exact exponent (N−1)/2 so you can reproduce the congruence independently. The algorithm uses only integer operations, has no random witness selection, and does not consult a table or remote service. Repeating an input therefore returns the same result and exposes every important value used in the theorem.

Treat a failed witness correctly

A witness that does not produce −1 does not, by itself, prove that the number is composite. It only means that this particular witness did not satisfy the sufficient condition in Proth's theorem. For that reason, the calculator returns `inconclusive` rather than `composite` when the residue differs and the witness is coprime to N. You may then try another mathematically chosen witness or use a different deterministic primality method. There is one useful exception: before interpreting the congruence, the calculator computes the greatest common divisor of the witness and N. If that value is a proper factor, the result is conclusively `composite` and the factor is returned. This distinction prevents the common mistake of turning a one-way theorem into an invalid two-way test. It also makes the capability useful in automated workflows: accept `prime` as a proof, reject `composite` when a factor appears, and route `inconclusive` for another test rather than silently treating it as failure.