0

Theorem (Euclid): There are infinitely many prime numbers.

Proof: We will prove it by contradiction. Assume the set of prime numbers is finite. We can denote them by $p_1,p_2,...,p_n$. Define $M = p_1p_2...p_n+1$. By the corollary above, $M$ must have a prime divisor. Since the only primes are $p_1 , p_2 ,..., p_n$ , there exists $i\in{1,2,...,n}$ such that $p_i|M$. But this implies $p_i |1$, which is a contradiction.

In the proof above, they said that $p_i | M$ implies $p_i |1$ – why? I'm confused on this part.

PCeltide
  • 1,534
Sooraj Singh
  • 1

1 Answers1

0

Since $M=p_1p_2p_3\cdots p_n+1$, by the euclidean gcd algorithm

$$a | ab+c \implies a | c$$

$$p_i | M \implies p_i | p_i*\cdots +1 \implies p_i | 1$$

The euclidean gcd algorithm "claim" can be proven quite easily, so try it yourself :D

Gareth Ma
  • 1,853