레온하르트 오일러(1707~1783)는 스위스에서 태어난 수학자입니다. 오일러라는 이름을 못 들어봤다면, 여러분은 한 분야에 인생을 매진했거나 수학에 담을 쌓은 사람일 겁니다.

  그 정도로 오일러는 수학에 엄청난 발자취를 남겼고 심지어 그 발자취 하나하나가 교과서를 장식합니다. 오일러는 함수를 $f(x)$로 쓰기 시작한 사람입니다. 또 자연상수 $e$, 지수함수와 로그함수를 대중화했습니다. '세상에서 제일 아름다운 공식'이라고 불리는 오일러의 공식을 발견했고, 심지어 기둥이 좌굴(기둥이 무게에 찌그러지는 대신 옆으로 꺾여버리는 현상. 좌굴을 일으키는 하중은 찌그러뜨리는 하중보다 작은 경우가 많아 꼭 대비해야 합니다.)하는 임계하중을 계산해내어 건축/토목공학에까지 자기 이름을 남겼습니다.

  '심심풀이로 읽는 수학' 등에 잘 나오는 이른바 '한붓그리기'도 오일러가 이론으로 승화했습니다. 그야말로 사람이 수학계에 세울 수 있는 업적은 거의 다 세웠다고 봐도 좋은 사람입니다. 삶이 곧 계산이자 수학이던 오일러는 1783년 76세의 나이에 뇌출혈로 사망합니다.

오일러의 정리

  오일러는 수학 전반에 걸쳐 업적을 남겼고, 오일러가 만든 공식과 기호도 많습니다. 이번에 살펴볼 것은 바로 오일러의 정리(Euler's theorem)입니다. 오일러의 공식(Euler's formula)와 헷갈리지 않도록 조심합시다. 물론 언젠가 오일러의 공식도 한 번 살펴볼 겁니다. 오일러의 정리는 다음과 같습니다.

  ≡는 보셨다시피 나눈 나머지가 같음을 나타내는 기호입니다. 나눗셈, 몫, 나머지랑 관련한 기호에 제곱이 당당하게 나오는 것이 신기합니다.

  그러나 아무 숫자나 넣어 보시면 공식이 맞음을 알게 됩니다. 예를 들어 10을 봅시다. 10 미만 자연수 중 10과 서로소인 수는 1, 3, 7, 9로 네 가지입니다. 즉 $\varphi(10)=4$입니다. 여기에 10과 서로소인 7을 a로 해 봅시다. 7^4는 2401입니다. 이걸 10으로 나누면 2401 = 10*240 + 1이 되어 나머지가 1입니다.

  합동식의 기본 개념을 '중국인의 나머지 정리'를 설명하면서 설명했습니다.

오일러의 정리 증명

  $\varphi(n)$에 해당되는 수(n보다 작으며 n과 서로소인 수)들만 모으면 $b_1, b_2 \dots$가 있다고 합시다.

(당연히 개수는 $\varphi(n)$)

  여기에 n과 서로소인 a를 곱하면 $ab_1, ab_2 \dots$가 됩니다. $b_1, b_2 \dots$가 모두 n과 서로소이고 a도 n과 서로소이므로 둘을 곱한 $ab_1, ab_2 \dots$도 n과 서로소입니다.

$ab_1, ab_2 \dots$를 n으로 나눕니다. 나머지는 서로 전부 다릅니다. 어떻게 알까요?

귀류법을 사용합니다. 귀류법은 일부러 틀리게 시작한 다음, 모순이 생기면 처음 가정이 틀리다고 결론 짓는 방법입니다. 그럼 나머지가 전부 다르지 않다, 같은 것이 있다고 가정해 봅시다.

  $ab_i \equiv ab_j \pmod{n}$ (단 i≠j)인 i와 j가 있다고 칩시다. ($= ab_i$를 n으로 나눈 나머지가 같은 i가 둘 있다) $ab_i \equiv ab_j$는 n으로 나눈 나머지가 같으므로 둘을 빼면 나머지가 상쇄해 n으로 나누어떨어질 겁니다.

  즉, $a(b_i-b_j)$가 n의 배수가 되는 셈이죠. a는 n과 서로소이므로 $(b_i-b_j)$쪽이 n의 배수입니다. b들은 n보다 작으면서 서로소인 수라고 했습니다. 당연히 전부 n 이하입니다. 이 b 둘을 뺐으니 차이의 절댓값도 n 보다 작습니다.

$-(n-1) \leq b_i-b_j \leq n-1$

그런데 이 범위에는 n의 배수가 있을 수 없습니다.

n=10이라면 $-(n-1)=-9, n-1=9$입니다.

-9와 9 사이엔 10의 배수가 없습니다.

$(b_i-b_j)$이 n의 배수인데 가능한 범위에 n의 배수가 존재하지 않다니요? 모순입니다.

따라서 귀류법에 따라 $ab_i$는 n으로 나눈 나머지가 같은 쌍이 있을 수 없습니다. 즉 나머지는 모두 다릅니다.

여기서 잠깐. 서로소를 나눈 나머지는 나눈 수와 서로소일까요?

X와 Y는 서로소다. X를 Y로 나눈 나머지는 Y와 서로소인가?로 써 봅시다.

이번에도 귀류법을 사용합니다.

Y와 나머지 Z가 서로소가 아니라고 해 보죠.

$Y=ay, Z=az (a \neq 1)$로 쓸 수 있습니다. a라는 1이 아닌 공약수가 있는 것이죠.

나눗셈은 $X = ay*m + az = a(ym + z)$로 표현 가능합니다.

$X =a(ym + z)$로 X는 a의 배수입니다.

X가 a의 배수라면 Y와 서로소라는 가정을 어기므로

귀류법에 따라 Y와 Z는 서로소입니다.

이렇게 n과 $ab_i$도 서로소이므로 n으로 나눈 나머지도 n과 서로소입니다.

$ab_1, ab_2 \dots$를 n으로 나눈 나머지들은

1) n보다 작고

2) n과 서로소고

3) 개수가 'n보다 작고 서로소인 숫자'들 개수와 같다.

그러므로 이 나머지들은 $b_1, b_2 \dots$와 순서는 다를지 몰라도 내용물이 완전히 같습니다.

  합동식은 mod 뒤 숫자만 같으면 여러 합동식이 있을 때 좌변은 좌변끼리, 우변은 우변끼리 곱해도 합동이 성립합니다.

$ab_1 \equiv \bigcirc_1 \pmod{n}$

$ab_2 \equiv \bigcirc_2 \pmod{n}$

$\dots$

↓

$ab_1 \times ab_2 \dots \equiv \bigcirc_1 \times \bigcirc_2  \dots \pmod{n}$

○들은 순서는 몰라도 내용물은 전부 $b_1, b_2 \dots$와 같습니다. 다 곱해버렸으니 이제 순서는 상관이 없겠죠. 따라서 

$ab_1 \times ab_2 \dots \equiv b_1 \times b_2 \dots \pmod{n}$

$ab_1 \times ab_2 \dots = a^{\varphi(n)} \times b_1 \times b_2 \dots $

로 쓸 수 있으니까 결과적으로

$a^{\varphi(n)} \times b_1 \times b_2 \dots \equiv b_1 \times b_2 \dots \pmod{n}$

입니다.

$b_1 \times b_2 \dots $는 n과 서로소고 최대공약수는 1이므로

합동식 성질에 따라

$ ab \equiv ac \pmod{m} $

일 때 d='a와 m의 최대공약수'라면

$b \equiv c \pmod{m/d}$로 나눌 수 있습니다.

  이 식에선 $b_1 \times b_2 \dots $와 n은 서로소니까 최대공약수 d=1입니다. 그러니 $b_1 \times b_2 \dots $로 나눠도 mod 뒤에 있는 n은 1로 나뉘어 똑같겠네요.

$1 \equiv a^{\varphi{n}} \pmod{n}$

페르마의 소정리

  수학자 하면 페르마도 빼놓을 수 없습니다. 비록 아마추어 수학자라고는 하지만 웬만한 프로 수학자만큼 업적이 대단한 사람이죠. 그 유명한 페르마의 마지막 정리로 수학자들을 고생시킨 장본인이고요.

페르마의 소정리(Fermat's little theorem)는 다음과 같습니다.

  페르마의 소정리는 오일러의 정리에 n 대신 소수 p를 입력하면 됩니다. 소수는 1과 자기 자신 빼고는 약수가 없는 수입니다. 따라서 소수 미만 자연수는 전부 그 소수와 서로소입니다.($\varphi(p)= p-1$)

응용

  페르마의 정리는 솔직히 실생활에 거의 쓸모가 없는 공식입니다. 주로 수학경진대회에 나와서 학생들의 골머리를 아프게 하죠.

문제 예) 7^2016의 마지막 세 자리를 구하시오

풀이 ) $\varphi(1000) = 400$임을 이미 아는 상태에서 시작하자.

$a=7, n=1000$으로 놓으면

$7^{400} \equiv 1 \pmod{1000}$이다.

$7^{2016} = (7^{400})^5 * 7^{16}$이고

$7^{2016} \equiv (7^{400})^5 * 7^{16} \pmod{1000}$이며

($a \equiv a \pmod{m}$이니까)

$7^{2016}$을 1000으로 나눈 나머지(마지막 세 자리)는

$(7^{400})^5 * 7^{16}$을 1000으로 나눈 나머지와 같다.

$(7^{400})^5$는 1000으로 나눈 나머지가 1이므로

......001로 끝난다. 여기에 $7^{16}$을 곱한 수는

마지막 세 자리가 $7^{16}$과 같다. 그러므로

$7^{2016}$의 마지막 세 자리는 $7^{16}$의 마지막 세 자리와 같다.

(물론 $7^{16}$의 마지막 세 자리도 구하긴 어렵겠지만)