| [ QuizWit ] in KIDS 글 쓴 이(By): scheme (스킴이어요�`) 날 짜 (Date): 1994년05월20일(금) 17시56분26초 KDT 제 목(Title): [re] 이진 최대공약수 (m,n)을 편의상 m과 n의 gcd를 나타낸다고 합시다. Claim) (2^m-1,2^n-1) = 2^(m,n) - 1 proof) 먼저 다음의 식을 증명하겠습니다. (2^(m+n)-1,2^n-1) = (2^m-1,2^n-1) 증명은 쉽습니다. (2^(m+n)-1,2^n-1) = (2^m * 2^n - 1,2^n-1) = (2^m-1 + (2^n-1)2^m,2^n-1) = (2^m-1,2^n-1) 이제, 이 식을 이용해서, 유클리드 호제법처럼(for Illusion: Euclidean Algorithm) 식 (2^m-1,2^n-1)에서 m과 n을 서로 빼 줍니다. d = (m,n)이라면, 결국은 우리가 이렇게 해서 얻는 값은 (2^m-1,2^n-1) = (2^0-1,2^d-1) = (0,2^d-1) = 2^d-1 qed !@#$%^&*()_+~!@#$%^&*()_+~ "The time has come," the Walrus said, "To talk of many things: 스킴이어요 ...... Of shoes-and ships-and sealing-wax -- !@#$%^&*()_+~!@#$%^&*()_+~ Of cabbages-and kings --" -Lewis Carroll |