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$ 만이 가능해 모순이 된다. 따라서 답은 ‘불가능’이다.