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.

Representing natural numbers as products of primes

The fundamental theorem of arithmetic states that every positive integer can be written as a product of primes in an essentially unique way. Primes are thus the "basic building blocks" of the natural numbers (The proof of this is below). For example, we can write

Related Topics:
Fundamental theorem of arithmetic - Unique

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:23244 = 2^2 imes 3 imes 13 imes 149

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

and any other such factorization of 23244 will be identical, except for the order of the factors. See prime factorization algorithm for details for how to do this in practice, for larger numbers.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The importance of this theorem is one of the reasons for the exclusion of 1 from the set of prime numbers. If 1 were admitted as a prime, the precise statement of the theorem would require additional qualifications.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Proof: Every positive integer greater than 1 has a prime divisor.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

We prove this through contradiction; we assume that there exists a number greater than one that has no prime divisors. Then, as the set of positive integers greater than one with no prime divisors is not an empty set, the well-ordering property tells us that there is a least positive integer n greater than 1 with no prime divisors. Since n has no prime divisors and n divides n, we see that n is not prime. Hence we can write n=ab with 1

~ ~ ~ ~ ~ ~ ~ ~ ~ ~