Fermat's Little Theorem gives results for taking a modulus by a number satisfying (*) this property.
The Pratt certificate for this is used in the Lucas-Lehmer algorithm for testing it. The Legendre symbol is used in the Solovay-Strassen test for this. The Miller-Rabin test for this results in many false witnesses from Carmichael numbers. Fermat's Little Theorem gives results for taking a modulus by a number satisfying (*) this property. A naive algorithm for testing this involves testing every integer up to the square root of a number to see if it is a divisor of that number. For 10 points, name this property of numbers that are only divisible by one and themselves.
The Pratt certificate for this is used in the Lucas-Lehmer algorithm for testing it.
primality [or prime number; accept equivalent word forms]