Infinitely Many Primes

Euclid's trick: N = p_1 p_2 p_n + 1 is coprime to every p_i.

The idea

Theorem (Euclid's theorem).

There are infinitely many primes.

Euclid proved this around 300 BC, and his argument remains the standard one. The claim says that no finite list of primes is complete: however many primes have been written down, some prime is missing from the list.

Ways to work on it

• Walkthrough. Euclid's proof in three steps.
• Practice. Multiply the first few primes, add one, and find a new prime factor.
• Hardest. Run Euclid's construction on an arbitrary list of primes, not just the first few.

Not sure where to start? Take the ten-question placement test.