Bài toán : Cho $n,p$ là các số nguyên dương lớn hơn $1$. a) Chứng minh rằng số bội số của $p$ trong dãy $1,2,3,....,n$ là $\left [ \dfrac{n}{p} \right ]$ b) (Định lí Legendre) Chứng minh rằng nếu $p$ là số nguyên tố và $p^{e}\parallel n!$ với $e\in \mathbb{Z}^{+}$ thì $e=\left [ \dfrac{n}{p} \right ]+\left [ \dfrac{n}{p^{2}} \right ]+\left [ \dfrac{n}{p^{3}} \right ]+...$ Lời giải : Bổ đề : Nếu $n\in \mathbb{Z}^{+},x\in \mathbb{R}$ thì $\left [ \dfrac{x}{n} \right ]=\left [ \dfrac{\left [ x \right ]}{n} \right ]$ Chứng minh bổ đề : Ta có $x=[x]+\left \{ x \right \}\qquad(0\leq {x}<1)$. Đặt $[x]=t.n+r\qquad(t.r\in \mathbb{N},0\leq r\leq n-1)$ Khi đó $\left [ \dfrac{x}{n} \right ]=\left [ \dfrac{[x]+\left \{ x \right \}}{n} \right ]=\left [ \dfrac{t.n+r+\left \{ x \right \}}{n} \right ]=t+\left [ \dfrac{r+{x}}{n} \right ]=t=\left [ \dfrac{[x]-r}{n} \right ]=\left [ \dfrac{[x]}{n} \right ]$ Trở lại bài toán : a) Gọi các bội số của $p$ trong dãy $1,2,3,...,n$ là $p ; 2p ; 3p ; .... ; mp$ với $m$ là số nguyên dương thì $m$ chính là số bội số của $p$ trong dãy trên. Nếu $p|n$ thì $n=pm\Rightarrow m=\dfrac{n}{p}=\left [ \dfrac{n}{p} \right ]$ Nếu $p\nmid n$ thì ta có : $n-p<mp<n\Rightarrow \dfrac{n}{p}-1<m<\dfrac{n}{p}\Rightarrow m=\left [ \dfrac{n}{p} \right ]$ Do đó số bội số của $p$ trong dãy $1,2,3,....,n$ là $\left [ \dfrac{n}{p} \right ]$ b) Theo câu trên, ta có dãy $1,2,3,....,n$ chứa các số $p,2p,3p,...,\left [ \dfrac{n}{p} \right ]p$ Suy ra $n!=1.2.3...n=p^{\left [ \frac{n}{p} \right ]}.\left [ \dfrac{n}{p} \right ]!.A\qquad(A\in \mathbb{Z}^{+},gcd(p,A)=1)$ Lại áp dụng câu a lần nữa, ta có số bội số của $p$ trong dãy $1,2,3,...,\left [ \dfrac{n}{p} \right ]$ là $\left [ \left [ \dfrac{p}{n} \right ] .\dfrac{1}{p}\right ]=\left [ \dfrac{n}{p^{2}} \right ]$ (áp dụng bổ đề) Do đó $\left [ \dfrac{n}{p} \right ]!=1.2.3...\left [ \dfrac{n}{p} \right ]=p^{\left [ \frac{n}{p^{2}} \right ]}.\left [ \dfrac{n}{p^{2}} \right ]!.B\qquad(B\in \mathbb{Z}^{+},gcd(B,p)=1)$ …… Suy ra $n!=p^{\left [ \frac{p}{n}\right ]}.\left [ \dfrac{p}{n} \right ]!.A=p^{\left [ \frac{p}{n} \right ]}.p^{\left [ \frac{p}{n^{2}} \right ]}.\left [ \dfrac{p}{n^{2}} \right ]!.B.A=p^{\left [ \frac{p}{n} \right ]+\left [ \frac{p}{n^{2}} \right ]+....}.K$ Với $K\in \mathbb{Z}^{+},gcd(K,p)=1$ Mà $p^{e}\parallel n!\Rightarrow e=\left [ \dfrac{n}{p} \right ]+\left [ \dfrac{n}{p^{2}} \right ]+\left [ \dfrac{n}{p^{3}} \right ]+....$ Đây là điều phải chứng minh.

Bài toán [Phần nguyên, giai thừa, bội số]

Bài toán : Cho $n, p$ là các số nguyên dương lớn hơn $1$ .

a) Chứng minh rằng số bội số của $p$ trong dãy $1, 2, 3, ...., n$ là $[\frac{n}{p}]$

b) (Định lí Legendre) Chứng minh rằng nếu $p$ là số nguyên tố và $p^{e} ∥ n!$ với $e \in Z^{+}$ thì $e = [\frac{n}{p}] + [\frac{n}{p ^{2}}] + [\frac{n}{p ^{3}}] + ...$

Lời giải :

Bổ đề : Nếu $n \in Z^{+}, x \in R$ thì $[\frac{x}{n}] = [\frac{[ x ]}{n}]$

Chứng minh bổ đề :

Ta có $x = [x] + {x} (0 \leq x < 1)$ . Đặt $[x] = t . n + r (t . r \in N, 0 \leq r \leq n - 1)$

Khi đó $[\frac{x}{n}] = [\frac{[ x ] + { x }}{n}] = [\frac{t . n + r + { x }}{n}] = t + [\frac{r + x}{n}] = t = [\frac{[ x ] - r}{n}] = [\frac{[ x ]}{n}]$

Trở lại bài toán :

a) Gọi các bội số của $p$ trong dãy $1, 2, 3, ..., n$ là $p; 2 p; 3 p; ....; m p$ với $m$ là số nguyên dương thì $m$ chính là số bội số của $p$ trong dãy trên.

Nếu $p ∣ n$ thì $n = p m \Rightarrow m = \frac{n}{p} = [\frac{n}{p}]$
Nếu $p ∤ n$ thì ta có : $n - p < m p < n \Rightarrow \frac{n}{p} - 1 < m < \frac{n}{p} \Rightarrow m = [\frac{n}{p}]$

Do đó số bội số của $p$ trong dãy $1, 2, 3, ...., n$ là $[\frac{n}{p}]$

b) Theo câu trên, ta có dãy $1, 2, 3, ...., n$ chứa các số $p, 2 p, 3 p, ..., [\frac{n}{p}] p$

Suy ra $n! = 1.2.3... n = p^{[\frac{n}{p}]} . [\frac{n}{p}]! . A (A \in Z^{+}, g c d (p, A) = 1)$

Lại áp dụng câu a lần nữa, ta có số bội số của $p$ trong dãy $1, 2, 3, ..., [\frac{n}{p}]$ là

$[[\frac{p}{n}] . \frac{1}{p}] = [\frac{n}{p ^{2}}]$ (áp dụng bổ đề)

Do đó $[\frac{n}{p}]! = 1.2.3... [\frac{n}{p}] = p^{[\frac{n}{p ^{2}}]} . [\frac{n}{p ^{2}}]! . B (B \in Z^{+}, g c d (B, p) = 1)$

……

Suy ra $n! = p^{[\frac{p}{n}]} . [\frac{p}{n}]! . A = p^{[\frac{p}{n}]} . p^{[\frac{p}{n ^{2}}]} . [\frac{p}{n ^{2}}]! . B . A = p^{[\frac{p}{n}] + [\frac{p}{n ^{2}}] + ....} . K$

Với $K \in Z^{+}, g c d (K, p) = 1$

Mà $p^{e} ∥ n! \Rightarrow e = [\frac{n}{p}] + [\frac{n}{p ^{2}}] + [\frac{n}{p ^{3}}] + ....$

Đây là điều phải chứng minh.

Bài toán [Phần nguyên, giai thừa, bội số]

Đề bài

Mô tả