# 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

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