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

お題への解答

q : 素数, n, m : 整数 のとき、
\left(\begin{array}{c}q^m\\n\end{\array}\right)\equiv0\pmod{q}
を示せ。0 < n < q^m とします。

逆にした方が分かり易いんじゃないでしょうか.

証明

Z/qZ上で, 恒等式(x + y)^{q^m}=x^{q^m} + y^{q^m}が成立すれば題意が言える.

まずZ/qZで(x + y)^q = x^q + y^qを示す.
これは割と簡単に言えて, x^a y^{q-a}の係数は\left(\begin{array}{c}q\\a\end{\array}\right). 0 < a < qについて\left(\begin{array}{c}q\\a\end{\array}\right)\equiv0\pmod{q}となるのでOK.
(\binom{q}{a} = q (\binom{q-1}{a-1}/a). \binom{q}{a}が整数なこととqが素数であることより, 括弧内は整数. よって, 言える.)

次に, mに関する帰納法を使う. m=1の場合は上より言える.
(x + y)^{q^m} = ((x + y)^{q^{m-1}})^q
 = (x^{q^{m-1}} + y^{q^{m-1}})^q
 = (x^{q^{m-1}})^q + (y^{q^{m-1}})^q
 = x^{q^{m}} + y^{q^{m}}
となる.
よって帰納法より任意の自然数mについて言える.