当サイトは、PRを含む場合があります。

上野竜生です。入試定番問題の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周期するまで実際に計算しなくても良くなるので便利です。

 

 

解説を読んで数学がわかった「つもり」になりましたか?数学は読んでいるうちはわかったつもりになりますが演習をこなさないと実力になりません。そのためには問題集で問題を解く練習も必要です。オススメの参考書を厳選しました

<高校数学> <大学数学> さらにオススメの塾、特にオンラインの塾についてまとめてみました。自分一人だけでは自信のない人はこちらも参考にすると成績が上がります。