Primes

The set of natural numbers is

$$\mathbb {N}= \{1,2,3,4,\ldots\},$$

and the set of integers is

$$\mathbb {Z}= \{\ldots, -2, -1, 0, 1,2,\ldots\}.$$

Definition 1.1 (Divides)   If $a, b\in \mathbb {Z}$ we say that $a$ divides $b$ , written $a\mid b$ , if $ac=b$ for some $c\in \mathbb {Z}$ . In this case we say $a$ is a divisor of $b$ . We say that $a$ does not divide $b$ , written $a\nmid b$ , if there is no $c\in \mathbb {Z}$ such that $ac=b$ .

For example, we have $2 \mid 6$ and $-3\mid 15$ . Also, all integers divide 0 , and 0 divides only 0 . However, $3$ does not divide $7$ in $\mathbb {Z}$ .

Remark 1.1   The notation $b \overset{\displaystyle .}{:}\! a$ for ``$b$ is divisible by $a$ '' is common in Russian literature on number theory.

Definition 1.1 (Prime and Composite)   An integer $n>1$ is prime if it the only positive divisors of $n$ are $1$ and $n$ . We call $n$ composite if $n$ is not prime.

The number $1$ is neither prime nor composite. The first few primes of  $\mathbb {N}$ are

$$2,3,5,7,11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, \ldots,$$

and the first few composites are

$$4,6,8,9,10,12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, \ldots.$$

Remark 1.1   J.H. Conway argues in [#!conway:sensual!#, viii] that $-1$ should be considered a prime, and in the 1914 table [#!lehmer:primetable!#], Lehmer considers $1$ to be a prime. In this book we consider neither $-1$ nor $1$ to be prime.

SAGE Example 1.1   In SAGE we compute all prime numbers between $a$ and $b-1$ , inclusive, using the command prime_range(a,b):

sage: prime_range(10,50)
[11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Computing the composites in an interval is a little more complicated:

sage: [n for n in range(10,30) if not is_prime(n)]
[10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28]

Every natural number is built, in a unique way, out of prime numbers:

Theorem 1.1 (Fundamental Theorem of Arithmetic)   Every natural number can be written as a product of primes uniquely up to order.

Note that primes are the products with only one factor and $1$ is the empty product.

Remark 1.1   Theorem 1.1.6, which we will prove in Section 1.1.4, is trickier to prove than you might first think. For example, unique factorization fails in the ring

$$\mathbb {Z}[\sqrt{-5}] = \{a + b\sqrt{-5} : a, b\in\mathbb {Z}\} \subset \mathbb {C},$$

where $6$ factors in two different ways:

$$6 = 2\cdot 3 = (1+\sqrt{-5})\cdot (1-\sqrt{-5}).$$