Prime number

A natural number greater than 1 whose only positive divisors are 1 and itself. Primes cannot be expressed as products of smaller natural numbers greater than 1.

Divisibility: An integer divides another when the second is an integer multiple of the first. A prime is defined by exactly which positive integers divide it.
Trial division: A method for testing divisibility by checking candidate factors up to the square root of a number. No composite number can evade a factor at or below its square root.
Twin prime: A pair of primes whose difference is 2. Twin primes illustrate how primes can cluster unusually close together.
Euclid: An ancient Greek mathematician whose surviving treatise, Elements, organized geometry and number theory. Elements contains the classic proof that there are infinitely many primes.
RSA: A public-key cryptosystem whose security relies on the difficulty of factoring products of large primes. RSA turns prime selection and multiplication into practical encryption keys.
Composite number: A natural number greater than 1 that has a positive divisor other than 1 and itself. Composite numbers are precisely the natural numbers greater than 1 that are not prime.
Sieve of Eratosthenes: An ancient algorithm that finds primes up to a limit by repeatedly removing multiples of known primes. It efficiently lists primes by eliminating numbers with known prime divisors.
Mersenne prime: A prime number of the form 2ⁿ − 1. Their form connects prime searches to efficient tests and perfect numbers.
Euclid's theorem: The theorem that infinitely many prime numbers exist. Its short contradiction proof establishes that no final prime exists.
Prime factorization: The expression of an integer greater than 1 as a product of primes. Factoring RSA moduli would reveal the secret structure behind their keys.

Linked from 88 pages