모듈로 연산에서 나눗셈을 하는 방법(모듈로 곱셈의 역원 구하기)

1. 합동식에서 기본적으로 알아야하는 성질

 

1-1) 양변에 어떤 정수에 대한 덧셈이나 뺄셈을 하더라도 상관없다. 

 

$a \equiv b (mod p)$이고 $c \equiv d (mod p)$이면, $$a \pm c \equiv b \pm d (mod p)$$

 

그러므로, c = d이면, 양변에 동일한 수를 더하거나 빼더라도 합동식은 변하지 않는다.

 

$$a \pm c \equiv b \pm c (mod p)$$

 

1-2) 양변에 어떤 정수에 대한 곱셈을 하더라도 상관없다

 

$a \equiv b (mod p)$이고 $c \equiv d (mod p)$이면, $$ac \equiv bd (mod p)$$

 

그러므로, c=d이면, 양변에 동일한 수를 곱하더라도 합동식은 변하지 않는다.

 

$$ac \equiv bc (mod p)$$

 

1-3) 덧셈, 뺄셈, 곱셈에 대해 분배법칙이 성립한다.

 

$$(a \pm b) (mod p) = (a mod p \pm b mod p) mod p$$

 

$$(a \times b) (mod p) = (a mod p \times b mod p) mod p$$

 

1-4) 동일한 자연수 거듭제곱을 하더라도 합동식은 변하지 않는다

 

$k$가 자연수이고, $a \equiv b (mod p)$이면, $$a^{k} \equiv b^{k} (mod p)$$ 

 

1-5) 기본적으로 a,b,c,d,k,p는 정수이다. 그러니까 실수에 대해서는 성립하지 않는다

 

곱셈 성질을 양변에 실수를 곱해가지고 왜 안돼? 하지말고, 정수에 대해서만 성립한다는 점을 기억하자

 

 

2. 모듈로 연산의 나눗셈

 

2-1) 일반적으로, 합동식의 양변에 어떤 정수로 나누는 것은 성립하지 않는다.

 

15와 27은 12로 나눈 나머지가 3으로 동일한데,

 

$$15 \equiv 27 (mod 12)$$

 

양변을 3으로 나눠보면.. $$5 \equiv 9 (mod 12)$$로 양변 5,9는 12로 나눈 나머지가 5,9로 서로 달라지니 합동이 아니다.

 

 

2-2) 나눗셈을 어떻게 정의할 수 있을까?

 

양변을 어떤 정수 a로 나눈다는 것은 어떤 정수 a의 곱셈에 대한 역원을 곱한다는 것과 수학적으로 동치이다.

 

곱셈에 대한 역원이란 무엇인가?

 

$$a \times a^{-1} \equiv 1 (mod p)$$를 만족하는 $a^{-1}$를 mod p에 대한 a의 곱셈의 역원이라고 부른다

 

 

2-3) 곱셈의 역원이 존재할 필요충분조건

 

나눗셈은 항상 가능하지는 않다. 일반적인 연산에서도 0으로 나누지는 못하는 것처럼, mod p에 대한 나눗셈도 불가능한 경우가 있다

 

곱셈에 대한 역원 x는 다음 식을 만족한다.

 

$$ax \equiv 1 (mod p)$$

 

이 식은 바꿔말하면, ax를 p로 나눈 나머지가 1이라는 의미이므로,

 

어떤 정수 q에 대하여, $$ax = pq + 1$$을 만족한다는 의미와 같다.

 

---------------------------------------------------------------------------------------------------------------------------------------------------

 

<보조정리> 베주의 항등식(Bézout's Identity)

 

적어도 둘 중 하나는 0이 아닌 정수 a,b에 대하여 a,b의 최대공약수가 gcd(a,b)라고 한다면,

 

1) $$ax + by = gcd(a,b)$$를 만족시키는 정수해 (x,y)는 반드시 존재한다

 

2) 최대공약수 gcd(a,b)는 정수 x,y에 대하여 ax+by로 표현될 수 있는 최소의 자연수이다.

 

3) 정수 x,y에 대하여 ax+by로 표현되는 모든 정수는 최대공약수 gcd(a,b)의 배수이다.

 

증명은 내 수준에서 어려우니 그냥 받아들이기로 한다

 

----------------------------------------------------------------------------------------------------------------------------------------------------

 

$$ax = pq + 1$$은 바꿔쓰면, $$ax-pq = 1$$이다.

 

그러므로 베주의 항등식에 의해, gcd(a,p) = 1을 만족시키는 정수 x,q가 반드시 존재한다.

 

 

역으로 gcd(a,p) = 1이라고 하자.

 

그러면 베주의 항등식에 의해 ay + pz = 1을 만족시키는 정수해 y,z가 반드시 존재한다.

 

그러면, ay = -pz + 1이므로, 어떤 음의 정수 z를 선택하면 a를 p로 나눈 나머지는 1이다.

 

$$ay \equiv 1 (mod p)$$

 

따라서, 어떤 정수 a의 mod p에서 곱셈에 대한 역원이 존재할 필요충분조건은 a와 p가 서로소, 그러니까 a와 p의 최대공약수가 1이다.

 

 

3. 모듈로 곱셈의 역원을 찾는 방법

 

정수 a와 p가 서로소여야 mod p에서 곱셈에 대한 역원이 존재한다는 것은 알았는데, 그러면 어떻게 곱셈에 대한 역원을 찾을 수 있을까?

 

사실 가장 쉬운 방법은 정의 그대로 구현하면 된다.

 

for i in range(1,m):
    
    if (a*i) % m == 1:
        
        a_inverse = i

 

하지만 최악의 경우 m번을 돌아야하니 시간복잡도가 O(m)이다.

 

더 빠르게 구할 수는 없을까?

 

 

3-1) p가 소수인 경우

 

사실 가장 쉬운 경우는 이미 공부했다.

 

p가 소수이고 정수 a와 p가 서로소이면, 페르마의 소정리에 의하여..

 

$$a^{p-1} \equiv 1 (mod p)$$이다.

 

그러면 모듈로 곱셈의 역원의 정의에 의해 식을 다음과 같이 바꿔볼 수 있다

 

$$a \times a^{p-2} \equiv 1 (mod p)$$

 

그러므로 p가 소수일때, a와 p가 서로소라면 a의 모듈로 곱셈에 대한 역원은 $a^{p-2}$와 같다.

 

즉 mod p에 대한 합동식에서 p가 소수인데 a,p가 서로소라면 양변을 정수 a로 나누고 싶을때,

 

양변을 $a^{p-2}$를 곱하면 된다.

 

 

3-2) p가 소수가 아닌 경우

 

소수가 아닌 경우에는 구할 수 없을까?

 

그렇지는 않다. 그런 경우도 사실 이미 공부한 것이나 마찬가지다.

 

곱셈에 대한 역원의 정의에 의하면..

 

$$ax \equiv 1 (mod p)$$인 정수 x를 구하면 된다.

 

그런데, 바꿔말하면 ax를 p로 나눈 나머지가 1이므로 $$ax = pq + 1$$과 같다.

 

그러면 식을 다시 바꿔쓰면 $$ax - pq = 1$$

 

이 식은 확장 유클리드 알고리즘에서 본 것과 완전히 동일하다

 

그래서 a,p에 대한 확장 유클리드 알고리즘으로 정수 x를 구하면 된다.

 

반복문으로 구한 확장 유클리드 알고리즘은 다음과 같다.

 

#반복문

def extended_gcd(a,b):
    
    before_x = 1
    before_y = 0
    
    x = 0
    y = 1
    
    while b != 0:
        
        q,r = a//b, a%b
        
        a,b = b,r
        
        before_x,x = x, before_x - x*q
        before_y,y = y, before_y - y*q
    
    return a,before_x,before_y

 

 

재귀함수로 구하는 확장 유클리드 알고리즘은 다음과 같다.

 

#재귀함수

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

 

여기서 x가 정수 a의 곱셈에 대한 역원이 된다.

 

 

4. 기타

 

4-1) 당연하지만 a의 모듈로 곱셈에 대한 역원은 유일하지 않다. 확장 유클리드 알고리즘으로 구하기 때문에

 

x,y가 p에 대한 a의 모듈로 곱셈에 대한 역원이라고 한다면..

 

$$ax \equiv 1 (mod p)$$

 

$$ay \equiv 1 (mod p)$$

 

두 식을 바꿔 쓰면, $ax = pq_{1} + 1$, $ay = pq_{2} + 1$

 

그러므로, $ax - ay = p(q_{1}-q_{2})$인데, a와 p가 서로소이므로(역원이 존재할 필요충분조건) a는 p로 나누어 떨어지지 않는다.

 

그런데 a(x-y)가 p로 나누어 떨어지므로, (x-y)가 p로 나누어 떨어져야 한다.

 

따라서 $x-y \equiv 0 (mod p)$

 

그러므로, $$x \equiv y (mod p)$$

 

a의 mod p에 대한 곱셈에 대한 역원이 유일하지는 않지만, 그러한 역원들을 p로 나눈 나머지는 항상 유일하다.

 

 

4-2) 다음과 같은 문제는 어떻게 해결할 수 있을까?

 

$$ax \equiv b (mod p)$$

 

1이 정수 b로 바뀐 것 뿐이다.

 

ax를 p로 나눈 나머지가 b이므로, $$ax = pq + b$$로 고칠 수 있고, $$ax - pq = b$$를 만족하는 정수해 x를 찾는 문제와 동일하다.

 

베주 항등식에 의해서, 정수해 b가 a,p의 최대공약수의 배수여야 x,q가 존재한다.

 

최대공약수의 배수가 아니면 해가 존재하지 않는다.

 

그래서, a,p의 최대공약수 g = gcd(a,p)를 찾고, 양변을 g로 나누면 $$(a/g)x - (p/g)q = (b/g)$$

 

----------------------------------------------------------------------------------------------------------------------------------------------

 

<최대공약수의 성질>

 

a,b의 최대공약수가 d = gcd(a,b)라고 한다면, a/d와 b/d의 최대공약수는 1이다.

 

왜냐하면, a = dm, b = dn이라고 하자. 양변을 d로 나누면, a/d = m, b/d = n이므로, gcd(a/d, b/d) = gcd(m,n)

 

m,n의 공약수가 p여서 m = pe, n = pq라고 하자.

 

그러면 a = dpe, b=dpq이다. 여기서 dp는 a,b의 공약수이다.

 

그런데 d는 최대공약수이므로 dp의 최댓값은 d이다. 따라서 p는 1일수밖에 없다. 

 

그러므로 a/d와 b/d의 최대공약수는 1이다.

 

최대공약수로 나누면 두 수가 서로소가 된다는거지?? 신기하네

 

-------------------------------------------------------------------------------------------------------------------------------------------------

 

따라서 확장 유클리드 알고리즘으로 (a/g)x' + (p/g)y' = 1을 만족하는 정수해 (x',y')을 찾는다.

 

그런데 b가 g의 배수이므로, b/g도 정수이고 그래서 x = (b/g)x', y = -(b/g)y'을 선택하면

 

x,y는 ax - py = b의 하나의 해가 된다.

 

예시) $12x \equiv 18 (mod 54)$의 해 x를 찾아보자.

 

12x + 54y = 18을 만족하는 x를 찾으면 된다.

 

gcd(12,54) = 6이므로, 양변을 6으로 나누면 2x + 9y = 3이다.

 

2,9의 최대공약수는 1이므로 2x+9y=1을 만족하는 x,y를 확장 유클리드 알고리즘으로 찾으면.. 예를 들어 

 

x = 5, y = -1을 찾는다.

 

이 값을 3배 해주면, x = 15, y = -3이 2x+9y=3의 해이다.

 

따라서 $x \equiv 15 (mod 54)$가 하나의 해가 된다.

 

 

5. 연습문제

 

14565번: 역원(Inverse) 구하기 (acmicpc.net)

14565번: 역원(Inverse) 구하기

 

 

덧셈의 역원과 곱셈의 역원을 구하는 문제

 

 

6. 풀이

 

덧셈에 대한 역원은 (a+b) mod n = 0이면 b를 a의 덧셈에 대한 역원이라고 정의한다고 한다.

 

그러면 $$a+b = np$$인데, $$b = np - a$$이다. 

 

우변에 n을 더하고 빼보면.. $$b = np - n + n - a = n(p-1) + n-a$$

 

따라서 a의 덧셈에 대한 역원은 $$b \equiv n-a (mod n)$$으로 구할 수 있다.

 

여기서 n-a는 항상 n보다 작으니.. 그 이상의 나머지 연산은 안해도 될것이고

 

-------------------------------------------------------------------------------------------------------------------------------------

 

곱셈에 대한 역원은 확장 유클리드 알고리즘으로 구하는데..

 

gcd = 1이면 존재한다. gcd가 1이 아니면 c = -1이겠지

 

그런데 정수 집합이 0부터 n-1까지라고 제한 조건을 주었다.

 

확장 유클리드 알고리즘으로 c를 구했더니 음수가 나온다면... 이미 배웠던 테크닉을 이용하자

 

$$ac + ny = 1$$에서 좌변에 an을 더하고 빼면..

 

$$ac+an +ny - an = 1$$이므로 $$a(c+n) + n(y-a) = 1$$이다.

 

따라서, c+n,y-a도 정수해가 된다.

 

그러니까 c가 음수라면, c가 양수가 될때까지 n을 더해준다.

 

양수가 되는 순간 반복문을 탈출했는데, n-1보다 크다면 c는 존재하지 않으니 -1이다.

 

from sys import stdin

def extended_gcd(a,b):
    
    before_x = 1
    before_y = 0

    x = 0
    y = 1

    while b != 0:
        
        q,r = a//b, a%b

        a,b = b,r

        before_x,x = x,before_x - x*q
        before_y,y = y,before_y - y*q
    
    return a,before_x,before_y

n,a = map(int,stdin.readline().split())

gcd,c,y = extended_gcd(a,n)

if gcd == 1:
    
    if c < 0:
        
        while c < 0:
            
            c += n
        
    
    if c > n-1:
            
        c = -1

else:
    
    c = -1
    
print(n-a,c)

 

참조

 

 

모듈러 산술(Modular Arithmetic) :: TH (tistory.com)

모듈러 산술(Modular Arithmetic)

 

합동식 - 나무위키 (namu.wiki)

합동식 - 나무위키

 

 

정수론 (4) - 합동식에서의 나눗셈 (tistory.com)

정수론 (4) - 합동식에서의 나눗셈

 

베주 항등식 - 나무위키 (namu.wiki)

베주 항등식 - 나무위키

 

 

abstract algebra - Prove that the multiplicative inverse of $a$ modulo $m$ exists if and only if $a$ and $m$ are coprime. - Mathematics Stack Exchange

Prove that the multiplicative inverse of $a$ modulo $m$ exists if and only if $a$ and $m$ are coprime.

 

2. 유클리드, 확장 유클리드 :: rkm0959 (tistory.com)

2. 유클리드, 확장 유클리드

 

 

Proving that modular inverse only exists when $\gcd(n,x)=1$ - Mathematics Stack Exchange

Proving that modular inverse only exists when $\gcd(n,x)=1$

 

 

최대공약수 - 나무위키 (namu.wiki)

최대공약수 - 나무위키