Prime Numbers | StudyTution

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