Prime Numbers

A prime number (also called a prime) is a natural number greater than 1 that cannot be divided evenly by any number other than 1 and itself. Examples include 2, 3, 5, 7, 11, and 13. Natural numbers greater than 1 that are not prime are called composite numbers, because they can be divided by smaller numbers greater than one.

The number 1 is not counted among the primes, as it has only one divisor. This definition is not arbitrary; it makes other mathematical rules work consistently. 2 is the only even prime number; all other primes are odd.

Fundamental Theorem of Arithmetic

Every natural number greater than 1 can be written as a product of prime numbers in exactly one way, if order is ignored. For example: 60 = 2 × 2 × 3 × 5. This is why primes are seen as the 'basic building blocks' of natural numbers, similar to atoms in chemistry.

The Number of Primes

There are infinitely many primes. An ancient proof attributed to Euclid showed this: if you multiply all numbers on any finite list of primes and add 1, the result is a prime divisor not on the original list. Although primes are infinite in number, they become rarer as numbers grow larger.

Methods of Finding Them

The most common method for generating a list of primes is the 'Sieve of Eratosthenes': write out all numbers up to a desired limit, then systematically remove multiples of each prime starting with 2. What remains are the primes. To check whether a single number is prime, it is sufficient to test divisibility up to the square root of that number.

Modern Applications

Internet data security systems such as RSA depend on the fact that large primes can be multiplied together easily, while factoring the product is hard when using ordinary computers. For this reason, finding large prime numbers is an ongoing task combining mathematics and computer science.