유클리드 알고리즘
vs.
확장 유클리드 알고리즘
만약...
이원일차부정방정식 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의
하나의 특수해를 알면
그것을 이용하여 일반해를 구하는 것은
쉬운 것으로 알려져 있습니다.