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

◆福岡県　田楽　さんからの解答。

【問題１】

（１）

pk-1Cp-1
= (pk-1)(pk-2)・・・(pk-p+1)
(p-1)!
≡ (-1)(-2)・・・(-p+1)
(p-1)!		　mod p
≡ (1)(2)・・・(p-1)
(p-1)!		　mod p
≡ (p-1)!
(p-1)!		　mod p
≡1　mod p

よって、pk-1Cp-1-1≡0　mod p

（２）

pkCp-k
= pk
p		・pk-1Cp-1-k
= kpk-1Cp-1-k
=k( pk-1Cp-1 -1)
≡0　mod pk
(∵（１）よりpk-1Cp-1-1≡0　mod p)

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

　数学の部屋へもどる