Proth's theorem

Proth's theorem states that a Proth number N = k·2ⁿ + 1, with odd k < 2ⁿ, is prime if and only if some integer a satisfies a^((N−1)/2) ≡ −1 (mod N).

Connect

Proth number: An integer of the form k·2ⁿ + 1, where k is odd and 0 < k < 2ⁿ. The theorem applies precisely to numbers with this form.
Mersenne number: An integer of the form 2ⁿ−1. Mersenne numbers have a different special form and use a different primality criterion.
Primality certificate: A compact, checkable proof that a specified integer is prime. A witness satisfying the congruence can be checked to certify a Proth number's primality.
François Proth: A French mathematician associated with the theorem for numbers now called Proth numbers. His name is attached to the number family and its primality criterion.
Fermat's little theorem: A theorem stating that a prime p does not divide a^(p−1)−1 when p does not divide a. Its exponent congruence underlies the prime direction of Proth's test.
Fermat number: A number of the form 2^(2ⁿ)+1. Fermat numbers share a structured form but do not satisfy Proth's defining shape.
Proth prime: A prime number that is also a Proth number. These are the positive outcomes identified by applying the theorem.
Édouard Lucas: A French mathematician known for work on number theory, sequences, and primality testing. His work on primality criteria forms part of the theorem's mathematical lineage.
Euler's criterion: A criterion that determines whether an integer is a quadratic residue modulo an odd prime using a power congruence. The test's exponent is half the candidate number minus one.
Congruence: A relation stating that two integers have the same remainder upon division by a modulus. The theorem expresses its test as a congruence to −1.