최근 보고 있는 MITOCW - 6.042J / 18.062J Mathematics for Computer Science에는

매 시간마다 Problems가 있어 그 날 배운 것을 복습할 수 있습니다.

아쉽게도 reading으로 제공되는 pdf 파일과 강좌 슬라이드만을 볼 수 있어

많은 자료를 얻지 못하는 단점이 있지만,

무료로 강의 자료를 얻는 것이니 이 정도라도 충분한 듯싶습니다.^^

여기에 사용된 정리들입니다.

7 · 3 ≡ 1  (mod  5)

에서 3은 modulo 5에서 multiplicative inverse of 7입니다.

물론 그 반대로 7은 3의 multiplicative inverse입니다.

여기 나온 문제 중 다음 문제가 재미있었습니다.

(b) Wilson’s Theorem says that (p-1)! ≡-1  (mod p).

The English mathematician Edward Waring said that

this statement would probably be extremely difficult to prove

because no one had even devised

an adequate notation for dealing with primes.

(Gauss proved it while standing.)

Your turn! Try cancelling terms of (p-1)! in pairs.

See if you can do it while standing on one leg.

Wilson's Theorem에 대해서 잘 모르지만, 재미있는 문구가 보였습니다.

'가우스는 일어선 동안 증명하였다.'

'너는 한쪽 다리로 서있는 동안 할 수 있음을 보여라.'

해당 문구를 보고 '좋다. 그럼 나도 해보자.'라며

자리에 일어서서 해당 정리의 증명을 생각하였습니다.

하지만 10분 가량을 생각해보았지만, 막히는 부분이 있어 증명할 수 없었습니다.

대표적으로 mod p에서 Multiplicative Inverse는 존재함을 알았지만,

이것이 uniqueness한지에 대한 얘기가 없었습니다.

만약 이것이 uniqueness하다면 생각을 더 진행할 수 있었으나

해당 성질을 증명하려면 종이와 펜이 필요하였기에 일어선 동안에는 하지 못합니다.

즉, 바로 가는 길이 있음에도 조금 돌아서 가는 길이라 생각하였고,

좋은 증명법을 알고자 답을 확인하였습니다.

답을 보니 2임을 얘기하고 그 뒤에 2보다 큰 값들을 얘기하고 있습니다.

하지만 왜 그렇게 나눠서 얘기하는지,

1과 p-1이 self-inverse임을 알지만(앞의 a번 문제에서 이를 구합니다.)

그 사이의 2부터 p-2는 서로 self-inverse가 있는지가 궁금하였습니다.

정확하게는 uniqueness가 있어 pair로 묶을 수 있는지 궁금하였습니다.

그렇게 한참을 고민하다 결국 그 뜻을 알았습니다.

먼저 p가 2라면 1! ≡ -1 (mod 2)로 성립함을 알 수 있습니다.

다음으로 소수는 2를 제외하고 모두 홀수입니다.

따라서 2부터 p-2의 개수는 2를 제외하고 모두 짝수입니다.

그렇기에 2를 제외하고 uniqueness가 있다면 pair로 묶을 수 있습니다.

따라서 이렇게 해당 구간 사이에 multiplicative inverse가 유일함을 확인하였습니다.

그리고 2부터 p-2까지는 모두 소수 p의 배수가 아닙니다.

그렇기에 2 이상의 modulo 소수에서

2에서 p-2까지 multiplicative inverse를 만들 수 있습니다.

최종적으로 그 안의 것들은 전부 1로 바뀔 것이고,

self-inverse를 갖는 1과 p-1의 곱과 modulo p 합동임을 알 수 있습니다.

따라서 이는 -1과 modulo p 합동입니다.

다른 문제와 마찬가지로 이 역시 이해를 한 후 그대로 문서철에 보관할 생각이었습니다.

하지만 이렇게 굳이 시간을 투자하여 글을 남기는 이유는

위에서 얘기한 두 문장 때문입니다.

(Gauss proved it while standing.)

See if you can do it while standing on one leg.

SICP를 풀면서도 느낀 것이지만,

이 문제를 주로 접하는 사람이 유능한 학생이라는 생각이 있어서인지

'역사상 천재가 이 문제를 풀었다.

너는 그들이 모르는 것을 알고 있다.

그럼 너도 한 번 풀어봐라.'

라는 식으로 학생에게 도전장을 던지는 투의 문장이 있었습니다.

물론 거기에 일일이 도발당해 열심히 삽질하다

'천재는 역시 다르구만...'이라며 먼산만 보는 저이기는 하지만...OTL.....

하지만 문제를 접할 때 호기심을 일으키는 좋은 방법 중 하나가

이렇게 학생을 도발하는 것이 아닌가 하는 생각이 듭니다.^^

여하튼 세상은 넓고 괴물은 많습니다...(먼산...;;;)

PS

위키피디아와 mathworld를 찾아보니 증명법이 다양합니다.

자료가 더 필요한 분은 도움이 되리라 생각합니다.

참조

008.pdf

009.pdf

http://en.wikipedia.org/wiki/Wilson%27s_theorem

http://mathworld.wolfram.com/WilsonsTheorem.html

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.