A prime number is a positive integer that is greater than one and has no factors except one and itself. One is not considered a prime number. 2, 3, 5, 7.. etc are some examples of prime numbers. Numbers that are not prime are called composite numbers. Here are the prime numbers less than 1000.

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997

So how do we find prime numbers?

One technique attributed to Eratosthenes of Cyrene (3rd century B.C) is called the sieve of Eratosthenes which allows us to find all prime numbers equal to or less than a specified number. The algorithm goes like this:

Start with all number from 2 to the specified number. For example, if we want to find all prime numbers less than or equal to 20, write down all numbers from 2 to 20.

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

Now remove all multiples of the first number (which is 2), from this list starting from the next position:

2, 3, 5, 7, 9, 11, 13, 15, 17, 19

Now remove all multiples of the second number (which is 3) from this list starting from the next position:

2, 3, 5, 7, 11, 13, 17, 19

Do this until you reach the end of the list. Now you will have the list of primes under 20 which is:

2, 3, 5, 7, 11, 13, 17, 19

The primes become more sparse as the numbers become larger and larger. So do they stop existing after we get to a certain point? In other words, is the list of prime numbers finite?

Euclid proved that there are an infinite number of prime numbers. He proved it using a technique called proof by contradiction.

To understand Euclid’s proof we need to learn about a theorem called the Fundamental Theorem of Arithmetic. This theorem states that every number greater than 1 is either a prime or is a unique product of primes.

Now let us move on to the proof.

Consider there are only a finite number of primes, say n. Let us represent this finite set as {p1, p2, p3…pn} where n is the total number of primes.

Let x = (p1 * p2 * p3 * .. * pn) + 1

Now ‘x’, which is one more than the product of the primes, should either be a prime or a composite. If x is prime, then the assumption that there are only n prime numbers is wrong. If x is a composite, then we should have a unique list of primes whose product will be equal to x (as stated by the Fundamental Theorem of Arithmetic).

Since x = (p1 * p2 * p3 * .. * pn) + 1, dividing x by any of the n primes would result in a remainder of 1. That means that there needs to exist at least one other prime number which would complete the unique list of primes that can be multiplied to get x. So our assumption that {p1, p2, p3… pn} represents the entire set of primes is wrong. To state it differently, there are infinite number of primes.

P.S.

As a reader you might be wondering what prompted me to write this post. I have been reading about prime numbers and found many explanations of the Euclid’s proof online. Some were plain wrong and some had very cryptic explanation. So I spent some time thinking about it and reading many websites to get things clear in my mind first and then I thought I will share it here for the benefit of other searching for the same.