유클리드 알고리즘 vs. 확장 유클리드 알고리즘

[재후]

유클리드 알고리즘

vs.

확장 유클리드 알고리즘

[  You and I -  아이즈원 / 송소희 / 박봄 ]

만약...

이원일차부정방정식 ax + by = c의

하나의 특수해를 구할 수만 있다면

일반해를 구하는 것은 쉬운 것으로 알려져 있습니다.

이것은

[유클리드 알고리즘 vs. 확장 유클리드 알고리즘]의

콤비네이션에 의한

하나의 특수해를 구하는 방법에 관한 것입니다.

유클리드 알고리즘

(Euclidean Algorithm)

두 자연수 b, a에 대하여

b를 a로 나눈

몫을 q, 나머지를 r이라 할 때,

b, a의 최대공약수는 

a, r의 최대공약수와

같습니다.

∴ gcd(b, a) = gcd(a, r)

혹은

∴ gcd(b, a) = gcd(a, [b]_a)

자연수 d에 대하여,

∴  gcd(d, 0) = d

이를테면...

78696 , 19332의 최대공약수를 구하는 문제는

다음과 같이

나눗셈의 나머지를 구하는 과정을 계속 적용하여 해결합니다.

나머지가 0이 나올 때까지 진행하게 됩니다.

(이때 몫에는 관심을 가질 필요가 없습니다.)

78696 ＝ 19332×4 ＋ 1368     19332 ＝ 1368×14 ＋ 180      1368 ＝ 180×7 ＋ 108       180 ＝ 108×1 ＋ 72       108 ＝ 72×1 ＋ 36        72 ＝ 36×2 ＋ 0

gcd(78696 , 19332)=gcd(19332, 1368) gcd(19332, 1368) = gcd(1368, 180) gcd(1368, 180) = gcd(180, 108) gcd(180, 108) = gcd(108, 72) gcd(108, 72) = gcd(72, 36) gcd(72, 36) = gcd(36, 0) = 36

함수명 gcd를 생략하고 표현하는 경우도 많습니다.

∴ (b, a) = (a, r)

혹은

∴ gcd(b, a) = gcd(a, [b]_a)

78696 ＝ 19332×4 ＋ 1368     19332 ＝ 1368×14 ＋ 180      1368 ＝ 180×7 ＋ 108       180 ＝ 108×1 ＋ 72       108 ＝ 72×1 ＋ 36        72 ＝ 36×2 ＋ 0

(78696 , 19332) = (19332, 1368) (19332, 1368) = (1368, 180) (1368, 180) = (180, 108) (180, 108) = (108, 72) (108, 72) = (72, 36) (72, 36) = (36, 0) = 36

그런데...

유클리드 알고리즘을 구하는 과정의

역 과정을 따라 계산해보면

gcd(b, a) = a·x + b·y 꼴로

나타낼 수 있음이 알려져 있습니다.

이것이 바로

'확장 유클리드 알고리즘'

입니다.

확장 유클리드 알고리즘

(Extended Euclidean Algorithm)

두 자연수 a, b에 대하여

ax + by = gcd(a, b)를 만족하는

정수 x, y를 구하는 알고리즘 중 하나입니다.

102와 38의 최대공약수를

유클리드 알고리즘으로 구하는 과정을

예로 들어보겠습니다.

102 = 2×38 + 26

38 = 1×26 + 12

26 = 2×12 + 2

12 = 6×2 + 0

최대공약수는 2입니다.

따라서 역계산을 통해

다음과 같은 꼴로 나타내야 합니다.

2 = 102·x + 38·y

102 = 2×38 + 26 38 = 1×26 + 12 26 = 2×12 + 2 12 = 6×2 + 0

∴ 26 = 102 - 2×38  … ① ∴ 12 = 38 - 1×26  … ② ∴ 2 = 26 - 2×12  … ③

우측에 있는 식은

좌측에서 얻어진 나머지를 좌변에 두어

그 나머지를 다른 것으로 대치하기 위함입니다.

맨 마지막에 있는

나머지 식에서 시작합니다.

∴ 2 = 26−2×12  … ③

여기에 ②식을 대입하면

2 = 26 - 2 × (38 - 1× 26)

정리하면

2 = 3 × 26 - 2 × 38

여기에 ①식을 대입하면

2 = 3 × (102 - 2× 38) - 2× 38

정리하면

2 = 3 × 102 - 8 × 38

곧

2 = 102×(3) + 38×(-8) 

일반적으로

2 = 102·x + 38·y 를 만족하는

정수 x, y는 무수히 많습니다.

위의 부정방정식을 만족하는

하나의 특수해가

바로 x = 3, y=-8이라고 할 수 있습니다.

즉 부정방정식의 특수해를 구하는 방법 중의 하나가

'확장 유클리드 알고리즘' 입니다.

먼저

'유클리드 알고리즘'을 통해

최대공약수를 구한 후,

'확장 유클리드 알고리즘'이라는

역연산을 통해

특수해를 구하는 것입니다.

이원일차부정방정식 ax + by = c의

하나의 특수해를 알면

그것을 이용하여 일반해를 구하는 것은

쉬운 것으로 알려져 있습니다.