Prime Supports

Today we shall look at a fairly standard type of argument concerning prime divisors of integer sequences.

Given a sequence $(a_n)_{n\ge 1}$ , we say a prime $p$ is a prime divisor of $(a_n)$ if $p$ is a factor of some term of the sequence. The set of all prime divisors of $(a_n)$ is known as its prime support and is denoted $\mathcal{P}(a)$ . Our goal is to determine the nature of the prime support of a given sequence, and in most cases we wish to show that it is infinite.

The most direct way to approach such problems is to assume that the number of prime divisors of the sequence is only finite, say $\{p_1,p_2,\dots , p_k\}$ and explicitly construct a term of the sequence which has bounded $\nu_{p_i}$ with respect to each of these primes (in practice, usually just relatively prime). As a toy example, to see why the set of all prime divisors of $\mathbb{N}$ is infinite, note that $N=p_1p_2\dots p_k+1$ is relatively prime to all $p_1,\dots , p_k$ .

Problem 1 (Schur’s Theorem)

Prove that for all non-constant polynomials $P$ with integer coefficients the prime support of $\{P(i)\ne 0 : i\in \mathbb{N}\}$ is infinite.

Assume that the prime support is in fact finite, say $\{p_1,\dots , p_k\}$ and let $m_i$ denote the term such that $p_i \mid P(m_i)$ and say $e_i = \nu_{p_i}(P(m_i))$ .

But now, consider a positive integer $N$ such that $N \equiv m_i \pmod{p_i^{e_i+1}}$ . Then, $\nu_{p_i}(P(N))=e_i$ (why?) for all such $N$ . However, by the Chinese Remainder theorem, there exists infinitely many such $N$ implying that there exists some such $N$ for which $|P(N)| > \prod_{i=1}^kp_i^{e_i}$ (why?). This choice of $P(N)$ must then have a prime factor outside our assumed set, a contradiction.

Try showing that the prime support of the set $\{2^i+3^i : i\in \mathbb{N}\}$ is infinite using the same approach, with Fermat’s Little Theorem as the construction tool.

This is also where our heavyweights Zsigmondy’s and Kobayashi’s reign supreme, so it is often useful to have them at the back of your mind when trying these problems. 2000 IMO Problem 5 and 2018 USA TSTST Problem 8 are a couple of great examples.

Next, we will look at the interplay between $p-$ adic valuations and size arguments, which is one of the most common tropes throughout problems of this species.

We begin with one of the most classical examples. The method below generalizes to other polynomial recurrences of first order and can be used to solve 2016 China Team Selection Test Problem 4, 2023 Silk Road MO Problem 3, 2018 MEMO Team Round Problem 7, and 2018 Bulgarian MO Problem 5 among others.

Problem 2 (IMO Shortlist 2014 N7)

Let $c \ge 1$ be an integer. Define a sequence of positive integers by $a_1 = c$ and $a_{n+1}=a_n^3-4c\cdot a_n^2+5c^2\cdot a_n+c$ for all $n\ge 1$ . Prove that for each integer $n \ge 2$ there exists a prime number $p$ dividing $a_n$ but none of the numbers $a_1 , \ldots , a_{n -1}$ .

In order to facilitate our observations, we first normalize the sequence by setting $(x_n)$ be the sequence such that $x_0=0$ and $x_n=\frac{a_n}{c}$ for all $n\ge 1$ . It is not hard to see that this sequence satisfies the recurrence relation

$x_{n+1}=c^2(x_n^3-4x_n^2+5x_n)+1$

for all integers $n\ge 0$ . Since $x_n$ is clearly coprime to $c$ , it suffices to show that $x_{n+1}$ has a prime factor which does not divide any of $x_1,\dots , x_n$ for all $n \ge 1$ .

We begin by making two observations. First, we wish to show that $x_i \equiv x_j \pmod{x_m}$ if $i \equiv j \pmod{m}$ . To see why, we proceed via induction, for fixed $m$ . Since $x_0 \equiv x_m \pmod{x_m}$ for all $m$ , the base case is clear and for the inductive step simply note,

$x_{m+i+1} \equiv c^2(x_{m+i}^3-4x_{m+i}^2+5x_{m+i})+1 \equiv c^2(x_i^3-4x_i^2+5x_i)+1 \equiv x_{i+1}$

modulo $x_m$ . In fact, if $i,j \ge 2$ we can take the claim one step forward and prove the same result modulo $x_m^2$ . The approach is once again induction, with the inductive step following trivially from the prior equation. For the base case simply note $x_{m+1}\equiv 5c^2x_m+1 \pmod{x_m^2}$ so,

$x_{m+1}^3-4x_{m+1}^2+5x_{m+1} \equiv (5c^2x_m+1)^3-4(5c^2x_m+1)^2+5(5c^2x_m+1)$

$\equiv (15c^2x_m+1)-4(10c^2x_m+1)+5(5c^2x_m+1) \equiv 2 \pmod{x_m^2}$

which immediately implies $x_{m+2} \equiv x_2 \pmod{x_m^2}$ as desired.

Second, we observe that the sequence $(x_n)$ is pretty fast-growing. In particular, we claim that $x_n>x_1x_2\dots x_{n-1}$ for all $n \ge 2$ . The base cases $x_2$ and $x_3$ being clear, we tackle the inductive step by noting that $(x_n)$ is strictly increasing so,

$x_{n+1}>x-n^3-4x_n^2+5x_n>7x_n^2-4x_n^4>x_n^2$

for all $n\ge 3$ , and the inductive hypothesis applies.

Now, we are in a position to tackle the problem. By our second observation, there must exist some prime $p$ for which $\nu_p(x_n)>\max{\nu_p(x_1),\dots , \nu_p(x_{n-1})}$ (why?) and if it is not a new prime factor of the sequence, let $x_k$ denote the earliest term such that $p \mid x_k$ . Since $x_{n-1}$ and $x_n$ are clearly coprime by the nature of our recursion and $x_1=1$ , we have $n-2 \ge k \ge 2$ .

Now, due to the minimality of $k$ it follows that $k \mid n$ (why?) so we further have that $x_n \equiv x_k \pmod{x_k^2}$ . However, this is a clear contradiction since if $\alpha = \nu_p(x_k)$ we must have $p^{\alpha +1} \mid x_n$ and $p^{\alpha+1}\mid x_k^2$ which implies $p^{\alpha+1} \mid x_k$ as well, absurd.

Problem 3 (Brazil Undergraduate MO 2017/2)

Let $a$ and $b$ be fixed positive integers. Show that the set of primes that divide at least one of the terms of the sequence $a_n = a \cdot 2017^n + b \cdot 2016^n$ is infinite.

Here, we assume that the sequence has only finitely many prime divisors say $\{p_1,\dots , p_k\}$ . Observe that $\gcd(a\cdot 2017^n,b\cdot 2016^n)$ is bounded above by some constant $M$ since $\gcd(2016,2017)=1$ . The trick is to consider the index of the largest prime power dividing a term $a_n$ and call it $f(n)$ .

Now by the Pigeonhole principle, among any block of $k+1$ consecutive terms of the sequence, there must exist $i$ and $j$ in the range such that $f(i)=f(j)$ .

Thus, for all positive integers $n$ , there exists some $0 < m \le k$ such that $f(n)=f(n+m)$ . Let $\min(v_{p_j}(a_n), v_{p_j}(a_{n+m}))=\ell$ , then we have

$p_j^{\ell} \mid a \cdot 2017^n+b \cdot 2016^n$ and $p_j^{\ell} \mid a \cdot 2017^{n+m}+b \cdot 2016^{n+m}$ , so $p_j^{\ell} \mid b\cdot 2016^n \cdot (2016^m-2017^m)$ .

However, that forces $\sqrt[k]{2017^n} \le p_j^{\ell} \le M \cdot (2017^k-2016^k)$ which is a contradiction as $n$ goes to infinity.

The framework of the above solution can be adapted for a wide range of problems, including this floors problem by Atul Shatavart Nadig and Pranjal Srivastava, involving sequences $(x_n)$ for which a ‘nice’ choice of integers $m,n$ can be found such that $|mx_i-nx_j|$ is in some sense ‘bounded’ for our choice of $f(i)=f(j)$ .

The trick employed in our final problem is slightly more niche but is still important to note.

The key idea is that $A$ is a set of positive integers such that $\sum_{a\in A}\frac{1}{a}$ diverges, then the prime support of $A$ must be unbounded. Indeed, if it were finite, say $\{p_1,p_2,\dots , p_k\}$ then,

$\sum_{a\in A}\frac{1}{a}\le \prod_{i=1}^k\left(1+\frac{1}{p_i}+\frac{1}{p_i^2}+\dots \right) = \prod_{i=1}^k \left(\frac{p_i}{p_i-1}\right)$

which is a clear contradiction. We shall now look at an example.

Problem 4

Denote $p_n$ by the $n$ th prime number in ascending order. Prove that the sequence $\{\lfloor \lambda p_n \rfloor\}_{n=1}^{+\infty}$ has infinitely many prime divisors where $\lambda\in \mathbb{R}_{>1}$ .

Simply note that,

$\sum_{i=1}^{\infty} \frac{1}{\lfloor \lambda p_i \rfloor} \ge \sum_{i=1}^{\infty} \frac{1}{\lambda p_i}= \frac{1}{\lambda} \sum_{i=1}^{\infty} \frac{1}{p_i}$

which clearly diverges. Now that felt almost like cheating.

Prime Supports

Published by Lasitha Jayasinghe

1 thought on “Prime Supports”

Leave a comment Cancel reply

Share this:

Related

Published by Lasitha Jayasinghe

1 thought on “Prime Supports”

Leave a comment Cancel reply