Infinitude of Primes - from Infinitude of Mutual Primes

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


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.


  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

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

Copyright © 1996-2018 Alexander Bogomolny