Question

Prove there are infinitely many primes by showing that${\mathbf{Q}}_{\mathbf{n}}\mathbf{=}\mathbf{n}\mathbf{!}\mathbf{+}\mathbf{1}$must have a prime factor greater than n whenever n is a positive integer.

Short answer

Proof by contradiction

Step-by-step solution

Step 1:

${\mathbf{Q}}_{\mathbf{n}}\mathbf{=}\mathbf{n}\mathbf{!}\mathbf{+}\mathbf{1}\mathbf{=}\mathbf{1}\mathbf{}\mathbf{mod}\mathbf{}\mathbf{k}$or every$\mathbf{2}\mathbf{<}\mathbf{k}\mathbf{<}\mathbf{n}$ .

Hence${\mathbf{Q}}_{\mathbf{n}}$is not divisible by any natural number less than or equal to(other than 1).

Hence the prime factors of ${\mathbf{Q}}_{\mathbf{n}}$must be larger than .

Step 2:

Now suppose that were only infinitely many primes ${\mathbf{p}}_1<{\mathbf{p}}_2<\dots .<{\mathbf{p}}_{m-1}<{\mathbf{p}}_m,\text{then}{\mathbf{Q}}_{{\mathbf{p}}_m}$, then will have prime factors bigger than${\mathbf{p}}_{\mathbf{m}}$ that is it has no prime factors, which contradicts the fundamental theorem arithmetic.

Thus, there should be infinitely many primes.