Maths Olympiad Prep

Library / /336 of 520

Number theory Difficulty 6.3 National olympiad Prove it

Lemma 7 There are infinitely many prime numbers

Solution

Assume the number of prime numbers is finite, with a total of nn primes, which are p1,p2p_{1}, p_{2}, p3,,pnp_{3}, \cdots, p_{n}. Among them, p1=2,p2=3,p3=5,p_{1}=2, p_{2}=3, p_{3}=5, \cdots. Let a=p1pn+1a=p_{1} \cdots p_{n}+1. If aa is a prime number, then because aa is not equal to any of p1,p2,,pnp_{1}, p_{2}, \cdots, p_{n}, the number of prime numbers is at least n+1n+1, which contradicts the assumption that there are only nn prime numbers. If aa is not a prime number, then by Lemma 5, the smallest factor bb of aa greater than 1 is a prime number. Since p1pnp_{1} \cdots p_{n} is divisible by any of p1,p2,,pnp_{1}, p_{2}, \cdots, p_{n}, but 1 is not divisible by any of p1,p2,,pnp_{1}, p_{2}, \cdots, p_{n}, aa is not divisible by any of p1,p2,,pnp_{1}, p_{2}, \cdots, p_{n}. Therefore, bb is not equal to any of p1,,pnp_{1}, \cdots, p_{n}, so there are prime numbers outside of p1,,pnp_{1}, \cdots, p_{n}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.