Cho
$$S={2007 \choose 0} + {2007 \choose 3} + \cdots + {2007 \choose 2007}$$
Hãy tính $S\!\!\!\! \!\pmod{\!\!1000}$
========
OP tại :
https://artofproblem...c20073c20072007
$$S={2007 \choose 0} + {2007 \choose 3} + \cdots + {2007 \choose 2007}$$ Hãy tính $S\!\! \pmod{1000}$
Bắt đầu bởi Nobodyv3, 07-02-2024 - 22:50
#2
Đã gửi 08-02-2024 - 07:01
Nobodyv3
-
- Thành viên
-
- 942 Bài viết
Generating Functions Faithful
Xét đa thức $G(x)=(1+x)^{2007}$. Gọi $\omega=e ^{2\pi i/3}$ là 1 nghiệm của phương trình $x^3=1$ thì theo định lý RUF ta có :
$$\begin {align*}
S &=\frac {2^{2007}+(1+\omega )^{2007} +(1+\omega ^2)^{2007} }{3}\\
&=\frac {2^{2007}-2}{3}
\end {align*}$$Ta thấy $1000=2^3\times 5^3$ mà $2^{2007} \equiv 0\!\! \pmod{2^3}$ và $2^{2007} \equiv 2^7\equiv 3\!\! \pmod{5^3}$. Suy ra :
$2^{2007}\equiv 128\!\!\pmod {1000}$ nên :
$2^{2007}-2\equiv 126\!\!\pmod {1000}$
Nhận thấy $gcd(3,1000)=1$ nên $3^{-1}\equiv 667\!\!\pmod {1000}$
Do đó :
$$\begin {align*}
S=\frac {2^{2007}-2}{3}&\equiv 667\times (2^{2007}-2)\\
&\equiv 667\times126\\
&\equiv 042\!\!\pmod {1000}
\end {align*}$$Vậy số dư là $ \boldsymbol {042}$
$$\begin {align*}
S &=\frac {2^{2007}+(1+\omega )^{2007} +(1+\omega ^2)^{2007} }{3}\\
&=\frac {2^{2007}-2}{3}
\end {align*}$$Ta thấy $1000=2^3\times 5^3$ mà $2^{2007} \equiv 0\!\! \pmod{2^3}$ và $2^{2007} \equiv 2^7\equiv 3\!\! \pmod{5^3}$. Suy ra :
$2^{2007}\equiv 128\!\!\pmod {1000}$ nên :
$2^{2007}-2\equiv 126\!\!\pmod {1000}$
Nhận thấy $gcd(3,1000)=1$ nên $3^{-1}\equiv 667\!\!\pmod {1000}$
Do đó :
$$\begin {align*}
S=\frac {2^{2007}-2}{3}&\equiv 667\times (2^{2007}-2)\\
&\equiv 667\times126\\
&\equiv 042\!\!\pmod {1000}
\end {align*}$$Vậy số dư là $ \boldsymbol {042}$
===========
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh
