🔢 mathematics

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

본 논문은 $a$ 와 $b$ 가 곱셈적으로 종속적일 때만 수열 $g_n = \gcd(a^n-1, b^n-1)$ 이 선형 점화식을 만족함을 증명함으로써 해당 수열을 조사하고, 독립적인 밑(base)들에 대한 공통 약수 수열의 주기성을 확립하며, 그 국소적 구조에 대한 정확한 공식을 도출하고, 정수 에일론-루드닉(Ailon–Rudnick) 추측을 향한 구조적 축소를 제공한다.

원저자: Khai-Hoan Nguyen-Dang

게시일 2026-06-09

📖 4 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Khai-Hoan Nguyen-Dang

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신에게 두 대의 거대하고 마법 같은 기계가 있다고 상상해 보세요. 이 기계들을 각각 머신 A와 머신 B라고 부르겠습니다.

머신 A는 숫자 $n$ 을 입력받아 거대한 숫자 $a^n - 1$ 을 내뱉습니다.
머신 B는 동일한 숫자 $n$ 을 입력받아 또 다른 거대한 숫자 $b^n - 1$ 을 내뱉습니다.

이제, 당신에게 "최대공약수(GCD)" 탐지기가 있다고 상상해 보세요. 이 탐지기는 두 기계가 방금 만들어낸 두 숫자를 살펴보고, 두 숫자를 모두 완벽하게 나누는 가장 큰 숫자를 찾아냅니다. 이 공통된 숫자를 $g_n$ 이라고 부르겠습니다.

Khai-Hoan Nguyen-Dang의 논문은 이 공유된 숫자들의 수열( $g_1, g_2, g_3, \dots$ )의 거동에 대한 깊이 있는 조사입니다. 저자는 다음과 같은 질문을 던집니다: 이 공유된 숫자들에는 단순하고 예측 가능한 패턴이 존재하는가?

다음은 이 논문의 발견을 쉬운 비유를 사용하여 정리한 내용입니다:

1. 두 종류의 기계

저자는 기계의 동작 방식이 그 시작 설정값인 $a$ 와 $b$ 사이의 관계에 전적으로 달려 있다는 것을 발견했습니다.

"의존적인" 기계 (예측 가능함):
만약 $a$ 와 $b$ 가 "곱셈적으로 의존적(multiplicatively dependent)"이라면, 이는 한 숫자가 다른 숫자의 거듭제곱이라는 의미입니다 (예를 들어, $4=2^2$ 이고 $8=2^3$ 이므로 4와 8은 의존적입니다).
- 결과: 기계들이 의존적일 때, 공유된 숫자들의 수열( $g_n$ )은 **선형 점화식(linear recurrence)**이라는 매우 엄격하고 단순한 규칙을 따릅니다.
- 비유: 이것은 마치 행진하는 악단이 노래를 연주하는 것과 같습니다. 만약 드럼과 트럼펫이 완벽하게 동기화되어 있다면(의존적이라면), 그들의 결합된 리듬은 예측 가능한 단순하고 반복적인 비트를 따르게 됩니다. 이 논문은 만약 수열이 이 단순한 비트를 따른다면, 기계들은 반드시 의존적이어야 함을 증명합니다.
"독립적인" 기계 (혼돈스러움):
만약 $a$ 와 $b$ 가 "곱셈적으로 독립적"(2와 3처럼 서로의 거듭제곱이 아닌 경우)이라면, 이들은 완전히 다른 노래를 연주하는 두 명의 음악가와 같습니다.
- 결과: 이 경우, 공유된 숫자들의 수열( $g_n$ )은 어떤 단순하고 일정한 규칙으로도 예측할 수 없습니다. 너무나 혼돈스럽기 때문입니다.
- 비유: 만약 당신이 두 음악가가 각자 독립적인 노래를 연주하고 있는데도 행진하는 악단이 단순한 비트를 따르도록 강요하려 한다면, 그 체계는 무너집니다. 이 논문은 당신이 이 숫자들에 어떤 단순한 규칙을 맞추려고 노력하더라도, 그것은 결국 실패할 것임을 증명합니다.

2. "유령" 패턴

저자는 더 깊은 질문을 던집니다. 설령 전체 수열이 혼돈스럽더라도, 그 안에 예측 가능한 "부분"이 존재할 수 있을까요? 구체적으로, 두 기계의 출력값을 모두 나누면서 단순한 규칙을 따르는 더 작은 수열이 존재할 수 있을까요?

발견: 만약 기계들이 독립적이라면, 그 작은 수열이 그저 지루하게 반복되는 루프(periodic)가 아닌 이상 답은 **"아니오"**입니다.
비유: 두 음악가가 만드는 혼돈스러운 소음 속에서 숨겨진 리듬을 찾으려고 노력한다고 상상해 보세요. 이 논문은 당신이 찾을 수 있는 유일한 "리듬"은 그저 계속해서 반복되는 단순하고 짧은 루프뿐이라는 것을 증명합니다. 여기에는 복잡하고 장기적인 숨겨진 패턴은 존재하지 않습니다.

3. "나쁜" 지점의 매핑

논문은 그다음으로 $g_n$ 이 1보다 큰 경우(즉, 두 기계가 공통 인자를 실제로 공유하는 경우)를 정밀하게 들여다봅니다.

"나쁜 집합(Bad Set)": 저자는 두 기계가 인자를 공유하는 모든 숫자 $n$ 의 지도를 만듭니다.
비유: 달력을 상상해 보세요. 대부분의 날에 기계들은 서로 공통점이 없는 숫자를 만들어냅니다. 하지만 특정 날에는 그들은 비밀을 공유합니다. 논문은 이 비밀이 발생하는 정확한 날을 가리키는 "화살표"를 달력에 그리는 공식적인 방법을 제공합니다.
- 알고 보니 이 "비밀스러운 날들"은 특정한 반복 일정(등차수열)들의 모임이었습니다.
- 만약 기계들을 첫째 날에 비밀을 공유하지 않도록 규격화한다면, 이 논문은 "나쁜 날들"이 정확히 특정 소수들의 일정에 해당하는 날들이라는 것을 보여줍니다.

4. "Ailon–Rudnick" 미스터리

마지막으로, 이 논문은 Ailon–Rudnick 추측이라 불리는 유명한 미해결 난제에 도전합니다.

퍼즐: 만약 기계들이 독립적이고 첫째 날에 비밀을 공유하지 않는다면, 언젠가는 (무한히 많은 날 동안) 공통 인자가 전혀 없는 숫자들( $g_n = 1$ )을 만들어낼까요?
논문의 기여: 저자는 이 퍼즐 전체를 해결하는 대신, 이를 작고 관리 가능한 조각들로 나눕니다. 저자는 이 문제를 해결하기 위해서는 특정 유형의 "나쁜 날들"(예: 소수)을 확인하고, 특정 대수적 "지문"(결과식, resultants)을 살펴봐야 한다는 것을 보여줍니다.
비유: 달력이 대체로 비밀이 없는 상태임을 증명하려는 대신, 저자는 이렇게 말합니다. "자, 화요일만 봅시다. 만약 우리가 화요일에 비밀이 없다는 것을 증명할 수 있다면, 우리는 엄청난 진전을 이룬 것입니다." 저자는 이 미스터리를 해결할 수 있는 조건들의 체크리스트를 제공합니다.

요약

요컨대, 이 논문은 두 지수 수열 사이의 공유된 인자의 리듬에 대한 엄밀한 조사입니다.

기저(bases)가 연관되어 있다면: 리듬은 단순하고 예측 가능합니다.
기저가 연관되어 있지 않다면: 리듬은 혼돈스러우며, (지루한 루프를 제외한) 어떠한 숨겨진 단순한 패턴도 존재하지 않습니다.
"나쁜" 날들: 저자는 공유된 인자가 발생하는 시점을 정확히 매핑하여, 막연한 미스터리를 정밀한 반복 일정의 목록으로 바꿉니다.
거대한 추측: 이 논문은 수학자들이 이 기계들이 언제 비밀 공유를 멈출지 마침내 증명할 수 있도록 돕는 더 날카롭고 정교한 도구들을 제공합니다.

기술 요약: 수열 $\gcd(a^n - 1, b^n - 1)$ 에 관하여

문제 정의

본 논문은 정수 $a, b \ge 2$ 에 대하여 $g_n := \gcd(a^n - 1, b^n - 1)$ 로 정의되는 수열 $(g_n)_{n \ge 1}$ 의 산술적 구조를 조사한다. 이 수열은 지수 수열의 최대공약수와 나누기 수열(divisibility sequences) 이론이라는 두 고전적 영역의 교차점에 위치한다.

중심적인 동기는 정수 집합에서의 Ailon–Rudnick 추측에서 기인한다. Ailon과 Rudnick은 함수체(function-field) 환경에서 $f, g \in \mathbb{C}[T]$ 가 곱셈적으로 독립(multiplicatively independent)이면 $\gcd(f^n - 1, g^n - 1)$ 이 다항식에 의해 유계임을 증명했으나, 정수 환경에서의 문제는 여전히 미해결 상태이다. 이 추측은 $a$ 와 $b$ 가 곱셈적으로 독립이고 $\gcd(a-1, b-1)=1$ 이면, 무수히 많은 $n$ 에 대해 $\gcd(a^n - 1, b^n - 1) = 1$ 이라고 상정한다.

본 논문의 목적은 상수 계수 선형 점화식(constant-coefficient linear recurrences) 및 **선형 나누기 수열(linear divisibility sequences, LDS)**의 프레임워크를 사용하여 $(g_n)$ 에 대해 무엇을 설명할 수 있고 무엇을 설명할 수 없는지를 명확히 규정하는 것이다.

방법론

저자는 대수적 수론, 해석적 유계값, 그리고 구조적 분류 정리의 조합을 활용한다:

선형 점화식의 경직성(Rigidity): 저자는 모든 공액(conjugate)이 닫힌 단위 원판 내에 있는 대수적 정수는 1의 거듭제곱근(root of unity)이라는 고전적 원리(Kronecker의 보조정리)를 이용한다. 이는 선형 점화식의 생성 함수에 적용되어, 아지스(subexponential) 성장을 보이는 수열은 결국 산술 진행(arithmetic progressions) 상에서 다항식이 되어야 함을 보여준다.
아지스 유계값(Subexponential Bounds): 근본적인 양적 입력값은 $a, b$ 가 곱셈적으로 독립일 때 $\log \gcd(a^n - 1, b^n - 1) \le \epsilon n + O_\epsilon(1)$ 임을 확립한 Bugeaud, Corvaja, Zannier의 정리이다.
LDS의 분류: 본 연구는 정수 선형 나누기 수열에 대한 Granville의 최근 분류에 크게 의존하며, 이는 해당 수열을 주기적(periodic), 거듭제곱(power), 그리고 다항식 생성(polynomially generated) 성분으로 분해한다.
국소 산술(LTE): 저자는 $p$ -진 가치(p-adic valuation)의 정확한 식을 도출하기 위해 LTE(Lifting The Exponent) 보조정리를 사용한다.
원분 결과식(Cyclotomic Resultants): 소수 인덱스에 대한 Ailon–Rudrick 추측을 다루기 위해, 저자는 원분 다항식과 결과식(resultant)의 성질을 이용하여 문제를 유한한 증명서(finite certificates)와 국소 피복(local covering) 문제로 환원한다.

주요 기여 및 결과

1. GCD 수열의 선형 점화식으로서의 분류

본 논문은 $(g_n)$ 이 상수 계수 선형 점화식을 만족하는지에 관한 날카로운 경직성 정리를 확립한다.

정리 1.1: 수열 $(g_n)$ $(g_{n})$ 이 상수 계수 선형 점화식을 만족할 필요충분조건은 $a$ $a$ 와 $b$ $b$ 가 **곱셈적으로 의존적(multiplicatively dependent)**인 것이다.
- 의존적인 경우, $a=c^r, b=c^s$ 를 만족하는 정수 $c \ge 2$ 와 $r, s \ge 1$ 이 존재한다. 이 경우 $g_n = c^{\gcd(r,s)n} - 1$ 이며, 이는 단순한 선형 점화식이다.
- 독립적인 경우, 수열의 어떤 꼬리(tail)도 선형 점화식을 만족하지 않는다.
따름정리 3.4: 결과적으로, $(g_n)$ 이 **선형 나누기 수열(LDS)**일 필요충분조건은 $a$ 와 $b$ 가 곱셈적으로 의존적인 것이다.

2. 공통 LDS 인자의 경직성

본 논문은 $a$ 와 $b$ 가 곱셈적으로 독립인 경우, 어떤 비자명한 선형 나누기 수열이 $a^n - 1$ 과 $b^n - 1$ 을 동시에 나눌 수 있는지 조사한다.

정리 1.2 / 정리 4.3: $a$ $a$ 와 $b$ $b$ 가 곱셈적으로 독립이면, $W_n \mid a^n - 1$ $W_{n} ∣ a^{n} - 1$ 및 $W_n \mid b^n - 1$ $W_{n} ∣ b^{n} - 1$ 을 만족하는 모든 정수 선형 나누기 수열 $(W_n)$ $(W_{n})$ 은 **주기적(periodic)**이다.
- 이 결과는 Bugeaud–Corvaja–Zannier의 유계값(아지스 성장)과 Granville의 LDS 분류를 결합한 것이다. 이는 "선형 점화식" 메커니즘이 독립적인 경우의 비자명한 공통 인자를 설명할 수 없음을 의미하며, 그러한 공통 인자는 반드시 주기적이어야 함을 시사한다.

3. 국소 구조 및 지지 집합 공식

본 논문은 $g_n$ 의 지지 집합(support)과 가치(valuation)에 대한 정확한 식을 제공하여, "나쁜 집합(bad set)" $\{n : g_n > 1\}$ 을 식별한다.

지지 집합 공식 (명제 5.1): 소수 $p \nmid ab$ 에 대하여, $L_p = \text{lcm}(\text{ord}_p(a), \text{ord}_p(b))$ 라 하면, $p \mid g_n \iff L_p \mid n$ 이다.
가치 공식 (명제 5.2): 홀수인 소수 $p \nmid ab$ 에 대하여, 만약 $L_p \mid n$ 이면, $v_p(g_n) = c_p + v_p(n)$ 이다. 여기서 $c_p = \min(v_p(a^{L_p}-1), v_p(b^{L_p}-1))$ 이다.
나쁜 집합 특성 (따름정리 5.4): $\gcd(a-1, b-1)=1$ 이라는 정규화 조건 하에서, 집합 $\{n : g_n > 1\}$ 은 정확히 다음과 같은 산술 진행의 합집합이다:
$\{n \ge 1 : g_n > 1\} = \bigcup_{p \nmid ab} L_p \mathbb{N}$
따라서 Ailon–Rudnick 추측은 이 합집합의 여집합이 무한하다는 것과 동치이다.

4. Ailon–Rudrick 추측을 향한 환원

본 논문은 선형 점화식 메커니즘을 배제하고, 추측의 난점을 국소 피복 문제로 격리하는 여러 구조적 환원을 도출한다.

원시 지지 기준 (명제 5.6): 나쁜 집합은 최소 주기 $L_p$ 를 갖는 원시 집합 $B$ 에 의해 생성되는 진행들의 합집합으로 압축될 수 있다. 만약 $\sum_{d \in B} 1/d < \infty$ 이면, 좋은 집합(good set)은 양의 하한 밀도(lower asymptotic density)를 갖는다.
소수 인덱스 환원 (정리 6.2): 유한한 예외 집합 $\Sigma(a,b)$ 밖의 소수 $\ell$ 에 대하여, $g_\ell > 1$ 인 것은 $A_\ell = \frac{a^\ell-1}{a-1}$ 와 $B_\ell = \frac{b^\ell-1}{b-1}$ 이 공통의 원시 약수(primitive divisor)를 공유할 때(즉, $\text{ord}_p(a) = \text{ord}_p(b) = \ell$ 인 소수 $p$ 가 존재할 때)와 같다.
유한 증명서 (정리 6.4): 만약 $g_\ell > 1$ 이면, $1 \le u, v \le \lceil \sqrt{\ell} \rceil$ 인 정수 $u, v$ 와 $p \equiv 1 \pmod \ell$ 인 소수 $p$ 가 존재하여 $p \mid a^u - b^v$ 또는 $p \mid a^u b^v - 1$ 을 만족한다.
결과식 압축 (따름정리 6.6): $g_\ell > 1$ 조건은 $p \equiv 1 \pmod \ell$ 인 소수 $p$ 가 원분 결과식 $R_\ell(b-a) = \text{Res}_X(\Phi_\ell(X), \Phi_\ell(X + b-a))$ 를 나눈다는 것을 함의한다.

의의 및 주장

본 논문은 선형 점화식 및 나누기 수열의 맥락 내에서 수열 $(g_n)$ 에 대한 결정적인 구조적 분석을 제공한다고 주장한다.

선형 메커니즘의 제거: 주요 의의는 $(g_n)$ 이 (의존적이지 않은 한) 선형 나누기 수열이 아니며, 독립적인 경우 어떠한 비주기적 선형 나누기 수열도 공통 인자로 작용할 수 없음을 증명한 데 있다. 이는 $(g_n)$ 을 선형 점화식으로 모델링함으로써 Ailon–Rudnick 추측을 해결할 수 없음을 시사한다.
난점의 국소화: 정확한 국소 식과 환원을 확립함으로써, 저자는 추측의 남은 어려움이 선형 점화식 현상이 아니라, 곱셈적 차수(multiplicative orders)와 소수 인덱스 장애물에 의해 지배되는 국소 피복 문제임을 주장한다.
정확한 특성화: 본 논문은 일반적인 경우에 대한 최초의 정확한 지지 집합 및 가치 공식을 제공하며, 나쁜 집합을 국소 주기 $L_p$ 에 의해 결정되는 명시적인 산술 진행의 합집합으로 식별한다.

저자는 "선형 점화식 메커니즘"은 완전히 이해되었고 제거되었으며, 이제 문제는 국소 주기들의 집합 $\{L_p\}$ 의 밀도와 피복 성질을 분석하는 것으로 귀결된다고 결론짓는다.