読者です 読者をやめる 読者になる 読者になる

今日のお題

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での逆元が必要だからです.