[Discrete Mathematics] 유클리드 호제법(Euclidean algorithm) 및 나머지 연산의 역원

---

유클리드 호제법

 

• 유클리드 호제법

유클리드 호제법은 두 정수의 최대공약수를 찾기 위한 효율적인 알고리즘이다.

$ a $ 가 음이 아닌 정수, $ b $ 가 양의 정수, $ r = a \bmod b $ 라면 $ \gcd(a, b) = \gcd(b, r) $ 이다. 이를 이용하여 $ a $ 에 $ b $ 를, $ b $ 에 $ r $ 을 대입하며 반복하다가 $ r $ 이 $ 0 $ 이 나온다면, $ b $ 가 최대공약수이다.

이는 $ a $ 와 $ b $ 의 공약수의 집합이 $ b $ 와 $ r $ 의 공약수의 집합과 같다는 것을 보임으로써 증명 가능하다.

몫과 나머지 정리에 의해 $ a = bq + r $ $ (0 \leq r < b) $ 를 만족하는 $ q $ 와 $ r $ 이 존재한다. $ c $ 를 $ a $ 와 $ b $ 의 공약수라 하면, $ c \mid bq $ 이다(참고 링크). $ c \mid a $ 이고 $ c \mid bq $ 이므로 $ c \mid a - bq (=r) $ 이다. 따라서 $ c $ 는 $ b $ 와 $ r $ 의 공약수이다. 반대로 $ c $ 가 $ b $ 와 $ r $ 의 공약수이면 $ c \mid bq $ 이고, $ c \mid bq + r (=a) $ 이다. 따라서 $ c $ 는 $ a $ 와 $ b $ 의 공약수이고, 두 공약수의 집합이 같다.

 

• 반복적 유클리드 호제법

입력 : $ a $, $ b $ (단 음이 아니고 동시에 $ 0 $ 이 아님)
출력 : $ \gcd(a, b) $

gcd(a, b) {
    if (a < b) {
        swap(a, b)
    }
    while (b != 0) {
        r = a mod b
        a = b
        b = r
    }
    return a
}

이때 $ 0 < a, b < m (m \geq 8) $ 일 때 나눗셈의 최대 횟수는 $ \log _{\frac{3}{2}} \frac{2}{3}m $ 이다.

 

• 재귀적 유클리드 호제법

입력 : $ a $, $ b $ (단 음이 아니고 동시에 $ 0 $ 이 아님)
출력 : $ \gcd(a, b) $

gcdr(a, b) {
    if (a < b) {
        swap(a, b)
    }
    if (b == 0) {
        return a
    }
    r = a mod b
    return gcdr(b, r)
}

 

---

확장 유클리드 호제법 (Extended Euclidean Algorithm)

 

베주 항등식(Bézout's identity)은 두 정수와 그 두 정수의 최대공약수 간 관계를 보여주는 항등식이다. 내용은 다음과 같다.

$ gcd(a, b) = d $ 라 할 때 $ d = ax + by $ 인 정수 $ x $, $ y $ 가 반드시 존재한다.

$ d $ 는 정수 $ x $, $ y $ 에 대하여 $ ax + by $ 형태로 표현 가능한 가장 작은 자연수다.

정수 $ x $, $ y $ 에 대하여 $ ax + by $ 형태로 표현되는 모든 정수는 $ d $ 의 배수이다.

이를 확장 유클리드 호제법을 이용하여 증명할 수 있다.

$ a > b \geq 0 $ 이 주어지고, $ r_0 = a $, $ r_1 = b $ 라 할 때 $ r_{i+1} $ 는 알고리즘에서 while 반복문이 $ i $ 번 실행된 후의 $ r $ 값이라 하자. 즉 $ r_2 = a \bmod b $ 라 하자.

$ r_n $ 이 처음으로 $ 0 $ 이 된다 가정하면, $ gcd(a,b) = r_{n-1} $ 이다.

따라서 일반적으로 $ r_{i+2} = r_i \bmod r_{i+1} $ 에서 $ r_{i+2} = -q_{i+2} r_{i + 1} + r_i $ 이다.

이때 $ i = n-3 $ 이라면 $ r_{n-1} = -q_{n-1} r_{n-2} + r_{n-3} = y_{n-3} r_{n-2} + x_{n-3} r_{n-3} $ 이다.

$ i = n-4 $ 라면 $ r_{n-2} = -q_{n-2} r_{n-3} + r_{n-4} $ 이다.

즉 $ r_{n-1} = y_{n-3} (-q_{n-2} r_{n-3} + r_{n-4} ) + x_{n-3} r_{n-3} $

$ = \left[ -y_{n-3} q_{n-2} + x_{n-3} \right] r_{n-3} + y_{n-3} r_{n-4} $

$ = y_{n-4} r_{n-3} + x_{n-4} r_{n-4} $ 이다.

이런 방식을 반복하면 다음식이 성립한다.

$ \gcd(r_0, r_1) = r_{n-1} = y_0 r_1 x_0 r_0 = y_0 b + x_0 a = ax + by $

 

• $ x $ 와 $ y $ 계산

입력 : $ a $, $ b $ (단 음이 아니고 동시에 $ 0 $ 이 아님)
출력 : $ \gcd(a, b) $, $ x $, $ y $

EEA(a, b, x, y) {
    if (b == 0) {
        x = 1
        y = 0
        return a
    }
    q = floor(a / b)
    r = a mod b
    g = EEA(b, r, x1, y1)
    x = y1
    y = x1 - y1 * q
    return g
}

 

---

나머지 연산의 역원 (Inverse Modulo Integer)

 

$ n > 0 $, $ m > 1 $ 을 $ \gcd(n, m) = 1 $ 인 정수라 할 때 $ nx \bmod m = 1 $, $ 0 < x < m $ 을 만족하는 정수 $ x $ 를 $ n \bmod m $ 의 역원이라 한다.

확장 유클리드 호제법을 이용하여 $ n x^\prime + m y^\prime = \gcd(n, m) = 1 $ 이 되는 정수 $ x^\prime $ 과 $ y^\prime $ 을 찾울 수 있다. 그러면 $ n x^\prime = - m y^\prime + 1 $ 이 되고, 이때 $ m > 1 $ 이므로 $ 1 $ 이 나머지가 된다. 따라서 $ n x^\prime \bmod m = 1 $ 이다.

$ 0 < x^\prime < m $ 을 만족시키지 않는다 가정하면, $ x = x^\prime \bmod m $ 이라 할 때, $ 0 \leq x < m $ 이 된다. 만약 $ x = 0 $ 이라면 $ m \mid x^\prime $ 이 되어 앞서 계산한 $ n x^\prime \bmod m = 1 $ 과 모순이 되므로 $ 0 < x < m $ 이다.

$ x = x^\prime \bmod m $ 이므로 $ x^\prime = q m + x $ 인 정수 $ q $ 가 존재한다. 앞선 식을 결합하면 $ nx = nx^\prime - mnq = - m y^\prime + 1 - mnq = m( - y^\prime -nq) + 1 $ 이다.

따라서 $ nx \bmod m = 1 $ 이다.

이때 $ x $ 는 유일하다. 이는 다음으로 증명된다.

$ nx \bmod m = 1 $ 과 $ nx^\prime \bmod m = 1 $, $ (0 < x < m, 0 < x^\prime < m) $ 을 가정하자.

$ x = x^\prime $ 을 증명하면 되는데, $ x^\prime = x^\prime \bmod m $, $ x = x \bmod m $ 이므로 $ x^\prime $$= x^\prime \cdot 1 $$= (x^\prime \bmod m)(nx \bmod m) $$= x^\prime n x \bmod m $$= \left[ ( x^\prime n \bmod m)(x \bmod m) \right] \bmod m $$= 1 \cdot x = x $ 이다.

그러므로 $ x $ 는 유일하다.