[数论] 求$C_{2n}^1,C_{2n}^3,C_{2n}^5,\cdots,C_{2n}^{2n-1}$的最大公因数

isee

求$C_{2n}^1,C_{2n}^3,C_{2n}^5,\cdots,C_{2n}^{2n-1}$的最大公因数。

tommywong

$n=2^m q,(2,q)=1$

结果好像是$(C_{2n}^1,C_{2n}^3,C_{2n}^5,\dots,C_{2n}^{2n-1})=2^{m+1}$

$C_{2n}^1=2n=2^{m+1}q$

$(C_{2n}^1,C_{2n}^3,C_{2n}^5,\dots,C_{2n}^{2n-1})|2^{m+1} q$

$C_{2n}^{2k+1}=\frac{2n}{2k+1}C_{2n-1}^{2k}=2^{m+1}\frac{qC_{2n-1}^{2k}}{2k+1}$

$2^{m+1}|C_{2n}^{2k+1}$

$2^{m+1}|(C_{2n}^1,C_{2n}^3,C_{2n}^5,\dots,C_{2n}^{2n-1})$

如果有一个$C_{2n}^{2k+1}$与q互质，那就会取等

tommywong

设叔叔$p>2,p^h||q,2n=\sum_{r\ge h}a_r p^r,a_h\neq 0$

由卢卡斯定理，$C_{2n}^{p^h}\equiv (\prod_{0\le r<h}C_0^0) (C_{a_h}^1)(\prod_{r>h}C_{a_r}^0)\equiv a_h\pmod{p}$

$p^h$与$C_{2n}^{p^h}$互质

isee

$n=2^m q,(2,q)=1$

结果好像是$(C_{2n}^1,C_{2n}^3,C_{2n}^5,\dots,C_{2n}^{2n-1})=2^{m+1}$

$C_{2n}^1=2 ...
tommywong 发表于 2017-10-7 21:37

厉害厉害，以我的水平只是对“答案”：结果完全正确。