[수학] 6. 라그랑주 정리

Understanding Cryptography | Christof Paar로 암호학을 공부하던 중 억울하게도 라그랑주의 정리 보다 라그랑주의 따름정리를 먼저 보게 되었다.
나는 아직 군(Group)의 개념을 처음 본 상황 이였고 라그랑주 정리뿐만 아니라 부분군(subgroup)이 뭔지도 몰랐다.

내가 공부하고 있는 교재는 암호학 교재여서 학교에서 배웠던 것처럼 증명은 잘 다루지 않았다. 그래서 내가 직접 증명을 해보려고 했다.
라그랑주 정리는 다음과 같다.

Lagrange’s theorem
유한군 G와 그 부분군 H에 대하여, |H|는 |G|의 약수이다.

교재에는 라그랑주 정리 말고 그것의 따름 정리를 먼저 설명해 주었다.

교재에 나와있는 대로 정확히 쓰면 다음과 같다.

유한군 $G$의 모든 원소 $g$는 $g^{|G|} = \mathbf{1}$을 만족시킨다.

이 때 1은 항등원을 의미한다.

내가 했던 증명은 다음과 같다.

증명과정 (펼치기/접기)

임의의 유한군 $(G, \cdot)$ 에 대하여
$$ G = \{1, a_1, a_2, ... , a_N\} $$ 라고 하자. 그러면 다음을 만족시키는 자연수 $k$가 존재한다.
$$ (a_1)^k = 1, \;\; 1 < k \le |G| $$ 이는 다음과 같이 증명할 수 있다.

증명

서로 다른 자연수 $i, j (i>j)$ 에 대하여
$(a_1)^i = (a_1)^j $일 때 $(a_1)^{i-j} = 1$ 이다. 이때 $i-j$ 가 $k$가 된다.
$(a_1)^1, \: (a_1)^2, \: ... , \: (a_1)^{|G|}$ 가 모두 서로 다르다고 가정하자. 그러면 $|G|$개의 원소들이 $G$의 원소이므로 1은 저 원소들 중 하나이다. 따라서 $(a_1)^k = 1$인 $k$가 $|G|$ 이하인 자연수 중에서 존재한다.

$(a_1)^k = 1$ 을 만족하는 $k$ 중 가장 작은 수를 $k$로 다시 정하겠다. 또한 $|G| = mk + r$ 을 만족시키는 $m, r$이 존재한다
($m$은 자연수, $r \in \{0, 1, \dots, k-1\}$)

$(a_1)^1, (a_1)^2, \dots, (a_1)^{k-1}$은 모두 서로 다르므로 일반성을 잃지 않고 $i < k$인 자연수 $i$에 대하여
$a_i = (a_1)^i$ 라고 할 수 있다.

$m$ 이하의 자연수 $t$와 $k$보다 작은 자연수 $i$에 대하여 $b_{tk+i} = a_{tk} \cdot a_i$, $b_{tk} = a_{tk}$ 라고 정의하자.

$i \in \{0, 1, 2, \dots, k-1\}$ 이고 $t$가 $m$ 이하의 자연수 일 때 $b_{tk+i} \neq 1, a_1, a_2, \dots, a_{k-1}$ 이다.¹
증명은 다음과 같다.

증명

$b_{tk+i} = 1$ 이면 $a_{tk} = a_{k-i}$ 이다. 이는 모순.
$k$보다 작은 자연수 $j$에 대하여
$b_{tk+i} = a_j$ 라고 하자. 그러면
$b_{tk+i} = a_{tk} \cdot a_i = a_j$
이는 $a_{tk} \in \{1, a_1, a_2, \dots, a_{k-1}\}$ 이므로 모순.

즉, 일반성을 잃지 않고 $i < k$인 자연수 $i$에 대하여 $a_{k + i} = a_k \cdot a_i$ 라고 할 수 있다. 이러면 $1$보다 큰 자연수 $t$에 대하여 $b_{tk + i} \neq a_{k + j}$ 이다. 증명은 다음과 같다. ²

증명

$b_{tk+i} = a_{k+j}$ 라고 하자.
$a_{tk} \cdot a_i = a_k \cdot a_j$
$a_{tk} \in \{a_k, a_{k+1}, a_{k+2}, \dots, a_{2k-1}\}$ 이는 모순.

즉, ²의 증명과정을 이용하면 일반성을 잃지 않고
$a_{2k + i} = b_{2k + i}$
$a_{3k + i} = b_{3k + i}$
...
$a_{(m-1)k + i} = b_{(m-1)k + i}$
$a_{mk + 1} = b_{mk + 1} , \dots , a_{mk + r - 1} = b_{mk + r - 1}$
라고 할 수 있고 $b_{tk+i} = b_{uk+j}$ 인 경우 $t=u, i=j$ 이다.³

증명

$t=u$인 경우 $b_{tk+i} = b_{uk+i} = a_{tk} \cdot a_i$ 한편, $b_{uk+j} = a_{uk} \cdot a_j$ 이므로 $i = j$
$t \neq u$ 인 경우 $a_{tk} \cdot a_i = a_{uk} \cdot a_j$ 이는 ²의 증명과정을 이용하여 모순

참고

$$ \begin{align*} G = \{ &1, a_1, a_2, \dots, a_{k-1}, \\ &a_k, a_{k+1}, \dots, a_{2k-1}, \\ &\dots, \\ &a_{mk}, a_{mk+1}, \dots, a_{mk+r-1} \} \end{align*} $$

$k \le i < mk+r$ 인 자연수 $i$에 대하여 ³에 의해
$r \neq 0$ 일 경우 $a_{mk + r - 1} \cdot a_1 = b_{mk + r} \neq b_i (=a_i)$ 이다. ¹에 의해 $b_{mk + r} \neq 1, 2, \dots, a_{k-1}$ 이므로
$a_{mk+r} \cdot a_1$은 $G$의 원소가 아니다. (다시 말해 $G$의 원소의 개수가 $|G|$ 보다 크다.) 이는 모순.
즉, $r = 0$ 이다. 따라서
$|G| = mk+r = mk$ 이므로 $(a_1)^{|G|} = (a_1)^{mk} = 1. \square$

원래의 라그랑주 정리는 부분군(subgroup)을 이용하여 쉽게 증명할 수 있다.
라그랑주 정리에 대해서 공부해보니 내가 했던 증명 방식은 잉여류(coset) 개념을 $b_{tk+i}$로 구현해서 증명했다는 것을 알 수 있었다.
추상적으로 받아들일 수 있는 라그랑주 정리의 증명을 더 직관적으로 볼 수 있는 증명이지 않을까 싶다.
(사실 내가 한 증명은 그냥 의미없어 보이기도 한다..)

RSA, Diffie-Hellman 키 교환, ECC 등 우리가 쓰는 거의 모든 공개키 암호 알고리즘은
결국 $a^{|G|} = \mathbf{1}$ 이라는 한 줄의 식에서 뻗어나간다.