『コンビネーションを使った素数判定』

【問題１】

（１）pを素数、kを自然数とする。
_p*k-1Ｃ_p-1-1はpで割り切れる事を示せ。

（２）（１）を利用して、_p*kＣ_p-kが、p*kで割り切れる事を示せ。

【問題２】

mをm≧3となるような自然数とする。

（１）mが素数ならば、
m
2 ≦h≦m-1となる様な任意の自然数hに対して、
_hＣ_m-hがhで割り切れる。

【ヒント】

じつは、mが素数のときは、m-hとhは互いに素になります。
証明も考えて見てください。

（２）mが合成数ならば、
m
2 ≦r≦m-1となるようなある自然数rに対して、
_rＣ_m-rがrで割り切れない。

【ヒント】

まず、m=p*h（pは素数、hは2以上の自然数）とおいて見てください。
問1より、pを素数、kを自然数とすると、
_p*kC_p-kがp*kで割り切れることが言えますね。
よって、_p*kC_pはp*kで割り切れないことが言えます。
この問題も、このような論法で示せます。

【問題３】

mをm≧4となるような自然数とする。

（１）mが素数ならば、
m
3 ≦h≦ m
2 となる様な任意の自然数hに対して、
_hＣ_m-2*hがhで割り切れる。

【ヒント】

これも、mが素数のとき、m-2*hとhが互いに素になります。

（２）mが合成数ならば、
m
3 ≦r≦ m
2 となる様な任意の自然数rに対して、
_rＣ_m-2*hがrで割り切れない。

【ヒント１】

n、rをn＞r＞0となるような自然数とすると、

r*(_nＣ_r)=n*(_n-1Ｃ_r-1)となる。

【ヒント２】

mが奇数か偶数かで場合分けが必要。
mが奇数のとき、問題２の(2)の証明と同様なことが言えます。