Infinitude of Primes - from Infinitude of Mutual 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

• Infinitude of Primes
  1. Infinitude of Primes - A Topological Proof
  2. Infinitude of Primes - A Topological Proof without Topology
  3. Infinitude of Primes Via *-Sets
  4. Infinitude of Primes Via Coprime Pairs
  5. Infinitude of Primes Via Fermat Numbers
  6. Infinitude of Primes Via Harmonic Series
  7. Infinitude of Primes Via Lower Bounds
  8. Infinitude of Primes - via Fibonacci Numbers
  9. New Proof of Euclid's Theorem
  10. Infinitude Of Primes From Legendre's Formula
  11. Infinitude of Primes - via Bertrand's Postulate
  12. Infinitude of Primes - An Impossible Injection
  13. Infinitude of Primes - from Infinitude of Mutual Primes
  14. Infinitude of Primes Via Euler's Product Formula
  15. Infinitude of Primes Via Euler's Product Formula for Pi
  16. Infinitude of Primes Via Powers of 2
  17. Infinitude of Primes As a Quickie
  18. A One-Line Proof of the Infinitude of Primes
  19. Infinitude of Primes - A. Thue's Proof
  20. Why The Number of Primes Could Not Be Finite?

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

Copyright © 1996-2018 Alexander Bogomolny