Prime number

In mathematics, a prime number (or prime) is a natural number greater than one whose only positive divisors are one and itself. Or for short: A prime number is a natural number with exactly two natural divisors. A natural number that is greater than one and is not a prime is called a composite number. The numbers zero and one are neither prime nor composite. The property of being a prime is called primality. Prime numbers are of fundamental importance in number theory.

Some properties of primes

• If p is a prime number and p divides a product ab of integers, then p divides a or p divides b. This proposition was proved by Euclid and is known as Euclid's lemma. It is used in some proofs of the uniqueness of prime factorizations.
• The ring Z/nZ (see modular arithmetic) is a field if and only if n is a prime. Put another way: n is prime if and only if φ(n) = n − 1.
• If p is prime and a is any integer, then a^p − a is divisible by p (Fermat's little theorem).
• If p is a prime number other than 2 and 5, 1/p is always a recurring decimal, with a period of p-1 or a divisor of p-1. This can be deduced directly from Fermat's little theorem. 1/p expressed likewise in base q (i.e. other than base 10) has similar effect, provided that p is not a prime factor of q. The Wiki page on recurring decimal shows some of the interesting properties.
• An integer p > 1 is prime if and only if the factorial (p − 1)! + 1 is divisible by p (Wilson's theorem). Conversely, an integer n > 4 is composite if and only if (n − 1)! is divisible by n.
• If n is a positive integer, then there is always a prime number p with n < p ≤ 2n (Bertrand's postulate).
• Adding the reciprocals of all primes together results in a divergent infinite series (proof). More precisely, if S(x) denotes the sum of the reciprocals of all prime numbers p with p ≤ x, then S(x) = Θ(ln ln x) for x → ∞ (see Big O notation).
• For each prime number p > 2, there exists a natural number n such that p = 4n ± 1.
• For each prime number p > 3, there exists a natural number n such that p = 6n ± 1.
• In every arithmetic progression a, a + q, a + 2q, a + 3q,... where the positive integers a and q ≥ 1 are coprime, there are infinitely many primes (Dirichlet's theorem).
• The characteristic of every field is either zero or a prime number.
• If G is a finite group and pⁿ is the highest power of the prime p which divides the order of G, then G has a subgroup of order pⁿ. (Sylow theorems)
• If p is prime and G is a group with pⁿ elements, then G contains an element of order p.
• The prime number theorem says that the proportion of primes less than x is asymptotic to 1/ln x (in other words, as x gets very large, the likelihood that a number less than x is prime is inversely proportional to the number of digits in x).