SENSEI AI
About App

(1) 素数 $p$ と $1 \le r \le p-1$ なる整数 $r$ に対して、二項係数に関する等式 $r \cdot {}_pC_r = p \cdot {}_{p-1}C_{r-1}$ が成り立つことを示し、また、${}_pC_r$ が $p$ の倍数であることを示す。 (2) 素数 $p$ に対して $2^p$ を $p$ で割った余りを求める。

数論二項係数素数フェルマーの小定理合同式
2025/3/28

1. 問題の内容

(1) 素数 pp と 1≤r≤p−11 \le r \le p-1 なる整数 rr に対して、二項係数に関する等式 r⋅pCr=p⋅p−1Cr−1r \cdot {}_pC_r = p \cdot {}_{p-1}C_{r-1} が成り立つことを示し、また、pCr{}_pC_r が pp の倍数であることを示す。
(2) 素数 pp に対して 2p2^p を pp で割った余りを求める。

2. 解き方の手順

(1)
まず、nCk=n!k!(n−k)!{}_nC_k = \frac{n!}{k!(n-k)!} であることを利用して、与えられた等式の左辺と右辺を計算する。
左辺：
r⋅pCr=r⋅p!r!(p−r)!=r⋅p⋅(p−1)!r⋅(r−1)!(p−r)!=p⋅(p−1)!(r−1)!(p−r)!r \cdot {}_pC_r = r \cdot \frac{p!}{r!(p-r)!} = r \cdot \frac{p \cdot (p-1)!}{r \cdot (r-1)! (p-r)!} = p \cdot \frac{(p-1)!}{(r-1)!(p-r)!}
右辺：
p⋅p−1Cr−1=p⋅(p−1)!(r−1)!((p−1)−(r−1))!=p⋅(p−1)!(r−1)!(p−r)!p \cdot {}_{p-1}C_{r-1} = p \cdot \frac{(p-1)!}{(r-1)!((p-1)-(r-1))!} = p \cdot \frac{(p-1)!}{(r-1)!(p-r)!}
したがって、r⋅pCr=p⋅p−1Cr−1r \cdot {}_pC_r = p \cdot {}_{p-1}C_{r-1} が成り立つ。
次に、pCr=pr⋅p−1Cr−1{}_pC_r = \frac{p}{r} \cdot {}_{p-1}C_{r-1} であるから、r⋅pCr=p⋅p−1Cr−1r \cdot {}_pC_r = p \cdot {}_{p-1}C_{r-1} を pCr=pr⋅p−1Cr−1{}_pC_r = \frac{p}{r} \cdot {}_{p-1}C_{r-1} と変形できる。
ここで、pCr{}_pC_r は整数であり、1≤r≤p−11 \le r \le p-1 より、rr は pp と互いに素である。
したがって、pCr{}_pC_r が整数であるためには、p⋅p−1Cr−1p \cdot {}_{p-1}C_{r-1} が rr で割り切れなければならないが、pp と rr は互いに素なので、p−1Cr−1{}_{p-1}C_{r-1} が rr で割り切れなければならない。
しかし、pCr=p!r!(p−r)!{}_pC_r = \frac{p!}{r!(p-r)!} と表せるので、pCr{}_pC_r は整数である。
ここで、r⋅pCr=p⋅p−1Cr−1r \cdot {}_pC_r = p \cdot {}_{p-1}C_{r-1} より、pCr=p⋅p−1Cr−1r{}_pC_r = \frac{p \cdot {}_{p-1}C_{r-1}}{r} が得られる。pCr{}_pC_r が整数なので、rr は p⋅p−1Cr−1p \cdot {}_{p-1}C_{r-1} を割り切る。rr は pp と互いに素であるから、rr は p−1Cr−1{}_{p-1}C_{r-1} を割り切る。つまり、rr は p−1Cr−1{}_{p-1}C_{r-1} の約数である。
r⋅pCr=p⋅p−1Cr−1r \cdot {}_pC_r = p \cdot {}_{p-1}C_{r-1} であるので、pCr=pr⋅p−1Cr−1{}_pC_r = \frac{p}{r} \cdot {}_{p-1}C_{r-1} と変形できる。
pCr{}_pC_rは整数なので、p⋅p−1Cr−1p \cdot {}_{p-1}C_{r-1}はrrで割り切れる。ppは素数であり、1≤r≤p−11 \le r \le p-1より、ppはrrを割り切らないので、p−1Cr−1{}_{p-1}C_{r-1}がrrで割り切れる。
r⋅pCr=p⋅p−1Cr−1r \cdot {}_pC_r = p \cdot {}_{p-1}C_{r-1} より、p⋅p−1Cr−1p \cdot {}_{p-1}C_{r-1} は rr の倍数である。
ここで、pp は素数なので、pp と rr は互いに素である。
したがって、pCr{}_pC_r は pp の倍数である。
(2)
フェルマーの小定理より、素数 pp に対して、2p≡2(modp)2^p \equiv 2 \pmod{p} である。
したがって、2p2^p を pp で割った余りは 22 である。

3. 最終的な答え

(1) r⋅pCr=p⋅p−1Cr−1r \cdot {}_pC_r = p \cdot {}_{p-1}C_{r-1} が成り立つことと、pCr{}_pC_r が pp の倍数であることは上記参照。
(2) 22

「数論」の関連問題

自然数Nを3進法で表すと4桁の数 $1ab1_{(3)}$ となり、5進法で表すと3桁の数 $a0b_{(5)}$ となる。 このとき、$a$, $b$, $N$ を求める。

進法整数方程式解法
2025/4/3

次の2つの不定方程式の整数解をすべて求める問題です。 (1) $3x - 5y = 1$ (2) $75x + 64y = 1$

不定方程式整数解ユークリッドの互除法
2025/4/2

$n > 1$ のとき、$n^7 - n$ が42で割り切れることを示す問題です。

整数の性質合同式因数分解フェルマーの小定理
2025/3/31

$n > 1$ のとき、$n^7 - n$ が $42$ で割り切れることを示す問題です。

整数の性質割り算因数分解フェルマーの小定理
2025/3/31

$n$ を自然数とするとき、「$n$ が 3 の倍数ならば $n^2$ も 3 の倍数となる」という命題の逆と裏の真偽を判定し、正しい組み合わせを選ぶ問題です。

命題真偽倍数整数の性質対偶
2025/3/31

自然数 $n$ に対して、「$n$ が 3 の倍数ならば、$n^2$ も 3 の倍数となる」という命題がある。この命題の逆と裏の真偽を判定し、正しい組み合わせを選択する。

命題真偽倍数対偶逆裏
2025/3/31

$n$ を自然数とし、$1$ から $n$ までの異なる $n$ 個の自然数からなる集合を $N$ とする。$N$ の2つの部分集合 $P_1, P_2$ は $P_1 \cap P_2 = \emp...

集合部分集合和整数の性質合同式
2025/3/30

最大公約数が4, 最小公倍数が84であるような2つの自然数の組をすべて求める問題です。

最大公約数最小公倍数整数の性質互いに素
2025/3/30

与えられた数 $0, 30, \sqrt{30}$ のうち、有理数はどれかを選択する問題です。

有理数無理数数の分類
2025/3/30

(1) $-28$ を $3$ で割ったときの余りを求めよ。 (2) $a, b$ は整数で、$a$ を $8$ で割ると $3$ 余り、$b$ を $8$ で割ると $6$ 余る。このとき、$3a^...

剰余合同式末尾の0素因数分解フェルマーの小定理
2025/3/30