Compositeness Certificate
A compositeness certificate is a piece of information which guarantees that a given number p is composite. Possible certificates consist of a factor of a number (which, in general, is much quicker to check by direct division than to determine initially), or of the determination that either
| a^(p-1)≢1 (mod p), |
(i.e., p violates Fermat's little theorem), or
| a!=-1,1 and a^2=1 (mod p). |
A quantity a satisfying either property is said to be a witness to p's compositeness.
See also
Adleman-Pomerance-Rumely Primality Test, Fermat's Little Theorem, Miller's Primality Test, Primality Certificate, WitnessExplore with Wolfram|Alpha
WolframAlpha
More things to try:
Cite this as:
Weisstein, Eric W. "Compositeness Certificate." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CompositenessCertificate.html