Prime numbers – basics and significance
The atoms of the natural numbers and their applications
Prime numbers are natural numbers greater than 1 that are only divisible by 1 and themselves. They are considered the "atoms" of arithmetic: the fundamental theorem of arithmetic states that every natural number greater than 1 can be represented uniquely as a product of prime numbers. This property makes prime numbers the foundation of modern number theory and cryptography.
The most efficient primality test for medium-sized numbers is trial division: you check all divisors from 2 up to the square root of the number being tested. If none of them is a divisor, the number is prime. For n = 17: √17 ≈ 4.1, so test 2, 3, 4 – none divides 17 → 17 is prime. For large numbers (above 10⁷), probabilistic tests such as Miller-Rabin are used, which are considerably faster.
The prime factorization writes every composite number as a product of its prime factors. For 12: 12 = 2 × 2 × 3. This decomposition is the basis for calculating the GCD and LCM. The RSA encryption algorithm, which secures the internet, relies on the fact that factoring large numbers (hundreds of digits) into their prime factors is practically impossible – even for modern supercomputers.
Well-known sequences of prime numbers: the set of prime numbers below 100 comprises 25 numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. The Mersenne primes(numbers of the form 2ⁿ − 1, e.g. 31 = 2⁵ − 1) are relevant to the search for especially large prime numbers. The largest currently known prime number has over 40 million decimal digits and is a Mersenne prime.