Processing math: 100%

Thursday, 6 June 2024

A Twist in Classical Proof of Infinitude of Primes

Most of us are familiar with the fact that there are infinitely many prime numbers. The classic argument of Euclid is as follows:

Consider a (nonempty) finite list of primes p_1, p_2 \ldots p_n. Since N := p_1p_2 \cdots p_n +1 > 1, there must a prime q dividing N and its easy to see that it is not in the given list.

Prime Factorization of integers plays an important role in the above argument  and this ultimately rests on Euclid's Lemma: if a,b are integers and p is a prime dividing ab then p divides either a or b.

Here is a modified version of classical proof. Choose any positive integer n. Note n and n+1 are coprime and so n(n+1) has at least two distinct prime factors. Similarly continue the argument with n(n+1) and n(n+1)+1 and so on.

No comments:

Post a Comment

Mathematical Biscuit I

 Can you find two irrational numbers a,b such that a^b is rational? Surprisingly, yes and the argument is very easy.  If $\sqrt{2}^{\sq...