정수론과 나눇셈 (Divisibility)

수학, 특히 수론에서 정수 $a$가 정수 $d$로 나누어 떨어질 때, 이를 '$a$는 $d$에 의해 정수배수 관계에 있다'고 표현하며, 기호로는 $d | a$로 표기합니다. 이는 나머지 없이 정확히 나뉘어진다는 뜻입니다.

나누떨어짐의 기본 속성들은 다음과 같습니다:

• 만약 $d | a$이면, 임의의 정수 $k$에 대하여 $d | ka$가 성립합니다.
• 만약 $d | a$이고 동시에 $d | b$라면, $d$는 두 수의 합차식 $a \pm b$도 반드시 가감할 수 있습니다.
• 만약 두 자연수 $a, b$가 서로 상대방을 인수분해할 때 ($b|a$ 및 $a|b$), 그리고 부호가 같다면 $a = b$이거나 절대값이 일치함을 의미합니다.

약수와 배수의 개념

음수가 아닌 정수 $a$에 대해, $d > 0$이고 $d|a$를 만족할 때 $d$를 $a$의 약수(Divisor)라고 명명합니다. 예를 들어, 20 의 약수는 1, 2, 4, 5, 10, 20 으로 나열할 수 있으며, 약수의 범위는 일반적으로 1부터 $|a|$까지 존재합니다.

또한, $d|a$인 경우 $a$를 $d$의 부수(Multiple)이라고 칭하며, 수학적으로 $a = kd$ (여기서 $k$는 어떤 정수)와 같이 나타낼 수 있습니다.

최대공약수 (GCD)

두 정수 $a$와 $b$를 동시에 나눌 수 있는 수를 공약수라고 합니다. 이 중 가장 큰 값을 최대공약수 (Greatest Common Divisor) 라고 정의하며, 보통 $\gcd(a, b)$로 표기합니다. 대표적인 예로 $\gcd(15, 20) = 5$, $\gcd(1, 20) = 1$, $\gcd(0, 20) = 20$이 됩니다. 단, 두 수 모두 0 인 $\gcd(0, 0)$은 정의상 0 으로 간주됩니다.

알고리즘적 관점에서 유용한 GCD 의 성질들:

1. $\gcd(a, ka) = |a|$
2. $\gcd(an, bn) = n \times \gcd(a, b)$
3. $\gcd(a, b) = \gcd(b, a \mod b)$ (유유희법/제올게니드 알고리즘의 근간)

특히 마지막 식 $\gcd(a, b) = \gcd(b, r)$ 은 유클리드 호제법 (Euclidean Algorithm) 의 원리를 설명하며, 이를 통해 큰 수의 공약수를 빠르게 구할 수 있습니다.

최소공배수 (LCM)

두 수 $a, b$ 의 공 bội수는 둘 다 배수가 되는 수이며, 그 중 가장 작은 양의 정수를 최소공배수 (Least Common Multiple) 라고 합니다. 표기법은 $\operatorname{lcm}(a, b)$ 를 사용합니다.

GCD 와 밀접한 관련이 있어 $\operatorname{lcm}(a, b) = \frac{a \times b}{\gcd(a, b)}$ 라는 공식이 성립합니다.

알고리즘 구현 사례

실무 및 문제 해결 시 가장 많이 사용되는 접근 방식은 유클리드 호제법을 이용한 GCD 계산 후, 이를 역이용하여 LCM 을 도출하는 것입니다. 또한 큰 수의 거듭제곱剰餘 연산을 위한 이진승법도 포함합니다.

1. 최대공약수 (재귀 구조 변경 및 변수명 수정)

// 유클리드 호제법을 기반으로 한 반복문 기반 구현
long long computeGCD(long long numA, long long numB) {
    while (numB != 0) {
        long long remainder = numA % numB; // 나머 저장
        numA = numB;
        numB = remainder;
    }
    return numA >= 0 ? numA : -numA; // 절댓값 보장
}

2. 최소공배수 유도

// 두 수의 곱을 최대공약수로 나누어 계산
long long computeLCM(long long u, long long v) {
    if (u == 0 || v == 0) return 0;
    return std::abs(u) / computeGCD(u, v) * std::abs(v); // tràn số tránh bằng cách chia trước
}

3. 모듈러 급수 지수함수 (Modular Exponentiation)

/*
 * 목적: (base ^ power) % modulus 계산을 O(log power) 시간 복잡도로 수행
 * 입력 base: 밑, exp: 지수, mod: 나머지 기준
 */
long long binPow(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod; 
    while (exp > 0) {
        if (exp & 1) { // 홀수 차수일 때마다 결과 축적
            res = (__int128)res * base % mod; // overflow 방지 위해 casting
        }
        base = (__int128)base * base % mod; // 제곱 과정에서도 modulo 적용
        exp >>= 1; // 2 로 나눔 (하프시프트)
    }
    return res;
}