Một số hàm số học và ứng dụng

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).

Định lý Dirichle

(Định lí Dirichle) Cho $\alpha$ là một số vô tỉ. Chứng minh rằng, tồn tại vô hạn các số nguyên p,q với q>0 sao cho:

$|\alpha -\frac{p}{q}| <\frac{1}{q^2}$

Lời giải:

Trước hết ta chứng minh với mọi $ N \ge q$ luôn tồn tại p,q thỏa mãn:

$|\alpha -\frac{p}{q}| <\frac{1}{qN}$

Thật vậy ta chia các [0;1) thành các khoảng $[\frac{k-1}{N};\frac{k}{N})(k =\overline{1,N})$

Thì theo nguyên lý Dirichle sẽ tồn tại hai số { $\alpha q_i$ } và { $\alpha q_j$ } thuộc vào một đoạn (  q= 0,1,..N)

$\Rightarrow \left | \begin{Bmatrix}
\alpha q_i
\end{Bmatrix}- \begin{Bmatrix}
\alpha q_j
\end{Bmatrix} \right |<\frac{1}{N(q_i-q_j)}\\\Rightarrow \left | \alpha -\frac{\begin{bmatrix}
\alpha q_i
\end{bmatrix}-\begin{bmatrix}
\alpha q_j
\end{bmatrix}}{q_i-q_j} \right | <\frac{1}{N(q_i-q_j)}$ Điều phải chứng minh.

Ta giả sử chỉ có hữu hạn các số p,q thỏa mãn đề bài Kí hiệu tập này là X.

Khi đó sẽ tồn tại M sao cho $|\alpha -\frac{p}{q}| >M$

Chọn N sao cho $\frac{1}{M}<N$ Khi đó tồn tại các số nguyên dương $p_i, q_i$ sao cho
$|\alpha -\frac{p_i}{q_i}| <\frac{1}{q_iN} <\frac{1}{q_iN}<\frac{1}{q_i^2}$

Suy ra $p_i,q_i$ thuộc X, nhưng $M >\frac{1}{q_iN} $ (mâu thuẫn)

Vậy ta có điều phải chứng minh.