pCkがpの倍数であることとフェルマーの小定理

上野竜生です。入試定番問題の１つである_pC_kがpの倍数証明問題とフェルマーの小定理に関することを紹介します。pは素数とします。

pが素数ならば_pC_kはpの倍数（1≦k≦p-1）である。

証明は割と入試頻出です。丸暗記でもいいぐらいでしょう。

[証明]

_pC_k=Nとおく。すると

よって\(k _pC_k = p _{p-1}C_{k-1} \)

_p-1C_k-1は整数だから右辺はpの倍数

1≦k≦p-1よりkとpは互いに素だから_pC_kはpの倍数である。

n^pをpで割った余りはnをpで割った余りに等しい

つまりn^p-nがpの倍数であることを証明すれば良い。

[証明]数学的帰納法

n=1のとき明らか（1^p-1=0はpの倍数）

n=kで成立すると仮定する。するとn=k+1のとき

_pC_k（1≦k≦p-1)はpの倍数であり，k^p-kは帰納法の仮定よりpの倍数だから(k+1)^p-(k+1)もpの倍数

よってn=k+1のときも成立し，数学的帰納法よりすべての自然数nに対し成立。

nとpが互いに素ならばn^p-1をpで割った余りは1　（フェルマーの小定理）

[証明]

n^p-1をpで割った余りをaとする。すると両辺をn倍すると

n^pをpで割った余りはanをpで割った余りと等しい。しかし先ほど示した命題よりn^pをpで割った余りはnをpで割った余りと等しい。

よってanをpで割ったあまりとnをpで割った余りは等しい。

つまりan-n=n(a-1)はpの倍数。nとpは互いに素だからa-1がpの倍数。

aはpで割った余りだから0≦a≦p-1であり-1≦a-1≦p-2だからa-1=0しかない。

よってa=1

応用問題