I) Hàm phần nguyên:
1) Định nghĩa
Phần nguyên của một số thực x là số nguyên lớn nhất không vượt quá x. Kí hiệu là [x].
2) Tính chất:
a) nếu x>y thì [x] $\ge$ [y]
b) [n+x]=n+[x] (với n nguyên)
c) [x+y] $\ge $ [x]+[y]
d)[2x]+[2y] $ \ge $ [x]+[y]+[x+y]
e) [([x]/d)]=[x/d]
f) Cho x là một số thực dương và d là một số nguyên dương. Khi đó các số nguyên dương là bội của d không vượt qua x là [x/d].
Từ đây ta có định lý:
Trong phân tích tiêu chuẩn của: $n!=p_1^{a_1}p_2^{a_2}..p_k^{a_k}$ số mũ $a_i$ của $p_i$ được tính theo công thức:
$a_i=\left [ \frac{n}{p_i} \right ]+\left [ \frac{n}{p_i^2} \right ]+\left [ \frac{n}{p_i^3} \right ]...$
3) Ứng dụng:
Bài 1: Chứng minh rằng với mọi số nguyên dương m,n ta có (2m)!(2n)! chia hết cho m!n!(m+n)!.
Lời giải:
Gọi p là một số nguyên tố bất kì. Theo định lí thì số mũ của p trong phân tích tiêu chuẩn của m!n!(m+n)! là:
$a=\sum_{k=1}^{\infty }\left [ \frac{m}{p^k} \right ]+\left [ \frac{n}{p^k} \right ]+\left [ \frac{m+n}{p^k} \right ]$
số mũ của p trong phân tích tiêu chuẩn của (2m)!(2n)! là:
$b=\sum_{k=1}^{\infty }\left [ \frac{2m}{p^k} \right ]+\left [ \frac{2n}{p^k} \right ]$
Theo tính chất d) ta có:
$\left [ \frac{m}{p^k} \right ]+\left [ \frac{n}{p^k} \right ]+\left [ \frac{m+n}{p^k} \right ] \le \left [ \frac{2m}{p^k} \right ]+\left [ \frac{2n}{p^k} \right ]$
Từ đó $b \ge a$. Vậy ta có đpcm.
Bài 2:
Cho số nguyên dương $a, n$ sao cho tất cả các ước nguyên tố của $a$ đều lớn hơn $n.$ Chứng minh rằng $(a-1)(a^{2}-1)...(a^{n-1}-1)$ chia hết cho $n!.$
Cách 1:
Gọi $p$ là 1 ước nguyên tố của $n$.
Có $a^{p-1}\equiv 1(modp)$ nên $V_{p}(VT)\geq V_{p}(\prod_{i=1}^{[\frac{n}{p-1}]}(a^{(p-1)i}-1))\geq [\frac{n}{p-1}] \\ V_{p}(n!)=[n/p]+[n/p^{2}]+...[n/p^{s}]\leq n/p+n/p^{2}+...+n/p^{s}=\frac{n-n/p^{s}}{p-1}\leq [\frac{n}{p-1}] \\ --> Q.E.D.\blacksquare$
Cách 2
Bổ đề : Cho $p$ là một số nguyên tố và $n$ là số nguyên dương . Kí hiệu $s_p(n)$ là tổng các chữ số của $n$ viết trong hệ cơ số $p$
Khi đó $v_p(n!)=\frac{n-s_p(n)}{p-1}$
Chứng minh bổ đề : Đặt $n=a_kp^k+a_{k-1}p^{k-1}+..+a_1p+a_0,a_i \in \{1,2,..,p-1\},i=\overline{1,k}$
Theo định lí Legendre : $v_p(n!)=\sum_{i=0}^k [\frac{n}{p_i}]=a_k\frac{p^k-1}{p-1}+a_{k-1}\frac{p^{k-1}-1}{p-1}+a_1$
$=\frac{(a_kp^k+a_{k-1}p^{k-1}+..+a_0)-(a_k+a_{k-1}+..+a_0}{p-1}=\frac{n-s_p(n)}{p-1}$ (đpcm)
Đi vào bài toán
Vì tất cả các ước nguyên tố của $a$ đều lớn hơn $n$ nên $(a,n)=1$ . Giả sử $p$ là ước nguyên tố của $n!$ thì ta có $(a,p)=1$.
Theo định lí Fermat ta có $a^{k(p-1)} \equiv 1 \pmod{p},k \ge 1$ . Mặt khác ta có $v_p(n!)=\frac{n-s_p(n)}{p-1} \le [\frac{n-1}{p-1}]$
Ta có
$v_p(\prod_{k=1}^{n-1}(a^k-1))=\sum_{k=1}^{n-1}v_p(a^k-1) \ge \sum_{k=1}^{k(n-1) \le n} v_p(a^{k(p-1)}-1) \ge [\frac{n}{p-1}] \ge [\frac{n-1}{p-1}] \ge v_p(n!)$
Vậy $n!|\prod_{k=1}^{n-1}(a^k-1)$
II) Hàm số các ước của một số tự nhiên.
1) Định nghĩa: Cho số nguyên dương n. Kí hiệu d(n) là số các ước của n
2) Định lí:
a) Giả sử $n=p_1^{a_1}p_2^{a_2}..p_k^{a_k}$ là phân tích tiêu chuẩn của n>1.
Khi đó $d(n)=(a_1+1)(a_2+1)..(a_k+1)$
b) Với mọi n ta có bất đẳng thức $d(n) < 2 \sqrt{n}$
III) Hàm tổng các ước
1) Định nghĩa: Cho số nguyên dương n. Ta kí hiệu $\sigma (n)$ là tổng các ước của n.
2) Định lí:
a) Hàm số $\sigma (n)$ có tính chất nhân tính. Nghĩa là nếu a,b là hai số nguyên tố cùng nhau thì:
$\sigma (ab)=\sigma (a).\sigma (b)$
b) Giả sử $n=p_1^{a_1}p_2^{a_2}..p_k^{a_k}$ là phân tích tiêu chuẩn của n>1. Khi đó:
$\sigma (n)=\left (\frac{p_1^{a_1+1}-1}{p_1-1} \right )\left (\frac{p_2^{a_2+1}-1}{p_2-1} \right )..\left (\frac{p_k^{a_k+1}-1}{p_k-1} \right )$
c) n là số nguyên tố khi và chỉ khi $\sigma (n)=n+1$.
d) $\sigma (n)$ là một số lẻ nếu và chỉ nếu n là số chính phương hoặc $\frac{n}{2}$ là số chính phương.
Liên quan đến hàm $\sigma (n)$ ta có số hoàn chỉnh.
Định lý về số hoàn chỉnh:
e) Nếu k là số tự nhiên sao cho $2^k-1$ là một số nguyên tốt thì số $n=2^{k-1}(2^k-1)$ là một số hoàn chỉnh.
f)Nếu n là một số hoàn chỉnh chẵn thì n có dạng:
$n=2^k.(2^{k+1}-1)$
IV) Hàm số Euler:
1) Định nghĩa:
Cho số tự nhiên $n \ge 1$. ta kí hiệu $\varphi (n)$ là số các số tự nhiên bé hơn n và nguyên tố cùng nhau với n.
2) Định lý:
Hàm $\varphi (n)$ có tính chất nhân tính theo nghĩa: Nếu a,b là hai số nguyên tố cùng nhau thì:
$\varphi (ab)=\varphi (a)\varphi (b)$
Chú ý rằng những định lý và các khái niệm đều được dùng thẳng trong kì thi VMO ( Theo công văn số 1447/ KTKĐCLGD-KT ngày 27/10/2015). Một điều lạ là kì thi VMO 2016 cho chứng minh định lí e) và f).
