2.1 Topics in Number Theory 3

Definition 2.1.6 (prime numbers)Anp 2 is said to be prime if its only positive

divisors are 1 and p. Otherwise, p is called composite.

Theorem 2.1.2 If p is prime and p|ab, then either p|a or p|b(or both).

Theorem 2.1.3 There are an infinite number of prime numbers.

Proof.

Let us assume that there are only finitely many primes, then we can list them all:

p1,p2, ··· ,pr .

Let P be their product, a very big number but still finite:

P = p1 × p2 ×···×pr.

We now consider P + 1 which is an integer and so can be factored into primes. But since

all of the primes divide P , none of them divide P + 1, since if pi divides P and it divides

P + 1, then it must divide 1. This our contradiction.

Observe that all that this proof do es for us is prove that there are infinitely many

primes. It is useless in trying to generate the primes. If we know the first n primes, this

will give us a new prime, but probably not the next prime. Also, this do es not promise

that P + 1 will be a prime. For example:

(2 × 3 × 5 × 7 × 11 × 13) + 1 = 30031 = 59 × 509.