어떤 이항계수 nCr(n,r)을 소수 p로 나눈 나머지는 n과 r을 p^i로 나눈 나머지 ni, ri에 대한 이항계수 nCr(ni,ri)의 곱을 p로 나눈 나머지와 같다. (단, ni<ri이면 이항계수의 값은 0이라고 한다.)
다르게 말하면 p진수 n과 r에 대한 이항계수의 1의 자리는 각 자릿수에 대한 이항계수의 곱과 같다.
예를 들어, 3진수의 이항계수 nCr(21122,10021)를 3으로 나눈 나머지는 nCr(2,1) nCr(1,0) nCr(1,0) nCr(2,2) nCr(2,1) 곱인 4를 3으로 나눈 나머지 1과 같다.
p=2일 때, nCr 값은 nCr(0,1)을 제외하면 모두 1이므로 각 자릿수의 크기를 비교하는 문제로 바뀌어 쉽게 해결가능하다. bitwise and연산 한번만으로 판단가능해지는 아주 간단한 문제로 바뀐다.
