Bài viết đã được chỉnh sửa nội dung bởi Nguyen Lam Thinh: 16-12-2012 - 21:16
$C_{{p^r}}^p \equiv {p^{r - 1}}(\bmod {p^r})$
Bắt đầu bởi dactai10a1, 14-11-2012 - 19:29
#1
Đã gửi 14-11-2012 - 19:29
Chứng minh rằng: $$C_{{p^r}}^p \equiv {p^{r - 1}}(\bmod {p^r})$$
#2
Đã gửi 14-11-2012 - 20:47
Giải như sau:CMR $C_{{p^r}}^p \equiv {p^{r - 1}}(\bmod {p^r})$
Ta cần cm $C_{p^r}^p-p^{r-1} \vdots p^r$
$\Leftrightarrow \dfrac{(p^r)!}{p!(p^r-p)!}-p^{r-1} \vdots p^r$
$\Leftrightarrow \dfrac{(p^r)!-p^{r-1}p!(p^r-p)!}{p!(p^r-p)!p^r} \in \mathbb{Z}$
Hay $v_p((p^r)!-p^{r-1}p!(p^r-p)!)\geq v_p(p!(p^r-p)!p^r)$
Xét $v_p(p!(p^r-p)!p^r)=v_p(p!)+v_p((p^r-p)!)+v_p(p^r)=v_p(p!)+v_p((p^r-p)!)+r$
Ta có $v_p(p!)=\left\lfloor\dfrac{p}{p}\right\rfloor=1$
$p^{r-1}<p^r-p<p^r$ nên $v_p((p^r-p)!)=\left\lfloor\dfrac{p^r-p}{p}\right\rfloor+\left\lfloor\dfrac{p^r-p}{p^2}\right\rfloor+...+\left\lfloor\dfrac{p^r-p}{p^{r-1}}\right\rfloor=\sum{i=1}^{r-1}{\left\lfloor\dfrac{p^r-p}{p^i}\right\rfloor}=\sum{i=1}^{r-1}{\left\lfloor\dfrac{p^r-p^i+p^i-p}{p^i}\right\rfloor}=\sum{i=1}^{r-1}{\left\lfloor\dfrac{p^r-p^i}{p^i}+\dfrac{p^i-p}{p^i}\right\rfloor}=\sum{i=1}^{r-1}{\left\lfloor p^{r-i}-1+\dfrac{p^i-p}{p^i}\right\rfloor}=\sum{i=1}^{r-1}{p^{r-i}-1}+\sum{i=1}^{r-1}{\left\lfloor\dfrac{p^i-p}{p^i}\right\rfloor}=\sum{i=1}^{r-1}{p^{r-i}-1}=p^{r-1}+...+p-(r-1)=p^{r-1}+...+p+1-r=\dfrac{p^r-1}{p-1}-r$
Do đó $v_p(p!(p^r-p)!p^r)=1+\dfrac{p^r-1}{p-1}-r+r=\dfrac{p^r-1}{p-1}+1=\dfrac{p^r-p}{p-1}$
Giờ ta xét $v_p((p^r)!-p^{r-1}p!(p^r-p)!)$
Ta thấy $v_p((p^r)!)=\left\lfloor\dfrac{p^r}{p}\right\rfloor+\left\lfloor\dfrac{p^r}{p^2}\right\rfloor+...+\left\lfloor\dfrac{p^r}{p^r}\right\rfloor=p^{r-1}+...+1=\dfrac{p^r-1}{p-1}$
Xét $v_p(p^{r-1}p!(p^r-p)!)=v_p(p^{r-1})+v_p(p!)+v_p((p^r-p)!)=r-1+1+v_p((p^r-p)!)$
Theo trên $v_p((p^r-p)!)=\dfrac{p^r-1}{p-1}-r$ suy ra $v_p(p^{r-1}p!(p^r-p)!)=r-1+1+\dfrac{p^r-1}{p-1}-r=\dfrac{p^r-1}{p-1}$
Như vậy $v_p(p^{r-1}p!(p^r-p)!)\geq \dfrac{p^r-1}{p-1}$
Hiển nhiên $\dfrac{p^r-1}{p-1}>\dfrac{p^r-p}{p-1}$ nên $v_p(TS)>v_p(MS)$ nên có $đpcm$
Bài viết đã được chỉnh sửa nội dung bởi Nguyen Lam Thinh: 16-12-2012 - 21:16
- perfectstrong, hxthanh, BlackSelena và 6 người khác yêu thích
#3
Đã gửi 05-12-2012 - 23:06
Đây là một bài toán không quá khó để phải dùng đến các kiến thức về số ${v_p}$ như vậy.CMR: $C_{{p^r}}^p \equiv {p^{r - 1}}(\bmod {p^r})$
Lời giải:
Áp dụng công thức $kC_{n}^k =nC_{k-1}^{n-1}$, ta được:
$$C_{p^r}^p - p^{r-1}= p^{r-1} \left ( C_{p^r-1}^{p-1} -1 \right )$$
Từ đó, ta chỉ cần chứng minh:
$$C_{p^r-1}^{p-1} \equiv 1 (mod p) (*)$$
Nhưng đây chỉ là một hệ quả của định lí Lucas.
Remark: Ta có thể chứng minh một bổ đề khác mạnh hơn $(*)$ như sau:
Cho số nguyên tố $p$ và các số tự nhiên $k,a$, trong đó $0 \le a \le p^{k-1}$.
Chứng minh: $C_{p^{k-1}}^{a} \equiv (-1)^a ( mod p)$
Và bổ đề trên cũng chỉ là 1 hệ quả của định lí Lucas
Bài viết đã được chỉnh sửa nội dung bởi Nguyen Lam Thinh: 16-12-2012 - 21:15
- perfectstrong, nguyenta98 và thaicuchuoi thích
$P_{G}(\sigma_{1},\sigma_{2},\cdots,\sigma_{n})=\frac{1}{|G|}\sum_{\tau\in G}ind(\tau)$
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh