Divisibility properties in a sequence

We say that the ordered pair $(a,b)$ of positive integers is a good pair if $a$ divides $2^b - 1$ . (Note that the definition is not symmetric.) Then the problem is to maximize the number of good pairs of the form $(n_j, n_i)$ .

First we prove the following result.

Lemma 1 . If $a$ and $b$ are positive integers greater than 1, then at most one of the pairs $(a,b)$ and $(b,a)$ is good.

Proof . For the sake of contradiction, suppose that both pairs $(a,b)$ and $(b,a)$ are good, so $a$ divides $2^b - 1$ and $b$ divides $2^a - 1$ . Let $p$ be the smallest prime dividing either $a$ or $b$ . (Such a prime must exist since both $a$ and $b$ are greater than 1.) Without loss of generality, assume that $p$ divides $a$ . Then $p$ divides $2^b - 1$ . In particular, $p$ must be odd.

Let $d$ be the order of 2 modulo $p$ , so $d > 1$ . Since $2^b \equiv 1 \pmod{p}$ , it follows that $d$ divides $b$ . But by Fermat's Little Theorem, $2^{p - 1} \equiv 1 \pmod{p}$ , so $d$ divides $p - 1$ . In particular, $d$ is less than $p$ . Since $d > 1$ , $d$ must be divisible by some prime. But $d$ divides $b$ and $d$ is less than $p$ , contradicting the minimality of $p$ . Therefore, at most one of the pairs $(a,b)$ and $(b,a)$ is good. $\blacksquare$

It follows from Lemma 1 that for all $i \neq j$ , at most one of the pairs $(n_i, n_j$ ) and $(n_j, n_i)$ is good. By taking $a = b$ in Lemma 1, it also follows that no pair of the form $(n_i, n_i)$ is good. Hence, the number of good pairs among the 10 positive integers is at most $\binom{10}{2} = 45$ .

We claim that it is possible to have 45 good pairs. To show this, we prove another result.

Lemma 2 . If $(a,b)$ is a good pair, then so is $(2^a - 1, 2^b - 1)$ .

Proof . Let $(a,b)$ be a good pair, so $a$ divides $2^b - 1$ . Let $2^b - 1 = ac$ . Then $2^{2^b - 1} - 1 = 2^{ac} - 1 = (2^a - 1)(2^{a(c - 1)} + 2^{a(c - 2)} + \dots + 1),$ so $(2^a - 1, 2^b - 1)$ is also a good pair. $\blacksquare$

We construct a sequence of sequences inductively, where each sequence has the following properties: (1) All the terms are odd, distinct positive integers greater than 1, and (2) if $a$ and $b$ are any two different terms in the sequence in that order, then $(a,b)$ is a good pair.

The first sequence consists of one term, namely 3. Now, consider such a sequence $(n_1, n_2, \dots, n_k)$ of length $k$ , so $(n_i, n_j)$ is a good pair for all $i < j$ . Then the next sequence is $(2^{n_1} - 1, 2^{n_2} - 1, \dots, 2^{n_k} - 1, 2^c - 1).$ The value of $c$ is chosen as follows: Since all the $n_i$ are odd, $M := \text{lcm}(n_1, n_2, \dots, n_k)$ is odd. Then there exists a positive integer $c$ such that $2^c \equiv 1 \pmod{M}$ . Take the smallest positive integer $c$ that has this property.

In this new sequence with $k + 1$ terms, it is clear that property (1) holds. (Note that from the case $a = b$ in Lemma 1, $c$ cannot coincide with any of the $n_i$ .)

By Lemma 2, $(2^{n_i} - 1, 2^{n_j} - 1)$ is a good pair for all $i < j$ . Also, by construction, $(n_i, c)$ is a good pair for all $i$ , so again by Lemma 2, $(2^{n_i} - 1, 2^c - 1)$ is also a good pair for all $i$ . Thus, property (2) holds.

The first few sequences are as follows:

\begin{gather*} (3), \\ (7, 3), \\ (127, 7, 63), \\ (2^{127} - 1, 127, 2^{63} - 1, 2^{42} - 1). \end{gather*}

Thus, for any positive integer $k$ , we can find $k$ distinct positive integers greater than 1 that contain $\binom{k}{2}$ good pairs.