유클리드 알고리즘 (Euclidean Algorithm)
- gcd (a, 0) = a
- gcd (a, b) = gcd (b, r) (r = a % b)
의 두 가지 사실을 이용해, 두 양의 정수 a, b의 최대공약수를 구하는 알고리즘.
Example a: gcd(25, 65) = ?
⇒ gcd(25, 65) = 5
확장 유클리드 알고리즘 (Extended Euclidean Algorithm)
두 정수 a, b가 주어졌을 때, 아래 식을 만족하는 다른 두 정수 s, t와 gcd(a, b)까지 동시에 구하는 방법.
Example : a = 161, b = 28. s, t, gcd(161, 28) = ?
⇒ gcd(161, 28) = 7, s = -1, t = 6.
일차 디오판투스 방정식 (Linear Diophantine Equation)
미지수 x, y와 정수 a, b, c에 대해 ax+by=c (a≠0 또는 b≠0) 를 2변수 1차 디오판투스 방정식이라 한다.
이 부정방정식의 해 x, y를 구하기 위해 확장 유클리드 알고리즘이 사용된다.
gcd(a, b) = d 이고, d|c 일 때, ax+by=c 꼴의 일차 디오판투스 방정식의 특수해와 일반해는
특수해 : $$x_0 = (c/d)s$$$$y_0 = (c/d)t$$ 이고, 이 특수해를 이용한 일반해는
일반해 : $$x = x_0 + (b/d)k$$$$y = y_0 - (a/d)k$$ (단, k는 정수) 이다.
Example : 21x + 14y = 35 의 특수해와 일반해를 구하라.
a = 21, b = 14, c = 35.
확장 유클리드 알고리즘을 이용하면
gcd(21, 14) = 7 = d
s = 1, t = -1
d|c (7|35)를 만족하므로일차 디오판투스 방정식의 해 적용 가능.
따라서, 특수해는 $$x_0 = 5 * 1 = 5$$$$y_0 = 5 * (-1) = -5$$ 일반해는 $$x = 5 + 2k$$$$y = -5 - 3k$$