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

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

フェルマーの小定理

スポンサーリンク

pが素数ならばpCkはpの倍数(1≦k≦p-1)である。

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

[証明]

pCk=Nとおく。すると

\(_{p}C_{k}=\frac{p!}{(p-k)!k!}=\frac{p}{k}\frac{(p-1)!}{(p-k)!(k-1)!}=\frac{p}{k} {}_{p-1}C_{k-1} \)

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

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

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

単純にpCkを分数式で表した後,分子のpが約分せずに残るから・・・
という証明でも良さそうですがこの証明を書いてほしいような誘導があることも多いです。

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

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

[証明]数学的帰納法

n=1のとき明らか(1p-1=0はpの倍数)

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

\( (k+1)^p-(k+1) \\=_pC_0 k^p + _pC_1 k^{p-1}+ \cdots +_pC_{p-1} k+ _pC_p – (k+1) \\=_pC_1 k^{p-1}+\cdots +_pC_{p-1} k +(k^p-k)\)

pCk(1≦k≦p-1)はpの倍数であり,kp-kは帰納法の仮定よりpの倍数だから(k+1)p-(k+1)もpの倍数

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

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

[証明]

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

npをpで割った余りはanをpで割った余りと等しい。しかし先ほど示した命題よりnpを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

応用問題

771001を101で割った余りはいくらか?ただし101は素数である。

答えaをnで割った余りがbであることをa≡b(mod n)とかく。

フェルマーの小定理より77100≡1(mod 101)である。

よって771001≡(77100)10・771≡110・77≡77(mod 101)よって余りは77

余りは周期的だから1周期するまで計算すればいいのですがこの定理は1周期するまで実際に計算しなくても良くなるので便利です。

数学はもちろん他の科目も勉強できる「スタディサプリ」なら人気講師の授業動画で、塾にいかなくてもまるで塾にいったかのような勉強ができます。塾と比較すると格安で、しかも無料おためしもできます。当サイトオススメのサイトです。


スタディサプリについて解説したページはこちら
スポンサーリンク

シェアする

  • このエントリーをはてなブックマークに追加

フォローする