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

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

먼저, 소수 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이 성립하게 된다.

Elegant Math 계정에서 작성한 트윗 타래트윗 타래를 정리. (2016/09/11, 2016/09/10)

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중