조합적으로 증명하는 합동식

정수론의 기초에서 다뤄지는 여러 합동식들 중 조합적인 아이디어로 증명하는 것이 가능한 경우가 있다. 여기서 일부 그러한 증명들을 소개하고자 함.

먼저, 소수 $p$ 와 정수 $a$ 에 대해 $a^p \equiv a\text{ (mod }p\text{)}$ 가 성립한다는 페르마의 소정리를 조합적으로 보일 수 있다. 원 하나를 $p$ 개의 동일한 부채꼴로 등분한다. 이 부채꼴들을 주어진 $a$ 개의 색들로 칠한다면, 그 모든 경우의 수는 $a^p$ 가 된다. 이 색칠된 결과는 크게 보아 다음 두 가지의 경우로 분류할 수 있다.

모든 부채꼴이 같은 색인 경우. 즉 한 가지 색만 쓴 경우로, 이런 경우의 수는 $a$ 가지.
그 외의 경우. 원의 중심을 중심으로 $2\pi / p$ 만큼 시계방향으로 회전하는 시행을 편의상 “회전”이라고 부르도록 한다. 그러면 이렇게 두 가지 이상의 색을 이용해 색칠한 상황에서 $p$ 번 회전하면 다시 원래대로 돌아오는데, 그 과정에서 등장하는 $p$ 개의 결과물들은 전부 서로 달라야 한다. (만약 중간에 $k$ 번 회전했을 때와 $k+d$ 번 회전했을 때의 결과가 같았다면 ( $d<p$ ) 두 상황에서 $k$ 번 역회전함으로써 원래 configuration은 $d$ 번 회전한 결과와 같아져야 함을 얻는다. 이런 $d$ 의 최솟값을 잡으면 $d|p$ 를 얻어 $p$ 가 소수임에서 $d=1$ 이 되어야 하나 이는 곧 모든 부채꼴의 색이 동일함을 의미하게 되어 모순이 된다)

따라서 두 번째 경우에 해당하는 $a^p-a$ 가지의 configuration들은, 회전을 통해 얻는 것이 가능할 때 동치관계가 성립한다고 두면 동치류들로 분할되고 각각의 동치류는 $p$ 개의 원소를 갖기 때문에 $p|a^p-a$ 가 성립하게 된다.

이는 곧 순환군 $C_p$ 의 group action의 orbit 개수를 세는 것과 연관이 있다. 이에 대한 일반적인 결과물로는 Burnside’s lemma이나 Polya’s theorem같은 것들이 있음. 사실 이런 elementary group theory에서 기초적인 예시 $S_p$ , $C_p$ 나 $\mathbb{Z}/p\mathbb{Z}$ 에 대한 group action의 조합적인 고찰들 때문에 그 관점에서 정수론적 결과물이 나오는 것도 다소 필연적이기도 하다. 참고로 위 증명은 Ira Gessel의 슬라이드에 의하면 1872년 Julius Petersen의 증명이라고 한다.

비슷한 예로 이런 것도 있다. 두 양의 정수 $a,b$ 와 소수 $p$ 에 대해 $\binom{ap}{bp} \equiv \binom{a}{b}\text{ (mod }p^2\text{)}$ 가 성립한다는 것.

$a<b$ 인 경우는 트리비얼하니 $a \geq b$ 라고 한다. 이 때 $ap$ 개의 단위정사각형을 가로 $p$ 개, 세로 $a$ 개로 직사각형 모양으로 배열하고, 이 $ap$ 개의 칸들 중 $bp$ 개의 칸을 택해 색칠한다고 한다. 이 때 각각의 행에 대해서, 1개 이상 $p-1$ 개 이하의 칸이 색칠되었다면 그 행을 “불완전한” 행이라고 부르고, $p$ 개의 모든 칸이 칠해진 행은 “완전한” 행이라 부르도록 한다. 그러면 불완전한 행은 1개만 나올 수 없으므로 (만약 1개만 나오면 나머지 행들은 색칠된 칸의 개수가 전부 $p$ 의 배수라서 총 색칠된 칸의 개수는 $p$ 의 배수가 되지 않기 때문에) 0개 또는 2개 이상이 되어야 한다.

모든 경우의 수는 $ap$ 개 중 $bp$ 개를 택하면 되므로 $\binom{ap}{bp}$ 가 되며, 불완전한 행이 0개인 경우의 수는 $a$ 개의 행 중에서 완전한 행 $b$ 개를 택해야 해 $\binom{a}{b}$ 가 된다. 따라서 불완전한 행이 2개 이상인 경우의 수가 $p^2$ 의 배수임만 보이면 증명이 끝난다.

불완전한 행이 $k>1$ 개라고 둔다. 여기서, 불완전한 행 하나를 택해 그 행의 칸들을 오른쪽으로 한 칸씩 밀어넣는 시행을 생각한다. (가장 오른쪽에 있던 칸을 맨 왼쪽으로 옮긴다) 이런 “슬라이딩” 시행을 통해 얻게되는 새로운 configuration을 원래 configuration과 동치관계가 되도록 한다. 그러면 앞에서와 비슷한 논의에 의해, 한 행에 대해서 $p$ 번 슬라이딩해서 원래대로 돌아오는 동안 $p$ 개의 서로 다른 configuration들을 얻게 된다. 따라서 동치류의 원소의 개수는 $p^k$ 개로 $p^2$ 의 배수가 됨을 알 수 있어 그들의 합 역시 $p^2$ 의 배수가 되므로 증명이 끝난다.

실은 mod $p^3$ 으로도 성립하는 합동식으로, Wolstenholme’s theorem이라 불린다. 만약 이걸 위와 같은 아이디어를 이용해서 증명하려면 불완전한 행이 2개 이상인 경우의 수가 $p^3$ 의 배수임을 보여야하는데, 결국 $k=2$ 에 해당하는 경우의 수가 $p^3$ 의 배수임을 보이게 되어 $a=2, b=1$ 인 경우로 귀결된다. 그러나 여기에서 바로 직접적인 조합적인 증명을 찾기는 힘들어보임.

앞서 봤던 합동식은 곧 $\binom{ap}{bp} \equiv \binom{a}{b}\text{ (mod }p\text{)}$ 를 의미하는데, 조금 더 나아가면 $0 \leq c,d < p$ 에 대해 $\binom{ap+c}{bp+d} \equiv \binom{a}{b}\binom{c}{d}\text{ (mod }p\text{)}$ 가 성립함을 알 수 있다. 이는 앞서 본 것처럼 $a \times p$ 개의 칸들과 별도의 $c$ 개의 칸들로 총 $ap+c$ 개의 칸들 중 $bp+d$ 개를 택해서 칠하고 똑같이 동치관계를 설정함으로써 ( $c$ 개의 칸은 딱히 슬라이드 같은 시행을 생각하지 않고 그대로 놔둔다) 얻을 수 있다. 이 결과물을 이용하면, $a,b$ 를 각각 $p$ 진법으로 쓰면 $(a_k a_{k-1} \cdots a_0), (b_k b_{k-1} \cdots b_0)$ 이 된다고 할 때, (즉 $a=\sum_{i=0}^k a_ip^k, b=\sum_{i=0}^k b_ip^k$ ) $\binom{a}{b} \equiv \binom{a_k}{b_k} \cdots \binom{a_0}{b_0}$ 이 된다는 Lucas’ theorem 역시 얻을 수 있게 된다.

한 편 앞서 언급한 Petersen은 페르마의 소정리와 더불어 정수론 기초에서 배우는 항등식 중 하나인 윌슨의 정리 역시 조합적으로 증명했다. 윌슨의 정리는 소수 $p$ 에 대해 $(p-1)! \equiv 1\text{ (mod }p\text{)}$ 이 성립한다는 것. 이를 증명하기 위해 $S_p$ 의 원소들, 즉 $p$ 개짜리 순열들을 생각한다. 이들 중 cyclic 순열, 즉 cycle이 길이 $p$ 인 것 1개뿐인 순열은 $(p-1)!$ 개 존재한다. 여기서 순환군 $C_p$ 의 group action을 단순히 합성하는 식으로 생각한다. 즉 $(a_1, a_2, \ldots, a_p)$ 와 $(a_2, a_3 ,\ldots, a_p, a_1)$ 이 동치관계를 갖는다고 생각. 그러면 $w(i) \equiv i+k$ ( $0<k<p$ )꼴의 $p-1$ 개의 순열들을 제외하면 모두 동치류가 $p$ 개의 원소를 갖게 되므로 $(p-1)! \equiv p-1$ 이 성립하게 된다.