제비의 리(除比의 理)의 활용 ⑤ : 최소공배수 호제법

제비의 리(除比의 理)의 활용 ⑤ :최소공배수 호제법 <embed width="560" height="315" src="https://www.youtube.com/v/RjzI-Y5S8iQ" frameborder="0" allowScriptAccess='sameDomain' type='application/x-shockwave-flash'> [ Swept Away - YANNI (Live At The Acropolis 1993) ] 최대공약수(Greatest Common Divisor)에 대한 호제법이 존재한다면그것과 쌍벽을 이루는최소공배수(Least Common Multiple)에 대한 호제법도 존재할까요? 물론입니다. 그런데... 최대공약수에 대한 호제법인유클리드 호제법을 이용하면최소공배수에 대한 호제법은아주 쉽게 구할 수 있기 때문에별도로 언급되지 않는게 보통입니다. 또한더 큰 이유는최대공약수를 알면최소공배수는 쉽게 구할 수 있기 때문입니다. 즉A, B의 최대공약수를 G,최소공배수를 L이라 하면이들 사이에는 다음 관계가 성립합니다.A·B = G·L … ① 혹은A, B의최대공약수를 gcd(A, B),최소공배수를 lcm(A, B)라고 한다면A·B = gcd(A, B)·lcm(A, B) … ①' ①식에서 알 수 있듯이 A, B, G를 알면L을 쉽게 구할 수 있는 것입니다. 또한유클리드 호제법과위의 관계를 이용하여최소공배수에 대한 호제법을쉽게 구해낼 수 있습니다. 이를테면두 수 b, a에 대하여b를 a로 나눈 몫을 q, 나머지를 r이라 할 때,b, a의 최대공약수를 gcd(b, a), a, r의 최대공약수를 gcd(a, r) 이라고 한다면 유클리드 호제법에 의해 gcd(b, a)는 gcd(a, r)와 같아야 합니다. gcd(b, a) = gcd(a, r) … ② 또한①'의 관계를 적용하면 b·a = gcd(b, a)·lcm(b, a) … ③ a·r = gcd(a, r)·lcm(a, r) … ④ 그러면②, ③, ④에 의해b·a / lcm(b, a) = a·r / lcm(a, r) 정리하면...lcm(b, a) = (b/r)·lcm(a, r) (단, r≠0)  이것이 바로'최소공배수 호제법'입니다. 그런데... 혹시[제비의 리(除比의 理)]를 활용하여'공약수 중 최대값이 최대공약수'라는 개념을 동원해유클리드 호제법을 유도했듯이,'공배수 중 최소값이 최소공배수'라는 개념을 동원해위와 같은 최소공배수 호제법을 유도할 수 있을까요? 가능합니다. <hr style="display:block; border: black 0 none; border-top: black 1px solid; border-bottom: black 3px solid; height: 7px"> [제비의 리(除比의 理)]를 이용한'최소공배수 호제법' <table class="txc-table" width="700" cellspacing="0" cellpadding="0" border="0" style="border:none;border-collapse:collapse;;font-family:gulim;font-size:13.3333px"><tbody><tr><td style="width:700px;height:24px;border-bottom:1px solid #ccc;border-right:1px solid #ccc;border-top:1px solid #ccc;border-left:1px solid #ccc;;">  lcm(b, a) = b/[b]a × lcm(a, [b]a)(단, [b]a≠0) </td></tr></tbody></table> (증명) 두 수 b, a에 대하여b를 a로 나눈 몫을 Q, 나머지를 R이라 합시다. 이제b, a의 공배수를 u,a, R의 공배수를 v라 하면... 공배수 중 최소값이 최소공배수이므로u의 최소값 min(u)와v의 최소값 min(v)의관계를 유도하면 됩니다. 물론 목표는 다음 관계식입니다. <table class="txc-table" width="700" cellspacing="0" cellpadding="0" border="0" style="border:none;border-collapse:collapse;;font-family:gulim;font-size:13.3333px"><tbody><tr><td style="width:700px;height:24px;border-bottom:1px solid #ccc;border-right:1px solid #ccc;border-top:1px solid #ccc;border-left:1px solid #ccc;;"> 목표:min(u) = (b/R)·min(v) </td></tr></tbody></table> u는 b, a의 공배수이므로 u = b×s , u = a×t  … ① v는a, R의 공배수이므로 v = a×y , v = R×z  … ② 따라서 ①에서 u = bs = at … ①' ②에서 v = ay = Rz … ②' ①'에서 b/a = t/s 여기에 [제비의 리(除比의 理)]를 적용하면 R/a = t'/s … ③ (단, R은 b를 a로 나눈 나머지, t'는 t를 s로 나눈 나머지) 또한 ②'에서 R/a = y/z … ④ ③, ④에서 R/a = t'/s = y/z … ⑤ 위와 같이 R/a는 분수입니다. 분수는 무한히 많은 방법으로 나타낼 수 있습니다. 이를테면4/2 = 8/4 = 12/6 = … 처럼... 하지만 그러한 분수들을 기약분수로 나타내서가능하면 분모, 분자가 최소가 되도록 할 수도 있습니다. 기약분수로 나타냈을 때그 분수의 분모, 분자는 최소가 됩니다. 4/2 = 8/4 = 12/6 = … = 2/1 처럼... 즉 R/a = t'/s = y/z … ⑤에서 분수 R/a에 대한 또 다른 분수 표현식인 t'/s 및 y/z의 s, z 등에 값들을 바꿔가면서다양한 분수를 얻어낼 수 있지만기약분수로 나타내면 그 표현이 같아집니다. 기약분수로 나타내려면선택할 수 있는 값 중에최소값을 취하면 됩니다. 즉min(s) = min(z) … ⑥ 그런데 ⑥을 ①에 적용하면min(u) = b×min(s) … ⑦ ⑥을 ②에 적용하면min(v) = R×min(z) … ⑧ 이제 ⑥, ⑦, ⑧에서 min(u) / b = min(v) / R 즉 min(u) = b/R × min(v) (단, R≠0) 즉lcm(b, a) = b/[b]a × lcm(a, [b]a)(단, [b]a≠0) ¶ (증명 끝)