Lifting The Exponent (LTE) Lemma

정의

Lifting The Exponent (LTE) 는 소수 p에 대해 v_p(a^n - b^n) 또는 v_p(a^n + b^n) 을 계산하는 정리. v_p(x)는 x의 p-진 값 (p로 나누어떨어지는 횟수).

1640년 페르마가 처음 사용했고, 현대 형태는 정수론 올림피아드에서 필수 도구.

문제 상황과 동기

큰 a^n - b^n에서 소수 p가 몇 번이나 나누는지 직접 계산: a^n은 지수 크기로 직접 계산 불가.

• naive: a^n - b^n을 직접 계산. a=4, b=1, n=9에 대해 4^9 - 1 = 262143. p=3으로 나누기: 262143/3 = 87381, 87381/3 = 29127, 29127/3 = 9709. v_3 = 3.
• LTE: v_3(4-1) = v_3(3) = 1, v_3(9) = 2. 합: 1+2 = 3. O(log n).

핵심 통찰: a^n - b^n의 p-진 값을 a-b의 p-진 값과 n의 p-진 값으로 분해.

시각화

핵심 아이디어

Case 1: p가 홀수, p | a-b, p ∤ a, p ∤ b

v_p(a^n - b^n) = v_p(a - b) + v_p(n)

증명 스케치: 수학적 귀납법으로 v_p(a^p - b^p) = v_p(a - b) + 1을 보이고, 일반 n에 대해 인수분해와 반복 적용.

Case 2: p = 2, 2 | a-b, a, b 홀수

v_2(a^n - b^n) = v_2(a - b) + v_2(a + b) + v_2(n) - 1   (n >= 1)

Case 3: p | a+b (a^n + b^n, n 홀수)

v_p(a^n + b^n) = v_p(a + b) + v_p(n)    (p 홀수, p | a+b, p ∤ a, p ∤ b)

핵심 공식

알고리즘

// p-진 값 계산
v_p(x):
    cnt = 0
    while x % p == 0:
        cnt += 1
        x //= p
    return cnt

// LTE main
lte(p, a, b, n):
    if p == 2 and (a - b) % 2 == 0 and a % 2 == 1 and b % 2 == 1:
        return v_2(a - b) + v_2(a + b) + v_2(n) - 1
    if (a - b) % p == 0 and a % p != 0 and b % p != 0:
        return v_p(a - b) + v_p(n)
    if n % 2 == 1 and (a + b) % p == 0 and a % p != 0 and b % p != 0:
        return v_p(a + b) + v_p(n)
    // fallback: 직접 계산 (a^n - b^n) mod p^k
    return v_p(pow(a, n) - pow(b, n))

구현

// Lifting The Exponent Lemma
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
​
int vp(ll x, int p) {
  int cnt = 0;
  while (x % p == 0) { cnt++; x /= p; }
  return cnt;
}
​
ll modpow(ll a, ll n, ll mod) {
  ll r = 1;
  while (n) {
      if (n & 1) r = r * a % mod;
      a = a * a % mod;
      n >>= 1;
  }
  return r;
}
​
int lte(int p, ll a, ll b, ll n) {
  if ((a - b) % p != 0) {
      if (n % 2 == 1 && (a + b) % p == 0 && a % p != 0 && b % p != 0)
          return vp(a + b, p) + vp(n, p);
      return 0;
  }
  if (a % p == 0 || b % p == 0) return 0;
  if (p == 2) {
      if (a % 2 == 0 || b % 2 == 0) return 0;
      return vp(a - b, 2) + vp(a + b, 2) + vp(n, 2) - 1;
  }
  return vp(a - b, p) + vp(n, p);
}
​
int main() {
  int p; ll a, b, n;
  cin >> p >> a >> b >> n;
  int ans = lte(p, a, b, n);
  cout << ans << "\n";
  // verify
  ll mod = 1;
  for (int i = 0; i < ans + 2; i++) mod *= p;
  ll diff = (modpow(a, n, mod) - modpow(b, n, mod) + mod) % mod;
  int act = vp(diff, p);
  cout << "v_p(a^n-b^n) = " << act << "\n";
}

# Lifting The Exponent Lemma
import sys
input = sys.stdin.readline
​
def vp(x, p):
  cnt = 0
  while x % p == 0:
      cnt += 1
      x //= p
  return cnt
​
def modpow(a, n, mod):
  r = 1
  while n:
      if n & 1: r = r * a % mod
      a = a * a % mod
      n >>= 1
  return r
​
def lte(p, a, b, n):
  if (a - b) % p != 0:
      if n % 2 == 1 and (a + b) % p == 0 and a % p != 0 and b % p != 0:
          return vp(a + b, p) + vp(n, p)
      return 0
  if a % p == 0 or b % p == 0:
      return 0  # LTE condition fails
  if p == 2:
      if a % 2 == 0 or b % 2 == 0:
          return 0
      return vp(a - b, 2) + vp(a + b, 2) + vp(n, 2) - 1
  return vp(a - b, p) + vp(n, p)
​
p, a, b, n = map(int, input().split())
ans = lte(p, a, b, n)
print(ans)
# verify
mod = p ** (ans + 2)
diff = (modpow(a, n, mod) - modpow(b, n, mod)) % mod
act = vp(diff, p)
print(f"v_p(a^n-b^n) = {act}")

3 4 1 9

3
v_p(a^n-b^n) = 3

2 5 3 4

3
v_p(a^n-b^n) = 3

복잡도

변형 / 활용

1. a^n + b^n (n 홀수)

p | a+b, p ∤ a, p ∤ b, n 홀수이면 v_p(a^n + b^n) = v_p(a+b) + v_p(n).

2. a^n - b^n where p | a-b but p | a

p가 a나 b를 나누면 조건 불충족. 다른 소인수 분석 필요.

3. 연립 LTE

여러 소인수에 대해 각각 LTE 적용 후 곱. 예: m = product of p_i^(e_i) 에 대해 m | a^n - b^n 조건.

함정

1. p가 a나 b를 나누는 경우

p | a이면 LTE 적용 불가. 직접 계산 또는 다른 소수 분석.

2. p = 2 특수 케이스

p=2에서는 일반 공식과 달라짐. v_2(a+b) 항이 추가로 필요.

3. 부호 반전

a^n - b^n과 b^n - a^n의 v_p는 같음. 단 n이 짝수면 a^n - (-b)^n 주의.

4. n이 p의 배수일 때

v_p(n)이 커질 수 있으므로 v_p(n) 계산에 overflow 주의.

BOJ 연습 문제

참고

• 유클리드 호제법
• 소인수분해
• 모듈러 역원
• 페르마 소정리