Prime number
Definition and Basics
A prime number (or a prime) is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4. Primes are central in number theory because of the Fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order.
History
The concept of prime number dates back to ancient times. The ancient Greeks were the first to systematically study prime numbers. Euclid's Elements contains important theorems about primes, including the infinitude of primes and the Euclidean algorithm for finding the greatest common divisor of two numbers.
Properties
Prime numbers exhibit many interesting properties, some of which are quite complex. For example, the Prime number theorem provides a rough approximation of how primes are distributed among the natural numbers. Another property is that there are infinitely many prime numbers. This was proven by Euclid over two thousand years ago.
Prime Number Theorem
The Prime Number Theorem describes the distribution of prime numbers among positive integers. It formalizes the intuitive idea that primes become less common as they become larger by precisely quantifying the rate at which this occurs. The theorem was first stated by Carl Friedrich Gauss and Adrien-Marie Legendre and was conclusively proven by Jacques Hadamard and Charles Jean de la Vallée Poussin independently in 1896.
Sieve Theory
Sieve theory is a set of general techniques in number theory, that are used to count, or more realistically to estimate the size of, sifted sets of integers. The original context of sieve theory was the problem of estimating the number of primes (prime numbers) in an arithmetic progression.
Primality Testing
Primality testing is the process of determining whether a given number is prime. There are several efficient algorithms, such as the AKS primality test, that can determine the primality of a number. Primality testing has important applications in cryptography.
Primes in Cryptography
Prime numbers are crucial in cryptography and are widely used in systems such as RSA. The difficulty of factoring large composite numbers that are the product of two primes is the basis of RSA security. This makes the distribution of prime numbers and the ability to find them efficiently of critical importance.