Prime Numbers Compendium

Purpose

This document provides a collection of mathematical facts about prime numbers.

What are prime numbers?

In number theory, a number is either composite or prime. Composite numbers are products of primes. Thus, 7 · 2 · 2 = 28, 5 · 3 · 2 = 30, and 103 · 1001 = 103,103 are examples of composite numbers.

If a number is not composite, then it is a unit or a prime number. Prime numbers have a unique factorization: 7 = 1 · 7, 340282366920938463463374607431768211456 = 340282366920938463463374607431768211456 · 1 = 2¹²⁸ - 1 is a Mersenne prime, proved by Euler to be infinite.

The unit 1 has no factorization (1 · 1) or has infinitely many (1 · 1 · 1 · 1 · 1...), which contradicts our finiteness definition; therefore, it has only one factorization. The unit cannot be prime, for it would have more than one factorization, contradicting the Fundamental Theorem of Arithmetic (FTA) that claims only one possible factorization for each positive integer.

The Fundamental Theorem of Arithmetic

This theorem is the primary reason prime numbers are so fundamental and useful.

        Theorem: Every positive integer can be factorized into a finite product of prime numbers in a unique way, except for their order.
      

More formally:

n = p_1^a \cdot p_2^b \cdot p_3^c \dots p_n^z \dots Z = \prod_{n=1}^z p_n^{a_n \dots z_n}

Note that there may be powers of a number.

As a corollary of this theorem, we can easily calculate the l.c.m. (least common multiple) and the g.c.d. (greatest common divisor) of two or more integers by their greatest and lowest exponents.

For example:

ext{g.c.d.}(60, 25) = (2^2 \cdot 3 \cdot 5, \; 5^2)

As g.c.d. is the greatest, we take the greatest exponent's basis, which is 5 and 2: 2 · 5 = 10. That is the g.c.d. To calculate the l.c.m., we do something analogous, taking instead the lowest exponent's basis and multiplying them.