A prime number is a positive integer greater than 1 for which the only divisors are 1 and the number itself. For example, 17 is a prime number because the only divisors of 17 are 1 and 17, while 18 is not prime because 2, 3, 6, and 9 all divide 18 in addition to 1 and 18. About 2300 years ago, Euclid gave one of the first known proofs using the method of contradiction when he proved in the Elements that there are infinitely many prime numbers. Suppose that there are only a finite number of primes. Let p be the largest prime number. Multiply together all the prime numbers and add 1. This number cannot be prime because it is bigger than p, so it must have a prime divisor. But that prime divisor would then have to divide the number 1, which is impossible. Therefore there cannot be a finite number of primes. Euclid also gave a proof that every...