数ならぬ

理学系のこと、特に数学について書きます。雑学的な知識もまとめていく所存。

ₚCₖの合同式とフェルマーの小定理

　有名な事実ではあるが、次のような定理が成り立つ。

${}_pC_k$ の整除性

$p$ を素数としたとき、 ${}_pC_k$ は $0< k < p$ を満たせば $p$ の倍数である

$Proof$

$0< k < p$ のとき、 ${}_pC_k=\dfrac{p(p-1)(p-2)\cdots (p-k+1)}{k(k-1)(k-2)\cdots 2\cdot 1}$ と展開できる。分子は $p$ の倍数である。ここで分母に着目する。これは $k < p$ であることから $p$ の倍数ではない。よって分子の $p$ はキャンセルされずに残るので、 ${}_pC_k$ は $p$ の倍数 $◽︎$

　この定理によって次のような合同式が成り立つことが分かる。

一年生の夢

$p$ を素数とする。このとき、 $(x+y)^p\equiv x^p+y^p \hspace{1mm}(mod\hspace{1mm}p)$

$Proof$

二項定理より、 $(x+y)^p=$ $\displaystyle\sum_{k=0}^p {}_pC_k x^ky^{p-k}\equiv$ $x^p+y^p\hspace{1mm}(mod\hspace{1mm}p)$ $◽︎$

　この定理の系として、次の有用な定理が得られる。

フェルマーの小定理

$p$ を素数とすると、 $a^p\equiv a\hspace{1mm}(mod\hspace{1mm}p)$

$Proof$

題意は数学的帰納法によって示される。 $a=0$ のとき、自明に正しい。 $a=n$ で正しいとして $a=n+1$ の時を示す。先ほど示した定理によって、

$(n+1)^p\equiv n^p+1\hspace{1mm}(mod\hspace{1mm}p)$

が成り立つことが分かる。ここで、帰納法の仮定により、

$n^p\equiv n\hspace{1mm}(mod\hspace{1mm}p)$

が成り立つので、

$(n+1)^p\equiv n+1\hspace{1mm}(mod\hspace{1mm}p)$

が成り立ち、これにより帰納法が回る $◽︎$

　よく見る形は次のようになっている。

フェルマーの小定理

$a$ を $p$ の倍数ではない整数とする。このとき $a^{p-1}\equiv 1\hspace{1mm}(mod\hspace{1mm}p)$

　この系は先ほどの形と $a$ が $p$ の倍数ではないときに合同式の割り算ができるという定理から導かれる。