Number Theory/The Integers/Prime Numbers

Introduction

Prime numbers are essential to everything discussed within number theory. In a way, prime numbers are the "building blocks" of all the natural numbers greater than 1, as you can always express them as a product of primes. Prime numbers are natural numbers greater than 1 such that their divisors are only $\pm 1$ and itself. Numbers greater than 1 that are not prime are termed composite.

Definition

An integer $p>1$ is called a prime number if 1 and ${\textstyle p}$ are its only positive divisors. Stated in another way, ${\textstyle p}$ cannot be expressed as a product of two natural numbers both smaller than ${\textstyle p}$ .

A natural number $q>1$ is composite if it has a divisor $a$ such that $1<a<q$ . It then follows that $q=ab$ , for some $b$ such that $1<b<q$ .

The first 10 prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Notice that 2 is the only even prime, as any even number $n$ greater than 2 can be expressed in the form $n=2k$ such that $1<k<n$ .

Finding Primes

Sieve of Eratosthenes

Prime numbers have been the subject of study of mathematicians for milennia. Eratosthenes (b. c. 276BC – c. 195) was a Greek mathematician from the Classical antiquity who developed a systemic method to find prime numbers.

First one lists all the numbers up to certain amount, in the image to the right we finish at 99, but one may list more numbers as desired. Next, one takes all numbers that are multiples of 2 (except 2 itself) and crosses them out. Since all of these numbers will be even they can be written as $2k$ and thus not prime. Then, repeat this process for the next smallest number that was not crossed out, in this case 3. Again, cancel all numbers that are multiples of 3, since all cancelled out numbers can be written as $3k$ they too are not prime. Repeating this process for 5 and 7 we have form the chart formed on the right. Once one gets the next smallest number that is not circled out and it itself does not have any multiples that are not already colored in (in this case 11) halt the sieve.

One may also note we may stop sieving numbers if the last number we are seiving to (in the previous example, 99) is less than the square of the next prime. The next prime in the sequence is 11, note that $11^{2}=121$ , since $121<99$ we can halt the sieve at this point too. Since all multiples of 11: $11,22,33,44,\dots$ will be multiplies of 11 with at least one other prime except for $121$ as the the only prime factor is 11 itself.

Prime Number Results

Euclid's Theorem

By the Sieve of Eratosthenes we expect the number of primes to get smaller as we big larger and larger numbers because we are more likely to find a divisor of a number. However, counterintuitively, there are infinitely many prime numbers. This result is known as Euclid's Theorem and he proved it nearly 100 years before the Sieve of Eratosthenes was formulated in his textbook Elements.

Euclid's Theorem

The set $\mathbb {P}$ which contains all primes is infinite.

Proof. Suppose that for argument's sake the list of primes is finite, then we have $\mathbb {P} ^{*}:=\{p_{1},p_{2},\dots ,p_{n}\}$ . Then define a two new numbers $P:=p_{1}p_{2}\dots p_{n}$ and $q:=P+1$ . Now $q$ is either prime or not prime.

If $q$ is prime then $q\not \in \mathbb {P} ^{*}$ . Hence there exists a prime outside the finite list, contradicting the assumption.
However, if $q$ is not prime then $\exists p:p\mid q$ , $p\in \mathbb {P}$ . If howvever $p\in \mathbb {P} ^{*}\implies p\mid P$ , if $p$ divides both $P$ and $q=P+1$ then it must divide their difference. Therefore $p\mid (P+1)-P\implies p\mid 1$ . No prime number divides 1. Hence $p\not \in \mathbb {P} ^{*}$ . Therefore in either case $\exists p\in \mathbb {P} :p\not \in \mathbb {P} ^{*}$ . This contradicts the assumption that the set of primes is finite. Hence $\mathbb {P}$ is infinite. □