二項係数C[n,k]=n!/(k!(n-k)!)で定義します。
C[70,35]を71で割ったときのあまりは、
(70×69×・・・×36)/(35×34×・・・×1)
≡((-1)×(-2)×・・・×(-35))/(35×34×・・・×1)(mod 71)
＝-1(mod 71)
よりあまりは70
これは正しいのですが、
C[80,40]を81で割ったときのあまりは
(80×79×・・・×41)/(40×39×・・・×1)
≡((-1)×(-2)×・・・×(-40))/(40×39×・・・×1)(mod 81)
＝1(mod 81)
よりあまりは1
これは正しくありません。
おそらく71は素数で、81は素数ではないからだと思うのですが、
C[80,40]を81で割ったときのあまりの求め方を教えてください。、
|
No.83112 - 2022/08/09(Tue) 23:28:17
| ☆ Re: あまり / らすかる | | | とりあえず以下のようにすれば正しい答えが出るようですが、
理論的な裏付けはありませんし、他の場合でも正しい答えが
出るかどうかはわかりません。
80,79,78,…,41と40,39,38,…,1のうち81と互いに素であるものは
80,79,77,76,74,…,41と40,38,37,35,…,1の13項ずつ
これを上と同じように(-1),(-2)のようにすると奇数個なので結果は-1
残りの78,75,72,…,42と39,36,33,…,3をそれぞれ3で割ると
26,25,24,…,14と13,12,11,…,1
よって
C[80,40]≡-C[26,13]=-10400600≡-38≡43
となり余りは43
|
No.83115 - 2022/08/10(Wed) 11:59:33 |
| ☆ Re: あまり / 大西 | | | 互いに素であるものだけを考えれば良さそうなのですね。
らすかるさんありがとうございます。
|
No.83116 - 2022/08/10(Wed) 16:15:50 |
| ☆ Re: あまり / IT | | | 少し一般化してみました。
奇素数pの累乗q=p^m について,n=(q-1)/2とする。2n=q-1である。
C[2n,n]をqで割ったときの余りを計算する。
C[2n,n]=(2n*(2n-1)*...*(n+1))/(1*2*...*(n-1)*n)
1,2,...,n-1,nのうち
pの倍数を,1p,2p,...,kp. 積をa.
pの倍数でないものを順にs[1],s[2],...,s[n-k]。 積をb.
n+1,n+2,...,2n-1,2nのうち
pの倍数を(k+1)p,(k+2)p,...,2kp。 積をc.
pの倍数でないものはq-s[1],q-s[2],...,q-s[n-k]。 積をd
とする.
このときC[2n,n]=(cd)/(ab)=(d/b)(c/a)
c/a=(k+1)(k+2),...,2k/(1*2*...*k)=C[2k,k]:整数
よって、C[2n,n]=(d/b)C[2k,k]
∴bC[2n,n]=dC[2k,k]
ここで d=(q-s[1])(q-s[2]),....,(q-s[n-k])≡((-1)^(n-k))b (mod q) なので
bC[2n,n]≡((-1)^(n-k))bC[2k,k] (mod q)
bはqと互いに素なので
C[2n,n]≡((-1)^(n-k))C[2k,k] (mod q)
|
No.83145 - 2022/08/12(Fri) 12:30:34 |
|
