재후의 이항연산 : ＜s , t＞＜v , w＞ = ＜tv , tw + s＞

[재후]

재후의 이항연산 : 

<s , t><v , w> = <tv , tw+s>

[  어디서 무엇이 되어 다시 만나랴 -  유심초 (작시: 김광섭) ]

여기에서 소개하는

이항연산은

[확장 유클리드 알고리즘]을 위해

제가 독자적으로 생각해 낸

매우 유용한(?)

이항연산입니다. 

---

고대 수학과

현대 수학의

만남

[ 저녁에 - 김광섭 작시 (어디서 무엇이 되어 다시 만나랴) ]

고대의 수학자들이 남기고 간 발자국을 따라 다시 걸으며

거기에 끼워 넣을 수 있는 독자적인 수학을 생각하다 보면

수학을 통해 시공을 초월하여

이미 만날 운명이었음을 느끼는 경우가 많습니다.

[재후의 이항연산] 또한

그 중의 하나입니다.

재후의 이항연산 

<s , t><v , w> = <tv , tw+s>

k<s , t> = <ks , kt>

(단, k는 실수)

※ 주의 사항:

위의 이항연산은

교환법칙, 결합법칙이 성립하지 않으므로

특별한 언급이 없는 한

앞에서부터 차례대로 계산해야 합니다.

그 절묘한 만남을

이제부터

위의 이항연산을 통해

풀어보겠습니다.

[유클리드 알고리즘]은

다음과 같습니다.

b를 a로 나누었을 때

몫을 q, 나머지를 r이라 하면

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

즉

b를 a로 나누었을 때

몫에는 관심을 가질 필요가 없음을 알 수 있습니다.

그러나

[확장 유클리드 알고리즘]을 통해

역연산으로

gcd(b, a) = ax + by 꼴로 나타내려 할 때는

몫의 영향을 받게 되어 있습니다.

따라서 위의 [유클리드 알고리즘] 표현에 빠져있는

몫을 다음과 같이 함께 나타내는 방법을 쓰도록 하겠습니다.

혹은

이것은

b를 a로 나누었을 때

몫은 q, 나머지는 r임을 나타내는 동시에

[유클리드 알고리즘]을 나타내고 있는

표기법입니다.

이제

19332와 1368의 최대공약수를

구하는 과정을 예로 들어보겠습니다.

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

이제 위에서 소개한 표기법을 사용하여

나타낸 것이 위 표에서 오른쪽 셀에 있으며,

[유클리드 알고리즘] 과정을

쭉 연결하여 나타내면

다음과 같습니다.

(참고: 나머지가 0이 되는 과정까지 쓸 필요는 없습니다.

나머지가 0이 됨을 눈치 챘으면 과정은 끝난 것입니다.)

과정을

일반화해서

나타내면 다음과 같습니다.

(단, R_n-1을 R_n으로 나눈 나머지는 0)

 

이제

[재후의 이항연산]을

이용할 시간이 되었습니다.

다음과 같은 

[재후의 이항연산]

계산이 필요합니다.

얻어진 몫 순서의

역순으로 몫을 사용합니다.

그러면

다음과 같은 

[유클리드 알고리즘]에서...

필요한

[재후의 이항연산]은

다음과 같습니다.

[재후의 이항연산] 규칙에 따라

실제로 계산을 해보겠습니다.

이를테면

<1, -1><1, -1> = <-1×1, -1×(-1) + 1> = <-1, 2>

<-1, 2><1, -7> = <2×1, 2×(-7) + (-1)> = <2, -15>

따라서...

<1, -1><1, -1><1, -7><1, -14>

=

<-1, 2><1, -7><1, -14>

=

<2, -15><1, -14>

=

<-15, 212>

즉

∴ <1, -1><1, -1><1, -7><1, -14> = <-15, 212>

위와 같은 계산을

도대체 왜 하고 있는 것일까요?

우리는

gcd(b, a) = bx + ay를 만족하는

정수 x, y를 찾고 있습니다.

즉

gcd(19332, 1368) = 36 이므로

36 = 19332·x + 1368·y

혹은

19332·x + 1368·y = 36을 만족하는

정수 x, y를 찾고 있습니다.

그런데...

이미 구했답니다.

∴  <1, -1><1, -1><1, -7><1, -14> = <-15, 212>

짜잔 !!!

<-15, 212> = <x, y>

즉

x = -15, y = 212

검증:

19332·x + 1368·y

=

19332×(-15) + 1368×(212)

=

36

혹은

gcd(19332 , 1368) = 19332×(-15) + 1368×(212)

즉

[재후의 이항연산]은

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

정수해 <x, y>를 구하는 것임을 알 수 있습니다.

다시 말하자면...

[재후의 이항연산]의 결과,

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

하나의 특수해 <x, y>를 얻게 되는 것입니다.

---

어디서 무엇이 되어 다시 만나랴

(수화 김환기(樹話 金煥基, 1913~1974) 작품)

점과 점이 만나 선이 되고,

선과 선이 만나 면이 되고

면과 면이 만나 공간이 되고

공간과 시간이 만나

그 속에서 인연이 이루어집니다.

[재후의 이항연산]은

많은 시행착오 속에서

탄생한 것입니다.

수많은

실패와 실패의 만남,

그리고

실낱같은

실패와 성공의 만남,

그리하여

결국

성공과 성공의 만남.

이제

[재후의 이항연산]을 통해,

이원일차부정방정식

ax + by = c를 만족하는

정수해 x, y를 공식화할 수 있는

하나의 수단을 가지게 되었습니다.

다음 글에서

이 문제를 해결하겠습니다.

---

그리고

이것을

일명성 공식을 구하는데

활용할 수 있는 지

살펴볼 것입니다.

[zaiz]

제가 수학에 대한 지혜가 있었다면
재후님의 글에 훨씬 깊이 빠져들 수 있었을 것입니다