標題: 餘數問題 [打印本頁]

---

作者: 耳東陳    時間: 2025-10-30 13:53     標題: 餘數問題

求\(\displaystyle \sum_{0\le i<j\le60}C_i^{60}C_j^{60}\)被31除的餘數。

114.12.6
題目重新打字，將圖片刪除。

---

作者: tsusy    時間: 2025-10-30 18:22     標題: 回覆 1# 耳東陳 的帖子

令 \( n=60 \)

考慮 \( f(x)=\left(\sum_{k=0}^{n}C_{k}^{n}x^{k}\right)\left(\sum_{k=0}^{n}C_{k}^{k}x^{k}\right)=(1+x)^{n}(1+x)^{n}=(1+x)^{2n} \)

\( 2^{2n}=f(1)=\sum_{\underset{i\neq j}{0\leq i,j\leq n}}C_{i}^{n}C_{j}^{n}+\sum_{k=0}^{n}(C_{k}^{n})^{2} \)

其中 \( \sum_{k=0}^{n}(C_{k}^{n})^{2}=\sum_{k=0}^{n}(C_{k}^{n}C_{n-k}^{n}) 為 (1+x)^{n}(1+x)^{n} \) 展開式中 \( x^{n} \) 項係數

故 \( \sum_{k=0}^{n}(C_{k}^{n})^{2}=C_{n}^{2n} \)

因此 \( \sum_{\underset{i<j}{0\leq i,j\leq n}}C_{i}^{n}C_{j}^{n}=\frac{2^{2n}-C_{n}^{2n}}{2} \)

其中 \( \frac{1}{2}C_{60}^{120} \) 被 31 整除 (31 是質數，\( \frac{120!}{60!60!} \) 中，分子有 \( 31\cdot62\cdot93 \)，分母有 \( 31^{2}) \)

故所求餘數與 \( 2^{119} \) 除以 31 的餘數相同，並注意到 \( 2^{5}=31+1 \)

因此 \( 2^{119}\equiv2^{4}\equiv16 \) (mod 31)

---

作者: 耳東陳    時間: 2025-10-31 16:01     標題: 回覆 2# tsusy 的帖子

謝謝

---

歡迎光臨 Math Pro 數學補給站 (https://math.pro/db/)

論壇程式使用 Discuz! 6.1.0