나머지 연산이란?
와 같이 a를 b로 나눈 나머지인 r을 얻기 위한 연산을 의미하며, 연산은 혹은 로 표현한다.
기본적으로 나머지 연산은 덧셈, 뺄셈, 곱셈에 대해 분배법칙이 성립하여 아래와 같은 식이 성립한다.
하지만, 나눗셈은 분배법칙이 성립하지 않는다.
이런 현상이 발생하는 이유는 나머지연산은 정수에 닫혀있지만,
나눗셈은 정수를 넘어서 실수에 닫혀있는 연산이기 때문이다.
그렇다면 나눗셈과 나머지 연산이 결합하면 방법이 없는 것일까?
결론적으로 말하면 아니다. 단지 형태가 우리가 생각하는 결합법칙과는 조금 다를 뿐 풀 수 있는 방법이 존재한다.
그럼 위의 식을 어떻게 전개할 수 있을까?
일단 나눗셈은 바로 전개가 되지 않는다고 했으니,
전개가 되는 연산인 곱셈으로 바꿔 생각해보자.
그럼 위의 식을 아래와 같이 바꿀 수 있다.
이처럼 곱셈에 대해서 분배법칙을 적용할 수 있고, 에 대해서만 해결할 수 있다면 문제의 해답을 찾을 수 있다.
은 곱셈의 역원으로 볼 수 있기 때문에 앞으로는 나눗셈을 구한다기보다는 나눗셈이 곱셈의 역원이라는 관점에서 문제를 풀어나가도록 한다.
나머지 연산에 대한 곱셈의 역원 구하기
나머지 연산에 대한 곱셈의 역원을 구하는 방법은 아래 2가지가 존재한다.
- 페르마의 소정리 (Fermat’s Little Theorem)
- 확장 유클리드 호제법 (Extended Euclidean Algorithm)
여기서는 그 두가지 방법을 이용하여 곱셈의 역원을 구하는 방법과 이에 대한 증명을 하고자 한다.
페르마의 소정리 (Fermat’s Little Theorem)
페르마의 소정리는 a이 소수 p로 나눠떨어지지 않을 경우 항상 아래식을 만족한다는 것이다.
단, a와 p는 서로소이어야 한다
이 수식의 양변에 을 곱하면 다음과 같은 결과가 얻어지고,
이를 이용하여 우리가 원하던 나머지 연산에 대한 나눗셈은 아래와 같은 형태로 전개할 수 있다.
단, b와 M는 서로소이어야 한다
페르마의 소정리 증명
페르마의 소정리의 증명은 그렇게 어렵지 않다.
소수 p에 대해 아래와 같은 두 종류의 집합을 생각해보자.
단, a와 p는 서로소이어야 한다
위의 수식에서 확인할 수 있는 것처럼 A 집합은 소수 p 보다 작은 수들로 이루어져 있기 때문에 나머지 연산을 적용하더라도 집합의 원소는 달라지지 않는다.
그럼 A 집합에 p와 서로소인 정수 a를 곱한 집합 B는 어떨까?
와 는 서로소이기 때문에 서로 나눠떨어지지 않는다는
것에 초점을 맞춰 생각해보면 쉽게 알 수 있다.
만약 쉽게 납득이 가지 않는다면 2개의 수직선을 상상해보자.
는 간격으로 위치에 눈금이 있는 직선이고,
는 간격으로 위치에 눈금이 있는 직선이다.
그 두 직선을 겹쳐보면 와 는 서로소이기 때문에
처음과 마지막 눈금을 빼면 겹치는 눈금이 없고,
각 직선에 표시된 눈금의 개수는 상대방 직선의 간격만큼인 것을 알 수 있다.
두 직선의 마지막 눈금은 모두 로 가 개
혹은 가 개 있다고 해석할 수 있기 때문이다.
이제 을 의 간격으로 접어보면 에
직선의 눈금이 위치한 것을 알 수 있다.
따라서 이를 수식으로 정리하면 아래와 같다.
이제 위의 집합에 대한 증명을 이용해서 페르마의 소정리를 증명해보자
위의 두 집합 와 에 에 대한 나머지 연산을 적용하면 집합원소가 같아지기 때문에,
내부 집합원소를 모두 곱한 경우도 나머지 연산을 적용하면 같은 값을 얻을 수 있다는 것을 쉽게 알 수 있다.
따라서, 이를 이용하면 아래 수식이 성립함을 알 수 있다.
확장 유클리드 호제법 (Extended Euclidean Algorithm)
많은 사람들이 Euclidean Algorithm은 익숙할 것이다. 적어도 전산학을 전공한 사람이라면, 최대공약수(GCD)를 구하는 프로그램을 한번쯤은 만들어봤을 것이고, 이 때 빼놓을 수 없는 것이 Euclidean Algorithm이다.
이름에서 알 수 있듯이 Extended Euclidean Algorithm은 를 구하는 Euclidean Algorithm의 확장된 개념으로, 모든 정수에 대해서 아래 식을 만족하는 수가 존재하고, 이 때 와 를 구할 수 있다는 것이 알고리즘의 핵심이다.
Euclidean Algorithm에서 Extended Euclidean Algorithm을 증명해가는 과정은 첨부파일을 확인하면 쉽게 알 수 있기 때문에 여기서는 Extended Euclidean Algorithm을 이용해서 나머지 연산에 대한 곱셈의 역원을 구하는 것에 집중한다. Extended Euclidean Algorithm에 대한 증명이 궁금하다면 Extended Euclidean Algorithm Prove[1] 를 참조하면 쉽게 이해할 수 있다.
그럼 이제 증명을 시작해보자.
우리가 알고 싶은 것은 나머지 연산에서 곱셈에 대한 역원이다.
즉, 곱셈 연산을 통해 항등원인 1을 만드는 방법을 알고 싶은 것이고,
a에 대해 아래식을 만족하는 x를 찾으려는 것이다.
그럼 이제 Extended Euclidean Algrithm을 이용하여 위의 식을 유도해보자.
먼저 Extended Euclidean Algorithm의 기본식을 조금만 변형하면 아래와 같은 식을 얻을 수 있다.
이 식의 양변에 M에 대한 나머지 연산을 적용해보자.
단, a와 M은 서로소이어야 한다
이 때, a과 M가 서로소의 관계라면, 즉 이라면, 우리가 유도하고자 했던 식이 완성된다.
따라서 나머지 연산에 대한 곱셈의 역원은 일 때, Extende Euclidean Algorithm의 해법으로 구할 수 있고, 그 해법은 아래와 같다.
def xgcd(a, b):
if b == 0:
return [1, 0, a]
x, y, d = xgcd(b, a % b)
return [y, x - (a // b) * y, d]
def inv(a, M):
x, y, d = xgcd(a, M)
return x