# What are prime numbers and how many are there?

This book will start out by introducing the concept of prime numbers. Prime numbers are often considered the "building blocks" of the natural numbers and are therefore very important to number theory.

**Definition:** Prime numbers are natural numbers whose whole number divisors only include 1 and itself. 1 is not considered a prime number because the fundamental theorem wouldn't be satisfied.

## Fundamental Theorem of Arithmetic[edit | edit source]

Every natural number has got a unique prime factorization

This theorem is actually not very easy to prove. It needs lemmas, help theorems, to prove.

**Existence of a factorization:** This is a proof by induction. We assume there exists a prime factorization for every integer between 1 and n. Now we show that n also has a prime factorization. In case n is prime the factorization is obvious. In case n is not prime we can write: n = ab, 1 < a ≤ b < n. Due to our initial assumption we can write a = p1*p2*... and b = q1*q2*...*qj. Therefore n = p1*p2*...pi*q1*q2*...*qj. n is a product of primes.

### Lemmas[edit | edit source]

**Bézout's identity:** Given two nonzero integers a, b and their greatest common divisor d, there exist two integers x, y so that ax+by=d
Choose d to be the smallest possible positve nonzero number. Proof by contradiction:
Assume d does not divide a.
a = ds + r and 0 < r < d
r = a - ds
r = a - (ax + by)s
r = a(1 - xs) + b(-ys)
This is a contradiction to our statement because r is smaller than d. d divides a. We can show that it divides b as well using the same procedure.

We know that d divides both a and b. We now show that a common divisor e cannot be greater than d. e divides a and b. Therefore e must divide ax and by and their sum d. e must be less or equal to d. d is the greatest common divisor of a and b.

**Euclids Lemma:** Given a prime p that devides the product of the natural numbers ab, p must devide at least one of the factors a, b.

Proof: Assume p does not devide a. We must now show that p devides b. By Bezout's identity we know: ax + py = 1 We multiply by b. abx + bpy = b p divides abx because it devides ab and bpy as it is a factor. Therefore it also divides b.

### Uniqueness of factorization[edit | edit source]

**Proof of uniqueness:** Assume there are two factorizations of n. n = p1*p2*...*pj and n = q1*q2*...*qk. According to Euclid's lemma if p1 devides n either p1=q1 or(and) p1 divides q2*…*qk. By induction we can show there exists a qi=p1. We can now cancel p1 and qi and proceed in the same manner for the rest of the factors. We show that both factorizations are identical.

## Infinitude of Primes[edit | edit source]

Theorem: There exist infinitely many primes

Proof: This is probably the simplest and most well known proof of this theorem. It was first published by Euclid in his Elements. It is a prove by contradiction. We assume we have got the finite set of all primes. Then we multiply them all together and add one. The resulting number isn't divisible by any of the original primes. Therefore it must contain a prime factor not included in the original list. There can not be a finite set of primes so there must be infinitely many.