Prime number

An integer greater than 1 that is not prime is called composite, and is a product of smaller integers: \(91=7\cdot13\). The number 1 is neither prime nor composite; excluding it is not arbitrary, since it keeps the factorization below unique. The only even prime is 2, and the first primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

The fundamental theorem of arithmetic states that every integer \(n>1\) is a product of primes, in exactly one way up to order: \(360=2^3\cdot3^2\cdot5\). That uniqueness rests on Euclid's lemma: if a prime divides \(ab\), it divides \(a\) or \(b\). With it one computes greatest common divisors and the number of divisors (if \(n=p_1^{e_1}\cdots p_r^{e_r}\), there are \((e_1+1)\cdots(e_r+1)\)), and many proofs follow.

To decide whether \(n\) is prime it suffices to test the primes \(p\le\sqrt n\): if \(n=ab\) with \(a\le b\), then \(a\le\sqrt n\). Euclid proved there are infinitely many primes: if there were finitely many, \(p_1p_2\cdots p_r+1\) would have a prime factor outside the list. Primes underlie public-key cryptography, which relies on how hard it is to factor huge numbers.