**How Many Primes Are There?**

- A prime number p has exactly two factors, 1 and p
- The first few prime numbers are 2, 3, 5, 7, . . .
- Is the set of prime numbers finite?
- Equivalently, is there a largest prime?
- Euclid proved, around 300 BCE, that there cannot be a largest prime
- Hence there must be infinitely many primes

**A fact about divisibility**

- If n|(a+b) and n|a, then n|b
- Since n|(a + b), a + b = u · n
- Since n|a, a = v · n
- Therefore a + b = vn + b = un
- Hence b = (u − v)n

**There is no large prime number**

- Suppose the list of primes is finite, say{p1, p2, . . . , pk }
- Consider n = p1 · p2 · · · pk + 1. If n is a composite number, at least one prime pj is a factor, so pj |n.
- Since pj appears in the product p1 · p2 · · · pk , we have pj |p1 · p2 · · · pk
- From our observation about divisibility, if pj |n and pj |p1 · p2 · · · pk , we must also have pj |1, which is not possible
- So n must also be a prime, which is clearly bigger than pk

**More about Primes**

- Prime numbers have been extensively studied in

mathematics - Let π(x) denote the number of primes smaller than x
- The Prime Number Theorem says that π(x) is

approximately x log(x) for large values of x - Checking whether a number is a prime can be done

efficiently — [Agrawal, Kayal, Saxena 2002] - No known efficient way to find factors of non-prime

numbers - Large prime numbers are used in modern cryptography
- Essential for electronic commerce

Facebook Comments Box