6k+1꼴 소수에 대한 문제

2010 USA IMO TST 9번 문제.

p=6k+1이 소수일 때, \binom{3k}{k} \equiv 1\text{ (mod }p\text{)}이 가능한가?

당시 IMO 대표 학생들이랑 미국 TST 문제들 같이 접하고 풀었었는데, 저 문제만 못 풀고 있었던 차 심지어 실제로 시험을 치른 미국 학생들 중 꽤 많은 학생들이 풀었다는 이야기를 들어서 더더욱 멘붕했던 기억이 있다. 나중에 결국 답을 전해들었는데 듣고나니 정말 납득이 가는 풀이였고 그래서 더욱 분했음.

\binom{n}{0}+\binom{n}{3}+\binom{n}{6}+\cdots 같은 값을 다룰 때 주로 쓰는 것이 roots of unity이다. 즉 \omega=e^{2\pi i/3}으로 잡으면 (1+1)^n+(1+\omega)^n+(1+\omega^2)^2을 이항정리했을 때 \binom{n}{0}(1+1+1)+\binom{n}{1}(1+\omega+\omega^2)+\binom{n}{2}(1+\omega^2+\omega^4)+\binom{n}{3}(1+\omega^3+\omega^6)+\cdots 이런 식으로 전개가 되는데, \binom{n}{3k}에 해당하는 항만 3이 곱해지고 나머지 이항계수는 0이 곱해지므로 \frac{1}{3}(2^n+(1+\omega)^n+(1+\omega^2)^n)이 되는 것.

이것을 mod p, 즉 \mathbb{Z}/p\mathbb{Z}에서 생각한다면, 앞에서 roots of unity에 해당하는 역할을 만들어야 하고 이를 위해 원시근(primitive root) g를 잡는다. 이 원시근은 order가 p-1인 원소로, 즉 g^{p-1} \equiv 1이지만 0<i<p-1에 대해 g^i \not \equiv 1인 원소를 뜻한다. 문제에서 관심있는 것은 \binom{3k}{k}이므로 k-th roots of unity를 잡는게 자연스럽고, g^6이 그 역할을 할 수 있다. (g^6+1)^{3k}+(g^{12}+1)^{3k}+\cdots+(g^{6k}+1)^{3k}를 앞에서처럼 전개하면 k(\binom{3k}{0}+\binom{3k}{k}+\binom{3k}{2k}+\binom{3k}{3k})와 합동이 되는데, 만약 \binom{3k}{k} \equiv 1이었다면 이 값은 4k가 된다. 그러나 mod p에서 무언가의 \frac{p-1}{2}=3k제곱은 0, 1, -1만 나올 수 있고 그런 값 k개를 더했다면 mod p=6k+1-k,-k+1,\ldots,-1,0,1,\ldots,k만이 가능해 모순이 된다. 따라서 답은 ‘불가능’이다.

개인적으론 비슷한 스킬을 미국 트레이닝 캠프에서 학생들에게 가르쳐주지 않았을까 하고 막연히 의리적 합심을……

답글 남기기

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

WordPress.com 로고

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

Google photo

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

Twitter 사진

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

Facebook 사진

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

%s에 연결하는 중