# Infinitude of Primes - from Infinitude of Mutual Primes

This follows from a proposition due to S. P. Mohanty:

### Proposition

Assume there exists an infinite set of positive integers \(A\) such that any two unequal elements of \(A\) are mutually prime. Then there are infinitely many primes.

Indeed, each of the members of \(A\) must be divisible by a prime that does not divide any other member of \(A\).

### Proof of the Proposition

Choose any coprime integers \(a\) and \(m\), and form the sequence:

\( \begin{cases} A_{0} &= a+m, \\ A_{n+1} &= A_{n}^{2} - mA_{n} + m,\space n\gt 0. \end{cases} \)

We are going to prove that \(\mbox{gcd}(A_{p},A_{q})=1\), for \(p\ne q\). The crucial step is to establish that

\(A_{n}=aA_{0}A_{1}\cdot\ldots\cdot A_{n-1}+m\).

This is done by induction. For \(n=0\) the statement holds by definition. Assume it holds for \(n=k\) and check that it does for \(n=k+1\):

\( \begin{align} A_{k+1} &= A_{k}^{2} - mA_{k} + m \\ &= (aA_{0}A_{1}\cdot\ldots\cdot A_{k-1}+m)^{2} - m(aA_{0}A_{1}\cdot\ldots\cdot A_{k-1}+m) + m \\ &= (aA_{0}A_{1}\cdot\ldots\cdot A_{k-1})^{2} + maA_{0}A_{1}\cdot\ldots\cdot A_{k-1} + m \\ &= aA_{0}A_{1}\cdot\ldots\cdot A_{k-1}(aA_{0}A_{1}\cdot\ldots\cdot A_{k-1} + m) + m \\ &= aA_{0}A_{1}\cdot\ldots\cdot A_{k-1}A_{k} + m. \end{align} \)

The statement implies

(*)

\(\displaystyle A_{n}=a^{2^n}\space (\mbox{mod}\space m)\)

and that the set \(\{A_{n}\}\) is infinite. This proves the proposition. Indeed, assume that \(\mbox{gcd}(A_{i},A_{j})=d\) and, for definiteness sake, that \(j\gt i\). Then

\(A_{j}=aA_{0}A_{1}\cdot\ldots\cdot A_{i}\cdot\ldots\cdot A_{j-1}+m\)

so that \(d\) divides \(m\) and, from (*), also \(a\); but \(\mbox{gcd}(a,m)=1\), hence, \(d=1\). In other words, \(\mbox{gcd}(A_{i},A_{j})=1\), as required.

**Note**: The special case \(a=1\) and \(m=2\) leads to the sequence \(\displaystyle f_{n}=2^{2^n}+1\) of *Fermat's primes* that satisfy the recurrence \(f_{n+1}=f_{n}^{2}-2f_{n}+2\), starting with \(f_{0}=3\). This case was dealt with by G. Polya.

## Reference

- S. P. Mohanty,
__The number of primes is infinite__,*Fib. Quarterly*, v 16 (1978), 381-384 - V. H. Moll, Numbers and Functions: From a Classical-Experimental Mathematician's Point of View, AMS, 2012, 26-27

- Infinitude of Primes
- Infinitude of Primes - A Topological Proof
- Infinitude of Primes - A Topological Proof without Topology
- Infinitude of Primes Via *-Sets
- Infinitude of Primes Via Coprime Pairs
- Infinitude of Primes Via Fermat Numbers
- Infinitude of Primes Via Harmonic Series
- Infinitude of Primes Via Lower Bounds
- Infinitude of Primes - via Fibonacci Numbers
- New Proof of Euclid's Theorem
- Infinitude Of Primes From Legendre's Formula
- Infinitude of Primes - via Bertrand's Postulate
- Infinitude of Primes - An Impossible Injection
- Infinitude of Primes - from Infinitude of Mutual Primes
- Infinitude of Primes Via Euler's Product Formula
- Infinitude of Primes Via Euler's Product Formula for Pi
- Infinitude of Primes Via Powers of 2
- Infinitude of Primes As a Quickie
- A One-Line Proof of the Infinitude of Primes
- Infinitude of Primes - A. Thue's Proof
- Why The Number of Primes Could Not Be Finite?

|Contact| |Front page| |Contents| |Algebra| |Up|

Copyright © 1996-2018 Alexander Bogomolny

65652090