今日のお題 - 186 @ hatenablog

p:素数, p|nとする. $\left(\begin{array}{c}n\\p\end{\array}\right)\equiv\frac{n}{p}\pmod{n}$ を示せ.
某講義ノートに証明無しで書かれていて困った.

p≠nは必要ない. イコールの場合は両辺ともに1なので問題なし

Hさんの解答

$\left(\begin{array}{c}n\\p\end{\array}\right) = \frac{n}{p} \cdot \frac{n-1}{p-1} \cdot\cdot\cdot \frac{n-p+1}{1}$ である.
もしpがnの最小の素因数であれば, 右側のn/p以外の項の分子からnを除いても良い (modulo nで考えているから). 従って右側= $\frac{n}{p} (-1)^{p-1}$ である. pが奇素数の場合は $\frac{n}{p} (-1)^{p-1} \equiv \frac{n}{p} \bmod{n}$ . (pが2の場合はどうしよう.) これで示せた.

他研究室4回生の解答

$A=\frac{n-1}{p-1} \cdot\cdot\cdot \frac{n-p+1}{1}$ を考える. A=ap+1と書けたとすると, $\frac{n}{p}A=an+\frac{n}{p}$ となるので, modulo nで考えれば, n/pと等しい.
なので, AをZ/pZで考える. すると, 分子も分母もZ/pZ中の0以外の要素が全て出現している. よって, AはZ/pZ中で1になるので, A=ap+1と書ける.

ちょっとだけ補足

割り算しているので微妙に議論が必要です. 整数の世界で割り算してからmoduloを取っている点に注意.
実際には, 0<i<pについて, $ki/i\equiv kii^{-1} \bmod{p}$ が成立しているので上の議論でOK. Hさんの解答ではpが最小の素因数である必要があります. 1〜p-1に法nでの逆元が必要だからです.