🔢 mathematics

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

Cet article étudie la suite $g_n = \gcd(a^n-1, b^n-1)$ en démontrant qu'elle satisfait une récurrence linéaire si et seulement si $a$ et $b$ sont multiplicativement dépendants, établissant ainsi la périodicité des suites de divisibilité communes pour des bases indépendantes, dérivant des formules exactes pour sa structure locale, et fournissant des réductions structurelles vers la conjecture entière d'Ailon–Rudnick.

Auteurs originaux : Khai-Hoan Nguyen-Dang

Publié 2026-06-09

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Khai-Hoan Nguyen-Dang

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous avez deux machines magiques géantes. Appelons-les Machine A et Machine B.

La Machine A prend un nombre $n$ et recrache un nombre géant : $a^n - 1$ .
La Machine B prend le même nombre $n$ et recrache un autre nombre géant : $b^n - 1$ .

Imaginez maintenant que vous avez un détecteur de « Plus Grand Commun Diviseur » (PGCD). Ce détecteur examine les deux nombres que les machines viennent de produire et trouve le plus grand nombre qui les divise tous les deux parfaitement. Appelons ce nombre commun $g_n$ .

L'article de Khai-Hoan Nguyen-Dang est une investigation profonde sur le comportement de cette séquence de nombres communs ( $g_1, g_2, g_3, \dots$ ). L'auteur pose la question suivante : Existe-t-il un modèle simple et prévisible pour ces nombres communs ?

Voici la décomposition des découvertes de l'article en utilisant des analogies simples :

1. Les deux types de machines

L'auteur découvre que le comportement de ces machines dépend entièrement de la relation entre leurs réglages de départ, $a$ et $b$ .

Les Machines « Dépendantes » (Prévisibles) :
Si $a$ et $b$ sont « multiplicativement dépendants », cela signifie que l'un est simplement une puissance de l'autre (comme 4 et 8, où $4=2^2$ et $8=2^3$ ).
- Le Résultat : Lorsque les machines sont dépendantes, la séquence des nombres communs ( $g_n$ ) suit une règle très stricte et simple appelée récurrence linéaire.
- L'Analogie : Pensez à une fanfare jouant une chanson. Si les batteurs et les trompettistes sont parfaitement synchronisés (dépendants), leur rythme combiné suit un battement simple et répétitif que l'on peut prédire indéfiniment. L'article prouve que si la séquence suit ce battement simple, les machines doivent être dépendantes.
Les Machines « Indépendantes » (Chaotiques) :
Si $a$ et $b$ sont « multiplicativement indépendants » (comme 2 et 3, où l'un n'est pas une puissance de l'autre), ils sont comme deux musiciens jouant des chansons complètement différentes.
- Le Résultat : Dans ce cas, la séquence des nombres communs ( $g_n$ ) ne peut pas être prédite par une règle simple et constante. Elle est trop chaotique.
- L'Analogie : Si vous essayez de forcer la fanfare à suivre un rythme simple alors que les musiciens jouent des chansons indépendantes, cela se brise. L'article prouve que peu importe la façon dont vous essayez d'ajuster une règle simple à ces nombres, elle finira par échouer.

2. Les motifs « Fantômes »

L'auteur pose également une question plus profonde : même si la séquence entière est chaotique, existe-t-il une partie de celle-ci qui est prévisible ? Plus précisément, existe-t-il une séquence plus petite qui divise les sorties des deux machines et suit une règle simple ?

La Découverte : Si les machines sont indépendantes, la réponse est non, à moins que cette séquence plus petite ne soit qu'une boucle répétitive ennuyeuse (périodique).
L'Analogie : Imaginez essayer de trouver un rythme caché dans le bruit chaotique des deux musiciens. L'article prouve que les seuls « rythmes » que vous pouvez trouver sont de simples boucles courtes qui se répètent sans cesse. Il n'existe aucun motif complexe caché à long terme.

3. Cartographier les points « Mauvais »

L'article se concentre ensuite pour regarder exactement quand le nombre commun $g_n$ est supérieur à 1 (c'est-à-dire quand les machines partagent un facteur).

L'Ensemble « Mauvais » : L'auteur crée une carte précise de tous les nombres $n$ où les machines partagent un facteur.
L'Analogie : Imaginez un calendrier. La plupart des jours, les machines produisent des nombres qui n'ont rien en commun. Mais certains jours, elles partagent un secret. L'article fournit une formule pour dessiner des « flèches » sur le calendrier pointant exactement vers les jours où ces secrets se produisent.
- Il s'avère que ces « jours secrets » sont simplement une collection de calendriers spécifiques et répétitifs (progressions arithmétiques).
- Si nous normalisons les machines pour qu'elles ne partagent pas de secret au jour 1, l'article montre que les « mauvais jours » sont exactement les jours qui tombent sur les calendriers de nombres premiers spécifiques.

4. Le mystère « Ailon–Rudnick »

Enfin, l'article s'attaque à un puzzle célèbre non résolu appelé la Conjecture d'Ailon–Rudnick.

Le Puzzle : Si les machines sont indépendantes et ne partagent pas de secret au jour 1, produiront-elles un jour des nombres qui n'ont aucun facteur commun (ce qui signifie que $g_n = 1$ ) pour une infinité de jours ?
La Contribution de l'Article : L'auteur ne résout pas tout le puzzle, mais il le décompose en morceaux plus petits et plus gérables. Il montre que pour résoudre le puzzle, il suffit de vérifier des types spécifiques de « mauvais jours » (comme les nombres premiers) et de chercher des « empreintes digitales » algébriques spécifiques (résultants).
L'Analogie : Au lieu d'essayer de prouver que tout le calendrier est principalement vide de secrets, l'auteur dit : « Regardons simplement les mardis. Si nous pouvons prouver qu'il n'y a pas de secrets les mardis, nous avons fait d'énormes progrès. » Il fournit une liste de contrôle de conditions qui, si elles sont remplies, résoudraient le mystère.

Résumé

En bref, cet article est une investigation rigoureuse du rythme des facteurs partagés entre deux séquences exponentielles.

Si les bases sont liées : Le rythme est simple et prévisible.
Si les bases sont sans lien : Le rythme est chaotique, et aucun motif simple caché n'existe (excepté des boucles ennuyeuses).
Les « mauvais » jours : L'auteur cartographie exactement quand ces facteurs partagés surviennent, transformant un mystère vague en une liste précise de calendriers répétitifs.
La Grande Conjecture : L'article fournit un nouvel ensemble d'outils plus précis pour aider les mathématiciens à enfin prouver si ces machines cessent de partager des secrets.

Résumé technique : Sur la suite $\gcd(a^n - 1, b^n - 1)$

Énoncé du problème

Cet article étudie la structure arithmétique de la suite $(g_n)_{n \ge 1}$ définie par $g_n := \gcd(a^n - 1, b^n - 1)$ pour des entiers $a, b \ge 2$ . La suite se situe naturellement à l'intersection de deux domaines classiques : les plus grands diviseurs communs de suites exponentielles et la théorie des suites de divisibilité.

La motivation centrale découle de la conjecture d'Ailon–Rudnick dans le cadre des entiers. Alors qu'Ailon et Rudnick ont prouvé un théorème fort dans le cadre des corps de fonctions stipulant que si $f, g \in \mathbb{C}[T]$ sont multiplicativement indépendants, $\gcd(f^n - 1, g^n - 1)$ est borné par un polynôme, le cas des entiers reste ouvert. La conjecture pose que si $a$ et $b$ sont multiplicativement indépendants et que $\gcd(a-1, b-1)=1$ , alors $\gcd(a^n - 1, b^n - 1) = 1$ pour une infinité de valeurs de $n$ .

L'article vise à délimiter précisément ce qui peut et ne peut pas être expliqué sur $(g_n)$ en utilisant les cadres des récurrences linéaires à coefficients constants et des suites de divisibilité linéaires (SDL).

Méthodologie

L'auteur emploie une combinaison de théorie algébrique des nombres, de bornes analytiques et de théorèmes de classification structurelle :

Rigidité des récurrences linéaires : L'article utilise le principe classique selon lequel les entiers algébriques dont tous les conjugués sont dans le disque unité fermé sont des racines de l'unité (lemme de Kronecker). Ceci est appliqué aux fonctions génératrices de récurrences linéaires pour montrer que les suites à croissance sous-exponentielle doivent finalement être polynomiales sur des progressions arithmétiques.
Bornes sous-exponentielles : L'apport quantitatif fondamental est le théorème de Bugeaud, Corvaja et Zannier, qui établit que pour $a, b$ multiplicativement indépendants, $\log \gcd(a^n - 1, b^n - 1) \le \epsilon n + O_\epsilon(1)$ .
Classification des SDL : Le travail s'appuie fortement sur la récente classification de Granville des suites de divisibilité linéaires entières, qui décompose ces suites en composantes périodiques, de puissance et générées par des polynômes.
Arithmétique locale (LTE) : L'article utilise le lemme de l'exposant levé (Lifting The Exponent, LTE) pour dériver des formules exactes pour les valuations $p$ -adiques de $g_n$ .
Résultants cyclotomiques : Pour traiter la conjecture d'Ailon–Rudrick pour les indices premiers, l'article emploie les propriétés des polynômes cyclotomiques et des résultants pour réduire le problème à des certificats finis et des problèmes de recouvrement locaux.

Contributions clés et résultats

1. Classification de la suite de GCD comme une récurrence linéaire

L'article établit un théorème de rigidité tranchant concernant la question de savoir si $(g_n)$ satisfait une récurrence linéaire à coefficients constants.

Théorème 1.1 : La suite $(g_n)$ $(g_{n})$ satisfait une récurrence linéaire à coefficients constants si et seulement si $a$ $a$ et $b$ $b$ sont multiplicativement dépendants.
- S'ils sont dépendants, il existe des entiers $c \ge 2$ et $r, s \ge 1$ tels que $a=c^r, b=c^s$ . Dans ce cas, $g_n = c^{\gcd(r,s)n} - 1$ , ce qui est une récurrence linéaire simple.
- S'ils sont indépendants, aucune queue de la suite ne satisfait une récurrence linéaire.
Corollaire 3.4 : Par conséquent, $(g_n)$ est une suite de divisibilité linéaire (SDL) si et seulement si $a$ et $b$ sont multiplicativement dépendants.

2. Rigidité des facteurs communs de SDL

L'article examine si une suite de divisibilité linéaire non triviale peut diviser simultanément $a^n - 1$ et $b^n - 1$ dans le cas indépendant.

Théorème 1.2 / Théorème 4.3 : Si $a$ $a$ et $b$ $b$ sont multiplicativement indépendants, alors toute suite de divisibilité linéaire entière $(W_n)$ $(W_{n})$ satisfaisant $W_n \mid a^n - 1$ $W_{n} ∣ a^{n} - 1$ et $W_n \mid b^n - 1$ $W_{n} ∣ b^{n} - 1$ est périodique.
- Ce résultat combine la borne de Bugeaud–Corvaja–Zannier (croissance sous-exponentielle) avec la classification de Granville des SDL. Cela implique que le mécanisme de "récurrence linéaire" ne peut pas expliquer les facteurs communs non triviaux dans le cas indépendant ; tout facteur commun de ce type doit être périodique.

3. Structure locale et formules de support

L'article fournit des formules exactes pour le support et les valuations de $g_n$ , identifiant l'ensemble "mauvais" $\{n : g_n > 1\}$ .

Formule de support (Proposition 5.1) : Pour un nombre premier $p \nmid ab$ , soit $L_p = \text{pcc}(\text{ord}_p(a), \text{ord}_p(b))$ . Alors $p \mid g_n \iff L_p \mid n$ .
Formule de valuation (Proposition 5.2) : Pour les nombres premiers impairs $p \nmid ab$ , si $L_p \mid n$ , alors $v_p(g_n) = c_p + v_p(n)$ , où $c_p = \min(v_p(a^{L_p}-1), v_p(b^{L_p}-1))$ .
Caractérisation de l'ensemble mauvais (Corollaire 5.4) : Sous la normalisation $\gcd(a-1, b-1)=1$ , l'ensemble $\{n : g_n > 1\}$ est exactement l'union de progressions arithmétiques :
$\{n \ge 1 : g_n > 1\} = \bigcup_{p \nmid ab} L_p \mathbb{N}$
La conjecture d'Ailon–Rudnick est ainsi équivalente à l'infinitude du complément de cette union.

4. Réductions vers la conjecture d'Ailon–Rudnick

L'article dérive plusieurs réductions structurelles qui isolent la difficulté de la conjecture sur des problèmes de recouvrement locaux, éliminant les mécanismes de récurrence linéaire.

Critère de support primitif (Proposition 5.6) : L'ensemble mauvais peut être compressé en une union de progressions générées par un ensemble primitif $B$ de périodes minimales $L_p$ . Si $\sum_{d \in B} 1/d < \infty$ , l'ensemble bon possède une densité asymptotique inférieure positive.
Réduction aux indices premiers (Théorème 6.2) : Pour un nombre premier $\ell$ en dehors d'un ensemble exceptionnel fini $\Sigma(a,b)$ , $g_\ell > 1$ si et seulement si $A_\ell = \frac{a^\ell-1}{a-1}$ et $B_\ell = \frac{b^\ell-1}{b-1}$ partagent un diviseur primitif commun (c'est-à-dire qu'il existe un premier $p$ tel que $\text{ord}_p(a) = \text{ord}_p(b) = \ell$ ).
Certificat fini (Théorème 6.4) : Si $g_\ell > 1$ , il existe des entiers $1 \le u, v \le \lceil \sqrt{\ell} \rceil$ et un premier $p \equiv 1 \pmod \ell$ tels que $p \mid a^u - b^v$ ou $p \mid a^u b^v - 1$ .
Compression par résultant (Corollaire 6.6) : La condition $g_\ell > 1$ implique l'existence d'un premier $p \equiv 1 \pmod \ell$ divisant le résultant cyclotomique $R_\ell(b-a) = \text{Res}_X(\Phi_\ell(X), \Phi_\ell(X + b-a))$ .

Signification et affirmations

L'article prétend fournir une analyse structurelle définitive de la suite $(g_n)$ dans le contexte des récurrences linéaires et des suites de divisibilité.

Élimination des mécanismes linéaires : La principale signification est la preuve que la suite $(g_n)$ elle-même n'est pas une suite de divisibilité linéaire (sauf si $a, b$ sont dépendants), et qu'aucune SDL non périodique ne peut servir de facteur commun dans le cas indépendant. Cela suggère que la conjecture d'Ailon–Rudnick ne peut être résolue en modélisant $(g_n)$ comme une récurrence linéaire.
Localisation de la difficulté : En établissant des formules locales exactes et des réductions, l'article soutient que la difficulté restante de la conjecture est un problème de recouvrement local régi par les ordres multiplicatifs et les obstructions d'indices premiers, plutôt qu'un phénomène de récurrence linéaire globale.
Caractérisation exacte : L'article fournit le premier support et les premières formules de valuation pour le cas général, identifiant l'ensemble mauvais comme une union explicite de progressions arithmétiques déterminées par des périodes locales $L_p$ .

L'auteur conclut que les "mécanismes de récurrence linéaire" sont pleinement compris et éliminés ; le problème se réduit désormais à l'analyse de la densité et des propriétés de recouvrement de l'ensemble des périodes locales $\{L_p\}$ .