pＣrがpで割り切れる理由と「pとrが互いに素である」とは

「pを素数とし、整数rが1≦r≦p-1を満たすとき、pＣrがpで割り切れることを示せ」という問題に対して、重要なポイントが「pとrは互いに素である」という条件です。この意味がわからない方も多いと思いますので、この記事ではその解説と、pＣrがpで割り切れる理由をわかりやすく説明します。

「pとrが互いに素である」とは？

「pとrが互いに素である」とは、pとrの最大公約数（gcd）が1であることを意味します。つまり、pとrが共通の因数を持たないということです。

この条件が重要な理由は、pが素数であるため、rがpと共通の因数を持たない場合、pがrを割り切らないことが確定するからです。このことが後の証明において大きな役割を果たします。

問題の「pＣr」について、まずpＣrは組み合わせの式であり、次のように定義されます。

pＣr = p! / (r!(p-r)!)

ここでp!はpの階乗を示し、p! = p × (p-1) × … × 2 × 1のように、pまでのすべての整数の積です。同様にr!と(p-r)!もそれぞれの階乗を示します。

この式の中で重要なのは、p!（pの階乗）にpが含まれているという点です。pが素数であるため、p!は必ずpで割り切れます。そのため、pＣrの計算式ではp!がpで割り切れるため、最終的にpＣrもpで割り切れることがわかります。

具体的な例を考えてみましょう。p = 5, r = 2の場合、pＣrは次のように計算されます。

5Ｃ2 = 5! / (2!(5-2)!) = (5 × 4 × 3 × 2 × 1) / (2 × 1 × 3 × 2 × 1) = 10

この場合、10は5で割り切れるため、pＣrがpで割り切れることが確認できます。したがって、p = 5の場合、pＣrはpで割り切れることがわかります。

「pとrが互いに素である」とは、pとrの最大公約数が1であることを意味し、この条件を満たすことで、pＣrがpで割り切れることが証明できます。pが素数であるとき、組み合わせの式pＣrではp!がpで割り切れるため、最終的にpＣrもpで割り切れることがわかります。これにより、問題の解答が導かれます。