🔢 mathematics

On the sequence $\mathrm{gcd}(a^n-1,b^n-1)$

This paper investigates the sequence $g_n = \gcd(a^n-1, b^n-1)$ by proving that it satisfies a linear recurrence if and only if $a$ and $b$ are multiplicatively dependent, establishing the periodicity of common divisibility sequences for independent bases, deriving exact formulas for its local structure, and providing structural reductions toward the integer Ailon–Rudnick conjecture.

Original authors: Khai-Hoan Nguyen-Dang

Published 2026-06-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Khai-Hoan Nguyen-Dang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have two giant, magical machines. Let's call them Machine A and Machine B.

Machine A takes a number $n$ and spits out a giant number: $a^n - 1$ .
Machine B takes the same number $n$ and spits out another giant number: $b^n - 1$ .

Now, imagine you have a "Greatest Common Divisor" (GCD) detector. This detector looks at the two numbers the machines just produced and finds the biggest number that divides both of them perfectly. Let's call this shared number $g_n$ .

The paper by Khai-Hoan Nguyen-Dang is a deep investigation into the behavior of this sequence of shared numbers ( $g_1, g_2, g_3, \dots$ ). The author asks: Is there a simple, predictable pattern to these shared numbers?

Here is the breakdown of the paper's findings using simple analogies:

1. The Two Types of Machines

The author discovers that the behavior of these machines depends entirely on the relationship between their starting settings, $a$ and $b$ .

The "Dependent" Machines (Predictable):
If $a$ and $b$ are "multiplicatively dependent," it means one is just a power of the other (like 4 and 8, where $4=2^2$ and $8=2^3$ ).
- The Result: When the machines are dependent, the sequence of shared numbers ( $g_n$ ) follows a very strict, simple rule called a linear recurrence.
- The Analogy: Think of this like a marching band playing a song. If the drummers and the trumpeters are perfectly synchronized (dependent), their combined rhythm follows a simple, repeating beat that you can predict forever. The paper proves that if the sequence follows this simple beat, the machines must be dependent.
The "Independent" Machines (Chaotic):
If $a$ and $b$ are "multiplicatively independent" (like 2 and 3, where one is not a power of the other), they are like two musicians playing completely different songs.
- The Result: In this case, the sequence of shared numbers ( $g_n$ ) cannot be predicted by any simple, constant rule. It is too chaotic.
- The Analogy: If you try to force the marching band to follow a simple beat while the musicians are playing independent songs, it breaks. The paper proves that no matter how you try to fit a simple rule to these numbers, it will eventually fail.

2. The "Ghost" Patterns

The author also asks a deeper question: Even if the whole sequence is chaotic, is there a part of it that is predictable? Specifically, is there a smaller sequence that divides both machines' outputs and follows a simple rule?

The Finding: If the machines are independent, the answer is no, unless that smaller sequence is just a boring, repeating loop (periodic).
The Analogy: Imagine trying to find a hidden rhythm inside the chaotic noise of the two musicians. The paper proves that the only "rhythms" you can find are just simple, short loops that repeat over and over. There are no hidden, complex, long-term patterns to be found.

3. Mapping the "Bad" Spots

The paper then zooms in to look at exactly when the shared number $g_n$ is greater than 1 (i.e., when the machines actually share a factor).

The "Bad Set": The author creates a precise map of all the numbers $n$ where the machines share a factor.
The Analogy: Imagine a calendar. Most days, the machines produce numbers that have nothing in common. But on certain days, they share a secret. The paper provides a formula to draw "arrows" on the calendar pointing to exactly which days these secrets happen.
- It turns out these "secret days" are just a collection of specific repeating schedules (arithmetic progressions).
- If you normalize the machines so they don't share a secret on day 1, the paper shows that the "bad days" are exactly the days that fall on the schedules of specific prime numbers.

4. The "Ailon–Rudnick" Mystery

Finally, the paper tackles a famous unsolved puzzle called the Ailon–Rudnick Conjecture.

The Puzzle: If the machines are independent and don't share a secret on day 1, will they eventually produce numbers that have no shared factors at all (meaning $g_n = 1$ ) for infinitely many days?
The Paper's Contribution: The author doesn't solve the whole puzzle, but they break it down into smaller, manageable pieces. They show that to solve the puzzle, you only need to check specific types of "bad days" (like prime numbers) and look for specific algebraic "fingerprints" (resultants).
The Analogy: Instead of trying to prove that the whole calendar is mostly empty of secrets, the author says, "Let's just look at the Tuesdays. If we can prove there are no secrets on Tuesdays, we've made huge progress." They provide a checklist of conditions that, if met, would solve the mystery.

Summary

In short, this paper is a rigorous investigation into the rhythm of shared factors between two exponential sequences.

If the bases are related: The rhythm is simple and predictable.
If the bases are unrelated: The rhythm is chaotic, and no hidden simple patterns exist (except for boring loops).
The "Bad" days: The author maps exactly when these shared factors occur, turning a vague mystery into a precise list of repeating schedules.
The Big Conjecture: The paper provides a new, sharper set of tools to help mathematicians finally prove whether these machines ever stop sharing secrets.

Technical Summary: On the Sequence $\gcd(a^n - 1, b^n - 1)$

Problem Statement

This paper investigates the arithmetic structure of the sequence $(g_n)_{n \ge 1}$ defined by $g_n := \gcd(a^n - 1, b^n - 1)$ for integers $a, b \ge 2$ . The sequence naturally sits at the intersection of two classical areas: the greatest common divisors of exponential sequences and the theory of divisibility sequences.

The central motivation stems from the Ailon–Rudnick conjecture in the integer setting. While Ailon and Rudnick proved a strong function-field theorem stating that if $f, g \in \mathbb{C}[T]$ are multiplicatively independent, $\gcd(f^n - 1, g^n - 1)$ is bounded by a polynomial, the integer case remains open. The conjecture posits that if $a$ and $b$ are multiplicatively independent and $\gcd(a-1, b-1)=1$ , then $\gcd(a^n - 1, b^n - 1) = 1$ for infinitely many $n$ .

The paper aims to delineate exactly what can and cannot be explained about $(g_n)$ using the frameworks of constant-coefficient linear recurrences and linear divisibility sequences (LDS).

Methodology

The author employs a combination of algebraic number theory, analytic bounds, and structural classification theorems:

Rigidity of Linear Recurrences: The paper utilizes the classical principle that algebraic integers with all conjugates in the closed unit disk are roots of unity (Kronecker's Lemma). This is applied to the generating functions of linear recurrences to show that sequences with subexponential growth must eventually be polynomial on arithmetic progressions.
Subexponential Bounds: The fundamental quantitative input is the theorem of Bugeaud, Corvaja, and Zannier, which establishes that for multiplicatively independent $a, b$ , $\log \gcd(a^n - 1, b^n - 1) \le \epsilon n + O_\epsilon(1)$ .
Classification of LDS: The work relies heavily on Granville's recent classification of integer linear divisibility sequences, which decomposes such sequences into periodic, power, and polynomially generated components.
Local Arithmetic (LTE): The paper uses the Lifting The Exponent (LTE) lemma to derive exact formulas for the $p$ -adic valuations of $g_n$ .
Cyclotomic Resultants: To address the Ailon–Rudnick conjecture for prime indices, the paper employs properties of cyclotomic polynomials and resultants to reduce the problem to finite certificates and local covering problems.

Key Contributions and Results

1. Classification of the GCD Sequence as a Linear Recurrence

The paper establishes a sharp rigidity theorem regarding whether $(g_n)$ satisfies a constant-coefficient linear recurrence.

Theorem 1.1: The sequence $(g_n)$ $(g_{n})$ satisfies a constant-coefficient linear recurrence if and only if $a$ $a$ and $b$ $b$ are multiplicatively dependent.
- If dependent, there exist integers $c \ge 2$ and $r, s \ge 1$ such that $a=c^r, b=c^s$ . In this case, $g_n = c^{\gcd(r,s)n} - 1$ , which is a simple linear recurrence.
- If independent, no tail of the sequence satisfies a linear recurrence.
Corollary 3.4: Consequently, $(g_n)$ is a linear divisibility sequence (LDS) if and only if $a$ and $b$ are multiplicatively dependent.

2. Rigidity of Common LDS Factors

The paper addresses whether any non-trivial linear divisibility sequence can divide both $a^n - 1$ and $b^n - 1$ simultaneously in the independent case.

Theorem 1.2 / Theorem 4.3: If $a$ $a$ and $b$ $b$ are multiplicatively independent, then every integer linear divisibility sequence $(W_n)$ $(W_{n})$ satisfying $W_n \mid a^n - 1$ $W_{n} ∣ a^{n} - 1$ and $W_n \mid b^n - 1$ $W_{n} ∣ b^{n} - 1$ is periodic.
- This result combines the Bugeaud–Corvaja–Zannier bound (subexponential growth) with Granville's classification of LDS. It implies that the "linear recurrence" mechanism cannot explain the non-trivial common factors in the independent case; any such common factor must be periodic.

3. Local Structure and Support Formulas

The paper provides exact formulas for the support and valuations of $g_n$ , identifying the "bad set" $\{n : g_n > 1\}$ .

Support Formula (Proposition 5.1): For a prime $p \nmid ab$ , let $L_p = \text{lcm}(\text{ord}_p(a), \text{ord}_p(b))$ . Then $p \mid g_n \iff L_p \mid n$ .
Valuation Formula (Proposition 5.2): For odd primes $p \nmid ab$ , if $L_p \mid n$ , then $v_p(g_n) = c_p + v_p(n)$ , where $c_p = \min(v_p(a^{L_p}-1), v_p(b^{L_p}-1))$ .
Bad Set Characterization (Corollary 5.4): Under the normalization $\gcd(a-1, b-1)=1$ , the set $\{n : g_n > 1\}$ is exactly the union of arithmetic progressions:
$\{n \ge 1 : g_n > 1\} = \bigcup_{p \nmid ab} L_p \mathbb{N}$
The Ailon–Rudnick conjecture is thus equivalent to the infinitude of the complement of this union.

4. Reductions toward the Ailon–Rudnick Conjecture

The paper derives several structural reductions that isolate the difficulty of the conjecture to local covering problems, eliminating linear recurrence mechanisms.

Primitive-Support Criterion (Proposition 5.6): The bad set can be compressed to a union of progressions generated by a primitive set $B$ of minimal periods $L_p$ . If $\sum_{d \in B} 1/d < \infty$ , the good set has positive lower asymptotic density.
Prime-Index Reduction (Theorem 6.2): For a prime $\ell$ outside a finite exceptional set $\Sigma(a,b)$ , $g_\ell > 1$ if and only if $A_\ell = \frac{a^\ell-1}{a-1}$ and $B_\ell = \frac{b^\ell-1}{b-1}$ share a common primitive divisor (i.e., there exists a prime $p$ with $\text{ord}_p(a) = \text{ord}_p(b) = \ell$ ).
Finite Certificate (Theorem 6.4): If $g_\ell > 1$ , there exist integers $1 \le u, v \le \lceil \sqrt{\ell} \rceil$ and a prime $p \equiv 1 \pmod \ell$ such that $p \mid a^u - b^v$ or $p \mid a^u b^v - 1$ .
Resultant Compression (Corollary 6.6): The condition $g_\ell > 1$ implies the existence of a prime $p \equiv 1 \pmod \ell$ dividing the cyclotomic resultant $R_\ell(b-a) = \text{Res}_X(\Phi_\ell(X), \Phi_\ell(X + b-a))$ .

Significance and Claims

The paper claims to provide a definitive structural analysis of the sequence $(g_n)$ within the context of linear recurrences and divisibility sequences.

Elimination of Linear Mechanisms: The primary significance is the proof that the sequence $(g_n)$ itself is not a linear divisibility sequence (unless $a, b$ are dependent), and that no non-periodic linear divisibility sequence can serve as a common factor in the independent case. This suggests that the Ailon–Rudnick conjecture cannot be resolved by modeling $(g_n)$ as a linear recurrence.
Localization of Difficulty: By establishing exact local formulas and reductions, the paper argues that the remaining difficulty of the conjecture is a local covering problem governed by multiplicative orders and prime-index obstructions, rather than a global linear recurrence phenomenon.
Exact Characterization: The paper provides the first exact support and valuation formulas for the general case, identifying the bad set as an explicit union of arithmetic progressions determined by local periods $L_p$ .

The author concludes that the "linear-recurrence mechanisms" are fully understood and eliminated; the problem now reduces to analyzing the density and covering properties of the set of local periods $\{L_p\}$ .