Bài toán : Chứng minh rằng $C_p^k$ chia hết cho $p$ với $k=1,2,...,p-1$. Lời giải : Bổ đề : Với $p,q$ nguyên tố và $i$ là số nguyên dương, ta có $\left \lfloor \dfrac{p-1}{q^i} \right \rfloor=\left \lfloor \dfrac{p}{q^i} \right \rfloor$. Chứng minh bổ đề : Nếu $p-1<q^i\Rightarrow p\leq q^i$ mà vì $p,q$ nguyên tố nên có $p<q^i$, từ đó $\left \lfloor \dfrac{p-1}{q^i} \right \rfloor=\left \lfloor \dfrac{p}{q^i} \right \rfloor=0$ Nếu $p-1\geq q^i$ ta đặt $p-1=q^i.t+r\;\;(0\leq r<q^i)$, dẫn đến $r+1\leq q^i$, nhưng nếu $r+1=q^i$ thì $p-1=q^i.t+q^i-1\Rightarrow p=q^i(t+1)$, mâu thuẫn vì $p,q$ nguyên tố, do đó $r+1<q^i$. Từ đó $\left \lfloor \dfrac{p-1}{q^i} \right \rfloor=\left \lfloor k+\dfrac{r}{q^i} \right \rfloor=k=\left \lfloor k+\dfrac{r+1}{q^i} \right \rfloor=\left \lfloor \dfrac{p}{q^i} \right \rfloor$ Tóm lại, bổ đề được chứng minh. Quay trở lại bài toán : Ta có $\dfrac{C_p^k}{p}=\dfrac{(p-1)!}{k!(p-k)!}$. Theo định lí $Legendre$, số mũ lớn nhất của thừa số nguyên tố $q$ trong $(p-1)!$ là : \[v_{q}\left ( (p-1)! \right )=\underset{i=1}{\overset{+\infty }{\sum} }\left \lfloor \dfrac{p-1}{q^i} \right \rfloor\] Theo định lí $Legendre$, số mũ lớn nhất của thừa số nguyên tố $q$ trong $k!(p-k)!$ là : \[v_{q}\left ( k!(p-k)! \right )=\underset{i=1}{\overset{+\infty }{\sum} }\left ( \left \lfloor \dfrac{k}{q^i} \right \rfloor +\left \lfloor \dfrac{p-k}{q^i} \right \rfloor\right )\] Áp dụng bổ đề và BĐT quen thuộc $\left \lfloor a+b \right \rfloor\geq \left \lfloor a \right \rfloor+\left \lfloor b \right \rfloor,\;\forall a,b\in \mathbb{R}$, ta được : \[\left \lfloor \dfrac{p-1}{q^i} \right \rfloor=\left \lfloor \dfrac{p}{q^i} \right \rfloor=\left \lfloor \dfrac{k}{q^i}+\dfrac{p-k}{q^i} \right \rfloor\geq \left \lfloor \dfrac{k}{q^i} \right \rfloor+\left \lfloor \dfrac{p-k}{q^i} \right \rfloor\Rightarrow \underset{i=1}{\overset{+\infty }{\sum} }\left \lfloor \dfrac{p-1}{q^i} \right \rfloor\geq \underset{i=1}{\overset{+\infty }{\sum} }\left ( \left \lfloor \dfrac{k}{q^i} \right \rfloor +\left \lfloor \dfrac{p-k}{q^i} \right \rfloor\right )\Rightarrow v_q\left ( (p-1)! \right )\geq v_q(k!(p-k)!)\Rightarrow \dfrac{C_p^k}{p}\in \mathbb{Z}\] Ta được điều phải chứng minh.

Number Theory

Bài toán : Chứng minh rằng $C_{p}^{k}$ chia hết cho $p$ với $k = 1, 2, ..., p - 1$ .

Lời giải :

Bổ đề : Với $p, q$ nguyên tố và $i$ là số nguyên dương, ta có $⌊ \frac{p - 1}{q ^{i}} ⌋ = ⌊ \frac{p}{q ^{i}} ⌋$ .

Chứng minh bổ đề :

Nếu $p - 1 < q^{i} \Rightarrow p \leq q^{i}$ mà vì $p, q$ nguyên tố nên có $p < q^{i}$ , từ đó $⌊ \frac{p - 1}{q ^{i}} ⌋ = ⌊ \frac{p}{q ^{i}} ⌋ = 0$

Nếu $p - 1 \geq q^{i}$ ta đặt $p - 1 = q^{i} . t + r (0 \leq r < q^{i})$ , dẫn đến $r + 1 \leq q^{i}$ , nhưng nếu $r + 1 = q^{i}$ thì $p - 1 = q^{i} . t + q^{i} - 1 \Rightarrow p = q^{i} (t + 1)$ , mâu thuẫn vì $p, q$ nguyên tố, do đó $r + 1 < q^{i}$ .

Từ đó $⌊ \frac{p - 1}{q ^{i}} ⌋ = ⌊ k + \frac{r}{q ^{i}} ⌋ = k = ⌊ k + \frac{r + 1}{q ^{i}} ⌋ = ⌊ \frac{p}{q ^{i}} ⌋$

Tóm lại, bổ đề được chứng minh.

Quay trở lại bài toán :

Ta có $\frac{C _{p}^{k}}{p} = \frac{( p - 1 )!}{k ! ( p - k )!}$ .

Theo định lí $L e g e n d r e$ , số mũ lớn nhất của thừa số nguyên tố $q$ trong $(p - 1)!$ là :

$v_{q} ((p - 1)!) = i = 1 \sum + \infty ⌊ \frac{p - 1}{q ^{i}} ⌋$

Theo định lí $L e g e n d r e$ , số mũ lớn nhất của thừa số nguyên tố $q$ trong $k! (p - k)!$ là :

$v_{q} (k! (p - k)!) = i = 1 \sum + \infty (⌊ \frac{k}{q ^{i}} ⌋ + ⌊ \frac{p - k}{q ^{i}} ⌋)$

Áp dụng bổ đề và BĐT quen thuộc $⌊ a + b ⌋ \geq ⌊ a ⌋ + ⌊ b ⌋, \forall a, b \in R$ , ta được :

$⌊ \frac{p - 1}{q ^{i}} ⌋ = ⌊ \frac{p}{q ^{i}} ⌋ = ⌊ \frac{k}{q ^{i}} + \frac{p - k}{q ^{i}} ⌋ \geq ⌊ \frac{k}{q ^{i}} ⌋ + ⌊ \frac{p - k}{q ^{i}} ⌋ \Rightarrow i = 1 \sum + \infty ⌊ \frac{p - 1}{q ^{i}} ⌋ \geq i = 1 \sum + \infty (⌊ \frac{k}{q ^{i}} ⌋ + ⌊ \frac{p - k}{q ^{i}} ⌋) \Rightarrow v_{q} ((p - 1)!) \geq v_{q} (k! (p - k)!) \Rightarrow \frac{C _{p}^{k}}{p} \in Z$

Ta được điều phải chứng minh.

Number Theory

Đề bài

Mô tả