곱셈 역원

곱셈 역원(乘法逆元, multiplicative inverse)은 어떤 수에 대해 곱했을 때 1이 되는 수를 말한다. 주로 모듈로 연산(modular arithmetic)에서 사용되며, 나눗셈을 곱셈으로 바꾸기 위해 활용된다.

개요

정수 a에 대해 어떤 수 x가 존재해서 다음을 만족하면, x는 a의 곱셈 역원이다.

a * x ≡ 1 (mod m)

여기서 ≡ 기호는 "동치(congruence)"를 의미하며, a * x를 m으로 나눈 나머지가 1과 같다는 뜻이다. 즉,

a * x % m == 1

과 같은 의미이다.

존재 조건

곱셈 역원 x가 존재하려면 다음 조건이 충족되어야 한다.

• a와 m이 서로소여야 한다. 즉, gcd(a, m) = 1이어야 한다.
• 이 조건이 성립할 때만 a의 역원이 (mod m)에서 존재한다.

계산 방법

• 브루트포스 방법

x = 1부터 m-1까지 순차적으로 대입하여 a * x % m == 1이 되는 x를 찾는다.

• 확장 유클리드 알고리즘

a * x + m * y = 1이 되는 정수 x, y를 구하고, x % m을 곱셈 역원으로 사용한다.

• 페르마의 소정리 (m이 소수일 경우)

x = a^(m - 2) % m을 계산하여 곱셈 역원을 구할 수 있다.

예시

• a = 3, m = 7인 경우:

3 * 5 = 15, 15 % 7 = 1 → 5는 3의 곱셈 역원이다.

• a = 4, m = 10인 경우:

gcd(4, 10) = 2 → 서로소가 아니므로 역원이 존재하지 않는다.

활용

• 모듈로 나눗셈 구현
• RSA 암호 알고리즘
• 선형 합동 방정식 해법
• 프로그래밍 대회나 수론 기반 알고리즘 문제 해결

파이썬 구현

# 확장 유클리드 알고리즘을 이용한 곱셈 역원
def modinv(a, m):
    def egcd(a, b):
        if b == 0:
            return (1, 0)
        x1, y1 = egcd(b, a % b)
        x, y = y1, x1 - (a // b) * y1
        return (x, y)

    x, y = egcd(a, m)
    if (a * x + m * y) % m != 1:
        raise ValueError("No modular inverse exists")
    return x % m

# 예시
print(modinv(3, 7))  # 출력: 5

같이 보기

• 모듈로 연산
• 확장 유클리드 알고리즘
• 페르마의 소정리
• RSA 알고리즘

참고 문헌

• Rosen, K. H. (2011). Elementary Number Theory and Its Applications. Pearson.
• Cormen, T. H. et al. (2009). Introduction to Algorithms. MIT Press.