모듈러 역원 (Modular Multiplicative Inverse)

shjk·2025년 5월 26일

1. 정의

모듈러 역원(modular multiplicative inverse)이란, 두 정수 $a$ 와 $m$ 에 대하여 다음 식을 만족하는 정수 $a^{-1}$ 을 말한다.

a \cdot a^{-1} \equiv 1 \pmod{m}

즉, $a \cdot a^{-1}$ 을 $m$ 으로 나누었을 때 나머지가 1이 되도록 하는 정수 $a^{-1}$ 을 의미한다.

여기서 정수 $a^{-1}$ 은 흔히 $a$ 의 모듈러 역원이라고 부른다.

2. 존재 조건

정수 $a$ 의 모듈러 역원 $a^{-1}$ 이 존재하려면, 다음과 같은 조건이 반드시 성립해야 한다.

\gcd(a, m) = 1

즉, $a$ 와 $m$ 이 서로소(coprime)일 때만 모듈러 역원이 존재한다.

이유:

$\gcd(a,m)=1$ 일 때, 베주 항등식(Bézout’s Identity)에 따라 정수 $x, y$ 가 존재하여
$ax + my = 1$
를 만족하므로, 양변을 모듈러 연산하면
$ax \equiv 1 \pmod{m}$
이 되어, $x$ 가 $a$ 의 모듈러 역원이 된다.

3. 계산 방법

(1) 확장 유클리드 알고리즘 (Extended Euclidean Algorithm)

모듈러 역원을 찾는 대표적인 방법은 확장 유클리드 알고리즘을 사용하는 것이다.

알고리즘의 과정:

두 정수 $a$ , $m$ 에 대하여 확장 유클리드 알고리즘을 이용해 다음을 만족하는 $x, y$ 를 찾는다.

ax + my = \gcd(a, m) = 1

이때의 $x$ 값을 $m$ 으로 나눈 나머지가 바로 모듈러 역원이다.

예제

$a=3$ , $m=11$ 일 때 모듈러 역원을 찾는다.

확장 유클리드 알고리즘을 적용하면:

$11 = 3 \times 3 + 2$
$3 = 2 \times 1 + 1$
$2 = 1 \times 2 + 0$

역으로 올라가면서 $1$ 을 표현하면,

$1 = 3 - 2 \times 1$
$1 = 3 - (11 - 3 \times 3) \times 1 = 4 \times 3 - 1 \times 11$

따라서

4 \cdot 3 \equiv 1 \pmod{11}

즉, 모듈러 역원은 $4$ 이다.

(2) 페르마의 소정리 (Fermat’s Little Theorem)

모듈러 연산의 나눗셈에서 나누는 수가 소수 $p$ 일 때 페르마의 소정리를 이용하여 모듈러 역원을 간단히 계산할 수 있다.

페르마의 소정리:

만약 소수 $p$ 와 서로소인 정수 $a$ 가 주어지면 다음이 성립한다.

a^{p-1} \equiv 1 \pmod{p}

이를 활용하면,

a^{p-2} \equiv a^{-1} \pmod{p}

를 얻을 수 있다.

예제:

$a=3$ , 소수 $p=11$ 일 때 모듈러 역원은

3^{11-2} = 3^9 \equiv 4 \pmod{11}

을 통해 쉽게 구할 수 있다.

4. 활용 예시 (프로그래밍에서의 적용)

컴퓨터공학적으로 큰 수의 나눗셈 연산은 직접 나누지 않고 모듈러 역원을 이용해 곱셈으로 변경하는 것이 연산 속도를 높일 수 있다.

예를 들어, 큰 수의 이항 계수(mod 연산 포함)를 구할 때 모듈러 역원을 활용한 다음 식이 널리 사용된다.

{n \choose k} \equiv \frac{n!}{k!(n-k)!} \equiv n! \cdot (k!)^{-1} \cdot ((n-k)!)^{-1} \pmod{m}

이 식에서 $(k!)^{-1}$ 와 $((n-k)!)^{-1}$ 는 모듈러 역원이다.

5. 파이썬 예제 코드

다음은 파이썬으로 확장 유클리드 알고리즘을 구현한 모듈러 역원 계산 예시이다.

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        gcd, x1, y1 = extended_gcd(b, a % b)
        x, y = y1, x1 - (a // b) * y1
        return gcd, x, y

def mod_inverse(a, m):
    gcd, x, _ = extended_gcd(a, m)
    if gcd != 1:
        raise ValueError("모듈러 역원이 존재하지 않습니다.")
    else:
        return x % m

# 예시: 3의 mod 11에 대한 역원 계산
print(mod_inverse(3, 11)) # 출력: 4