回覆 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)
