pを素数とする。1≦k≦p-1を満たす整数kに対して、二項係数p-1Ckをpで割ったときの余りを求め

pを素数とする。1≦k≦p-1を満たす整数kに対して、二項係数p-1Ckをpで割ったときの余りを求めよ。

わかりません。お願いします。

No.1 ベストアンサー 回答者： ゼロプライム 回答日時： 2019/07/07 18:04

ｐは素数。

１≦ｋ≦p-1を満たす整数ｋに対して、次の等式を考えます。

p-1Ck-1+p-1Ck＝pＣk…①

証明はしませんが、パスカルの三角形を考えてもらえば、すぐわかると思います。

①の右辺を考えます。
pCk=p(p-1)…(p-k+1)/k(k-1)…2・１
この式の右辺の分子は(p-k+1)からｐまでの連続するｋ個の自然数の積なので、分母の１からｋまでのどの自然数の倍数も必ず含んでいます(1の倍数、2の倍数、3の倍数、…、ｋの倍数)。したがって、必ず割り切れて、pCkは自然数になるわけです。ところで、分子のｐは素数なので割られずに残ります。(ｐ＞ｋですから、分母にｐはありません。)　ですから、pCkはｐの倍数になります。

では、p-1Ckを考えます。
ｋ=1のとき、p-1C1＝p-1　ｐで割った余りは、p-1です。
ｋ=2のとき、①の左辺は、p-1C1+p-1C2となりますが、p-1C１をｐで割った余りはp-1なので、①の左辺がｐの倍数になるためには、p-1C2をｐで割った余りは１となります。
k=3のとき、①の左辺は、p-1C2+p-1C3となりますが、p-1C２をpで割った余りは１なので、p-1C3をpで割った余りはp-1となります。

これを繰り返すことで、
ｋが奇数の時は、p-1Cｋをpで割った余りはp-1
ｋが偶数の時は、p-1Cｋをｐで割った余りは１
となります。