Popoviciu’s theorem

Trong bài này chúng tôi sẽ giới thiệu một công thức tính số nghiệm tự nhiên của phương trình $ax+by=n,$ ở đây $a,b$ là các số nguyên dương thỏa mãn $(a,b)=1$ và $n$ là số tự nhiên.

Định lí. (Công thức Popoviciu) Gọi $N(a,b;n)$ là số các cặp số tự nhiên $(x,y)$ sao cho $ax+by=n$ , ở đây $a,b$ là các số nguyên dương thỏa mãn $(a,b)=1$ và $n$ là số tự nhiên. Khi đó

$\displaystyle N(a,b;n)=\frac{n}{ab}-\left\{\frac{a^{-1}n}{b}\right\}-\left\{\frac{b^{-1}n}{a}\right\}+1,$ với $a^{-1}$ là nghịch đảo modulo $b$ của $a$ và $b^{-1}$ là nghịch đảo modulo $a$ của $b$ .

Chứng minh. Gọi $\displaystyle F(z)=\sum_{n=0}^{+\infty}N(a,b;n)z^n$ là hàm sinh của dãy số $\{N(a,b;n)\}_{n\geq 0}$ . Ta có

$\displaystyle F(z)=\sum_{k\in\mathbb{N}}\sum_{l\in\mathbb{N}}z^{ak}z^{bl}=\frac{1}{(1-z^a)(1-z^b)}.\quad (1)$

Vì $(a,b)=1$ nên đa thức $(1-z^a)(1-z^b)$ có nghiệm là $1$ với bội $2$ và các nghiệm đơn $\xi_a^k$ $(k=1,2,\ldots,a-1)$ , $\xi_b^l$ $(l=1,2,\ldots,b-1)$ , ở đây $\xi_a=\cos\dfrac{2\pi}{a}+i\sin \dfrac{2\pi}{a}$ và $\xi_b=\cos\dfrac{2\pi}{b}+i\sin \dfrac{2\pi}{b}.$ Kết hợp với $(1)$ ta có tồn tại các số phức $C_1,C_2; A_i; B_i$ sao cho

$\displaystyle F(z)=\frac{C_1}{1-z}+\frac{C_2}{(1-z)^2}+\sum_{k=1}^{a-1}\frac{A_k}{1-\xi_a^{-k}z}+\sum_{l=1}^{b-1}\frac{B_l}{1-\xi_b^{-l}z}.\quad (2)$

Để ý đến hệ số của $z^n$ , từ $(2)$ ta có

$\displaystyle N(a,b;n)=C_1+C_2(n+1)+\sum_{k=1}^{a-1}A_k\xi_a^{-nk}+\sum_{l=1}^{b-1}B_l\xi_b^{-nl}.\quad (3)$

Bây giờ ta sẽ đi tìm các số phức $C_1,C_2; A_i; B_i$ từ đẳng thức

$\displaystyle \frac{1}{(1-z^a)(1-z^b)}=\frac{C_1}{1-z}+\frac{C_2}{(1-z)^2}+\sum_{k=1}^{a-1}\frac{A_k}{1-\xi_a^{-k}z}+\sum_{l=1}^{b-1}\frac{B_l}{1-\xi_b^{-l}z}.\quad (4)$

Nhân hai vế của $(4)$ với $(1-z)^2$ và cho $z\to 1$ ta có $C_2=\dfrac{1}{ab}$ , sau đó nhân hai vế của $(4)$ với $1-z$ , để $C_1$ một bên và cho $z\to 1$ ta được $C_1=\dfrac{a+b-2}{2ab}$ . Theo cùng một cách ta có

$\displaystyle A_k=\frac{1}{a(1-\xi_a^{kb})},\quad B_l=\frac{1}{b(1-\xi_b^{la})}.$

Thay vào $(3)$ ta được

$\displaystyle N(a,b;n)=\frac{n}{ab}+\frac{a+b}{2ab}+\frac{1}{a}\sum_{k=1}^{a-1}\frac{\xi_a^{-nk}}{1-\xi_a^{bk}}+\frac{1}{b}\sum_{l=1}^{b-1}\frac{\xi_b^{-nl}}{1-\xi_b^{al}}.\quad (5)$

Từ $(5)$ ta có $\displaystyle N(a,1;n)=\frac{n}{a}+\frac{a+1}{2a}+\frac{1}{a}\sum_{k=1}^{a-1}\frac{\xi_a^{-nk}}{1-\xi_a^{k}}$ , mà $\displaystyle N(a,1;n)=\left[\frac{n}{a}\right]+1$ , suy ra

$\displaystyle \frac{1}{a}\sum_{k=1}^{a-1}\frac{\xi_a^{-nk}}{1-\xi_a^{k}}=\frac{1}{2}-\left\{\frac{n}{a}\right\}-\frac{1}{2a},$

do đó $\displaystyle \frac{1}{a}\sum_{k=1}^{a-1}\frac{\xi_a^{-nk}}{1-\xi_a^{bk}}=\frac{1}{a}\sum_{k=1}^{a-1}\frac{\xi_a^{-nb^{-1}k}}{1-\xi_a^{k}}=\frac{1}{2}-\left\{\frac{nb^{-1}}{a}\right\}-\frac{1}{2a},$

chứng minh tương tự ta được

$\displaystyle \frac{1}{b}\sum_{l=1}^{b-1}\frac{\xi_b^{-nl}}{1-\xi_b^{al}}=\frac{1}{2}-\left\{\frac{na^{-1}}{b}\right\}-\frac{1}{2b},$

thay hai đẳng thức cuối cùng vào $(5)$ ta có điều cần chứng minh. $\Box$

Subconvex sequences

Trong bài này tôi sẽ giới thiệu một lớp dãy hay gặp trong các đề thi chọn học sinh giỏi các cấp. Chứng minh định lí chính trong bài là của Adrian Sandovichi. Để theo dõi cho dễ, các em học sinh nên đọc lại bài sau:

https://nttuan.org/2023/09/15/limit-of-a-sequence/

Định nghĩa. Cho dãy số thực không âm $(x_n)_{n\geq 1}$ và số nguyên $k>0$ . Dãy số $(x_n)_{n\geq 1}$ được gọi là một dãy lồi dưới cấp $k$ nếu có các số thực $\alpha_1,$ $\alpha_2,\ldots,$ $\alpha_k$ sao cho hai điều kiện sau được thỏa mãn đồng thời:

(1) $\alpha_i\in (0;1),\quad \forall i=\overline{1,k}$ và $\alpha_1+\alpha_2+\cdots+\alpha_k\leq 1.$

(2) $x_{n+k}\leq \alpha_1x_{n+k-1}+\alpha_2x_{n+k-2}+\cdots+\alpha_kx_n,\quad \forall n\geq 1.$

Mọi dãy lồi dưới cấp $1$ đều có giới hạn bằng $0.$ Trong định nghĩa trên, nếu dãy số $(x_n)$ có giới hạn hữu hạn và $\sum\alpha_i<1$ thì $\lim x_n=0.$

Định lí. Cho số nguyên dương $k$ . Khi đó mọi dãy lồi dưới cấp $k$ đều có giới hạn hữu hạn.

Chứng minh. Gọi $(x_n)$ là một dãy lồi dưới cấp $k$ . Khi đó tồn tại các số thực $\alpha_1,$ $\alpha_2,\ldots,$ $\alpha_k$ sao cho hai điều kiện sau được thỏa mãn đồng thời:

(1) $\alpha_i\in (0;1),\quad \forall i=\overline{1,k}$ và $\alpha_1+\alpha_2+\cdots+\alpha_k\leq 1.$

(2) $x_{n+k}\leq \alpha_1x_{n+k-1}+\alpha_2x_{n+k-2}+\cdots+\alpha_kx_n,\quad \forall n\geq 1.$

Xét dãy số $(y_n)_{n\geq 1}$ xác định bởi $\displaystyle y_n=\max_{0\leq i\leq k-1}x_{n+i}$ với mọi số nguyên $n>0.$ Ta thấy $(y_n)_{n\geq 1}$ là một dãy số không tăng và bị chặn dưới bởi $0$ nên nó có giới hạn hữu hạn không âm, đặt $L=\lim y_n$ . Ta sẽ chứng minh $(x_n)$ có giới hạn hữu hạn và $L=\lim x_n$ .

Với mọi số thực dương $\epsilon$ , cố định nó.

Đặt $\displaystyle t=\min\left\{1;\frac{\alpha_1^k}{2^k(1-\alpha_1)}\right\}.$ Vì $t>0$ và $L$ là giới hạn của dãy số không tăng $(y_n)$ nên tồn tại số nguyên dương $n_{\epsilon}$ để

$x_n\leq y_n<L+t\epsilon\leq L+\epsilon,\quad \forall n\geq n_{\epsilon}.\quad (*)$

Bây giờ ta chứng minh $x_m>L-\epsilon,\quad \forall m\geq k+n_{\epsilon}.\quad (**)$

Giả sử tồn tại số nguyên dương $m\geq k+n_{\epsilon}$ sao cho $x_m\leq L-\epsilon.$

Mệnh đề. $\displaystyle x_{m+p}\leq L-\epsilon\left(\frac{\alpha_1}{2}\right)^p,\quad \forall p=\overline{1,k-1}.$

Chứng minh. Ta chứng minh bằng quy nạp theo $p.$ Với $p=1$ , từ $(*)$ và cách chọn $t$ ta có

$x_{m+1} \leq \alpha_1x_m+\alpha_2x_{m-1}+\cdots+\alpha_kx_{m-k+1}$

$\leq\alpha_1x_m+(\alpha_2+\cdots+\alpha_k)(L+t\epsilon)$

$\leq\alpha_1(L-\epsilon)+(1-\alpha_1)(L+t\epsilon)$

$\leq L-a_1\epsilon+\left(\frac{\alpha_1}{2}\right)^k\epsilon$

$\leq L-a_1\epsilon+\left(\frac{\alpha_1}{2}\right)^1\epsilon$

$=L-\epsilon\left(\frac{\alpha_1}{2}\right).$

Suy ra khẳng định đúng với $p=1.$ Giả sử khẳng định đúng đến $p<k-1$ , ta chứng minh nó đúng với $p+1.$ Theo giả thiết quy nạp, $(*)$ và cách chọn $t$ ta có

$x_{m+p+1} \leq \alpha_1x_{m+p}+\alpha_2x_{m+p-1}+\cdots+\alpha_kx_{m+p-k+1}$

$\leq\alpha_1\left(L-\epsilon\left(\frac{\alpha_1}{2}\right)^p\right)+(1-\alpha_1)(L+t\epsilon)$

$=L-a_1\epsilon \left(\frac{\alpha_1}{2}\right)^p+(1-\alpha_1)t\epsilon$

$\leq L-a_1\epsilon \left(\frac{\alpha_1}{2}\right)^p+\left(\frac{\alpha_1}{2}\right)^k\epsilon$

$\leq L-a_1\epsilon \left(\frac{\alpha_1}{2}\right)^p +\left(\frac{\alpha_1}{2}\right)^{p+1}\epsilon$

$=L-\epsilon\left(\frac{\alpha_1}{2}\right)^{p+1}.$

Suy ra khẳng định đúng với $p+1$ . Theo nguyên lý quy nạp toán học, mệnh đề là đúng. $\Box$

Continue reading →

Limit of a sequence

Giải tích thực là một nhánh của giải tích toán học nghiên cứu dáng điệu của dãy thực, chuỗi thực, và hàm giá trị thực. Một khái niệm trung tâm của giải tích thực là dãy hội tụ.

Định nghĩa 1. Một dãy số thực $\left(u_{n}\right)$ hội tụ đến một số thực $l$ , hay $l$ là một giới hạn của dãy số $(u_n),$ nếu với mỗi số thực dương $\epsilon$ , tồn tại số nguyên dương $N$ sao cho mỗi khi $n \geq N,$ ta có $\left|u_{n}-l\right|<\epsilon$ . Nếu một dãy số có một giới hạn ta nói nó là dãy hội tụ, nếu nó không có giới hạn, ta nói nó là dãy phân kỳ.

Để chỉ $\left(u_{n}\right)$ hội tụ đến $l$ , ta viết $\lim u_{n}=l$ hoặc $\lim \left(u_{n}\right) =l$ . Ký hiệu $\displaystyle \lim _{n \rightarrow \infty} u_{n}=l$ cũng hay được dùng. Định nghĩa trên có thể gây rối đối với những bạn mới học giải tích, sau đây chúng tôi giới thiệu một định nghĩa khác, hình học hơn. Để làm điều này ta cần đến:

Định nghĩa 2. Cho số thực $l$ và số thực $\epsilon>0$ , tập

$U_{\epsilon}(l)=\{x \in \mathbb{R}:|x-l|<\epsilon\}$ được gọi là $\epsilon$ -lân cận của $l$ .

Để ý rằng $U_{\epsilon}(l)$ gồm tất cả các điểm trên trục số cách điểm $l$ một khoảng bé hơn $\epsilon$ . Nói cách khác, $U_{\epsilon}(l)$ là một khoảng có tâm tại $l$ và bán kính $\epsilon$ .

Định nghĩa 3. Một dãy số thực $\left(u_{n}\right)$ hội tụ đến một số thực $l$ , hay $l$ là một giới hạn của dãy số $(u_n),$ nếu với mỗi $\epsilon$ -lân cận $U_{\epsilon}(l)$ của $l,$ có một vị trí trong dãy mà từ đó trở đi, mọi số hạng của dãy đều thuộc $U_{\epsilon}(l).$ Nói cách khác, mỗi $\epsilon$ -lân cận của $l$ đều chứa hầu hết (chỉ trừ một số hữu hạn) các số hạng của dãy $(u_n).$

Số $N$ nói chung phụ thuộc vào $\epsilon.$ Khi $\epsilon$ càng nhỏ có thể $N$ càng lớn. Định nghĩa giới hạn của một dãy số thực được sử dụng để kiểm tra xem một số thực $l$ có là giới hạn của dãy hay không, nó không cho ta cách xác định giới hạn của dãy.

Ví dụ 1. Với mọi số thực $a,$ dãy hằng $a,a,a,\ldots$ hội tụ đến $a.$

Lời giải. Xét một số thực $a$ . Ta phải chứng minh $\lim u_n=a$ , trong đó $(u_n)_{n\geq 1}$ là dãy số xác định bởi $u_n=a$ với mọi số nguyên dương $n$ . Với một số thực dương $\epsilon$ bất kỳ, chọn $N=1$ , ta có $\mid u_n-a\mid =\mid a-a\mid =0<\epsilon,\quad\forall n\geq N.$ Từ đây ta có điều cần chứng minh. $\Box$

Ví dụ 2. Chứng minh rằng $\lim\dfrac{1}{\sqrt{n}}=0.$

Lời giải. Ta phải chứng minh $\lim u_n=0$ , trong đó $(u_n)_{n\geq 1}$ là dãy số xác định bởi $u_n=\dfrac{1}{\sqrt{n}}$ với mọi số nguyên dương $n$ . Với một số thực dương $\epsilon$ bất kỳ, chọn $N=2+[1/\epsilon^2]$ , ta có $\mid u_n-0\mid =\frac{1}{\sqrt{n}}<\epsilon,\quad\forall n\geq N.$ Từ đây ta có điều cần chứng minh. $\Box$

Ví dụ 3. Chứng minh rằng $\lim\dfrac{n+1}{n}=1.$

Lời giải. Ta phải chứng minh $\lim u_n=1$ , trong đó $(u_n)_{n\geq 1}$ là dãy số xác định bởi $u_n=\dfrac{n+1}{{n}}$ với mọi số nguyên dương $n$ . Với một số thực dương $\epsilon$ bất kỳ, chọn $N=2+[1/\epsilon]$ , ta có $\mid u_n-1\mid =\frac{1}{{n}}<\epsilon,\quad\forall n\geq N.$ Từ đây ta có điều cần chứng minh. $\Box$

Continue reading →

A proof of Cauchy–Davenport theorem

Trong bài này tôi sẽ giới thiệu một chứng minh của định lí Cauchy-Davenport.

Định lí Cauchy – Davenport. Cho số nguyên tố $p$ và hai tập con khác rỗng $A,B$ của $\mathbb{Z}/p\mathbb{Z}.$ Khi đó

$|A+B|\geq\min (p,|A|+|B|-1).$

Chứng minh. Ta chứng minh khẳng định bằng quy nạp theo $|B|$ . Khi $|B|=1$ ta có

$|A+B|=|A|=\min (p,|A|)=\min (p,|A|+|B|-1).$ Suy ra khẳng định đúng khi $|B|=1$ . Khi $|B|=2$ ta viết $B=\{b_1,b_2\}$ và $A=\{a_1,a_2,\ldots,a_m\},$ ta có ngay $|A+B|\geq m$ .

Nếu $|A+B|= m$ thì $\{b_1+a_1,\ldots,b_1+a_m\}=\{b_2+a_1,\ldots,b_2+a_m\},$ suy ra $mb_1\equiv mb_2\pmod{p}$ , hay $m=p$ . Khi đó $|A+B|=p\geq\min (p,|A|+|B|-1).$

Nếu $|A+B|>m$ thì $|A+B|\geq m+1\geq\min (p,m+1)=\min (p,|A|+|B|-1).$

Vậy khẳng định đúng khi $|B|=2$ . Giả sử khẳng định đúng với mỗi tập $B$ thỏa mãn $|B|<n,$ trong đó $n\geq 3.$ Ta sẽ chứng minh khẳng định đúng với mọi tập $B$ có $|B|=n.$ Xét một tập $B$ thỏa mãn $|B|=n$ . Đặt $|A+B|=l,|A|=m$ và viết $B=\{b_1,b_2,\ldots,b_n\}.$ Xét ba trường hợp

Trường hợp 1. $l\geq p.$

Ta có $|A+B|=l\geq p\geq\min (p,|A|+|B|-1).$

Trường hợp 2. $m+n>p.$

Ta có $A+B=\{0,1,2,\ldots,p-1\}$ , thật vậy với mỗi $g\in \{0,1,2,\ldots,p-1\}$ , hai tập $g-A$ và $B$ có giao khác rỗng vì chúng là các tập con của tập $\{0,1,2,\ldots,p-1\}$ và có tổng số phần tử lớn hơn $p$ . Lấy $h\in g-A\cap B$ ta có ngay $g=b=g-a\,\, (a\in A,b\in B),$ suy ra $g=a+b\in A+B$ . Từ đây ta có $|A+B|=p\geq\min (p,|A|+|B|-1).$

Trường hợp 3. $l<p$ và $m+n\leq p.$

Ở trường hợp này thì $\min (p,|A|+|B|-1)=\min (p,m+n-1)=m+n-1.$ Áp dụng giả thiết quy nạp cho hai tập $C=A+B$ và $\{b_1,b_n\}$ ta có $|C+\{b_1,b_n\}|\geq\min (p,|C|+|\{b_1,b_n\}|-1)=\min (p,l+1)=l+1,$ suy ra $C+b_1\not = C+b_n$ , do đó tồn tại số nguyên $x$ sao cho $x-b_1\in A+B$ và $x-b_n\not\in A+B$ . Từ đây ta thấy tồn tại số nguyên dương $r<n$ sao cho $x-b_i\in A+B,\,\forall i=\overline{1,r}$ và $x-b_i\not\in A+B,\,\forall i=\overline{r+1,n}$ . Áp dụng giả thiết quy nạp cho hai tập $A$ và $B^{\prime}=\{b_{r+1},b_{r+2},\ldots,b_n\}$ ta có

$|A+B^{\prime}|\geq \min (p,|A|+|B^{\prime}|-1)=\min (p,m+n-r-1)=m+n-r-1.$ Ta có $x-b_i\not\in A+B^{\prime},\,\forall i=\overline{1,r}$ , vì nếu chẳng hạn $x-b_1\in A+B^{\prime}$ thì

$x-b_1= a+b_{s}\Rightarrow x-b_s\in A+B,$ điều này trái với cách chọn $r$ . Vậy $|A+B|\geq r+|A+B^{\prime}|\geq r+m+n-r-1=m+n-1,$ và định lí được chứng minh. $\Box$

Bằng quy nạp ta chứng minh được kết quả sau.

Hệ quả. Cho số nguyên dương $h>1,$ số nguyên tố $p$ và $h$ tập con khác rỗng $A_1,$ $A_2,\ldots,$ $A_h$ của $\mathbb{Z}/p\mathbb{Z}.$ Khi đó $\displaystyle \mid A_1+A_2+\cdots+A_h\mid \geq \min \left(p,\sum_{i=1}^h\mid A_i\mid-h+1\right).$

Principle of inclusion and exclusion

Bài này là một mở đầu của phương pháp sàng trong các bài toán đếm. Ở phương pháp này, khi muốn đếm số phần tử của một tập $A$ , ta bắt đầu với một tập $B$ chứa $A$ , sau đó tìm cách loại đi các phần tử không nằm trong $A$ .

Để theo dõi bài này cho dễ, các bạn hãy xem qua các bài sau:

[1] https://nttuan.org/2011/09/15/basic-counting-principles/

[2] https://nttuan.org/2012/09/15/permutations/

[3] https://nttuan.org/2013/09/15/combinations/

Chúng ta biết rằng nếu $A$ và $B$ là các tập hữu hạn rời nhau thì $|A\cup B|=|A|+|B|$ , tổng quát hơn ta có: Nếu $A$ và $B$ là các tập hữu hạn bất kỳ thì $|A\cup B|=|A|+|B|-|A\cap B|,$ đây chính là nguyên lý bù-trừ cho hai tập hợp. Với $n>1$ tập hợp ta có định lí sau

Định lí. Nếu $A_1,A_2,\ldots,A_n$ là các tập hữu hạn thì

$\displaystyle \left|\bigcup_{i=1}^nA_i\right|=\sum_{1\leq i\leq n}|A_i|-\sum_{1\leq i<j\leq n}|A_i\cap A_j|+\cdots+(-1)^{n+1}\left|\bigcap_{1\leq i\leq n}A_i\right|.$

Chứng minh. Ta sẽ chứng minh rằng mỗi phần tử trong $\displaystyle\bigcup_{i=1}^nA_i$ được đếm đúng một lần trong vế phải. Gọi $x$ là một phần tử trong hợp đó và nó nằm trong dúng $m$ tập $A_i$ , khi đó trong vế phải nó sẽ được đếm đúng $C_m^1-C_m^2+\cdots+(-1)^{m+1}C_m^m=1$ lần (lưu ý $(1-1)^m=0$ ). $\Box$

Ngoài cách chứng minh trên các bạn có thể chứng minh định lí bằng phương pháp quy nạp toán học, tôi chọn giới thiệu cách chứng minh này vì phong cách tổ hợp của nó.

Ví dụ 1. Có bao nhiêu số nguyên dương $n$ sao cho $n$ là ước của ít nhất một trong hai số $10^{40}$ và $20^{30}$ ?

Lời giải. Gọi $A$ và $B$ lần lượt là tập các ước dương của $10^{40}$ và $20^{30}$ . Đề bài yêu cầu tính $|A\cup B|$ . Ta có $10^{40}=2^{40}5^{40}, 20^{30}=2^{60}5^{30}$ và $(10^{40},20^{30})=2^{40}5^{30}.$ Suy ra $|A|=(40+1)(40+1)=1681, |B|=(60+1)(30+1)=1891$ và $|A\cap B|=(40+1)(30+1)=1271.$ Bởi thế nên $|A\cup B|=|A|+|B|-|A\cap B|=2301.$ $\Box$

Ví dụ 2. Tìm số các số nguyên dương trong $\{1,2,\ldots,500\}$ chia hết cho $2$ hoặc $3$ hoặc $5.$

Lời giải. Đặt $S=\{1,2,\ldots,500\}$ . Gọi $A,B$ và $C$ lần lượt là tập các phần tử của $S$ chia hết cho $2,3$ và $5$ . Khi đó $A\cup B\cup C$ là tập các số nguyên dương trong $S$ chia hết cho $2$ hoặc $3$ hoặc $5.$ Đề bài yêu cầu tính $|A\cup B\cup C|$ .

Vì $2,3$ và $5$ là các số nguyên dương đôi một nguyên tố cùng nhau nên $A\cap B$ là tập các số nguyên dương trong $S$ chia hết cho $6$ , $B\cap C$ là tập các số nguyên dương trong $S$ chia hết cho $15$ , $C\cap A$ là tập các số nguyên dương trong $S$ chia hết cho $10$ , và $A\cap B\cap C$ là tập các số nguyên dương trong $S$ chia hết cho $30$ . Suy ra $|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C|$ $\displaystyle=\left[\frac{500}{2}\right]+\left[\frac{500}{3}\right]+\left[\frac{500}{5}\right]-\left[\frac{500}{6}\right]-\left[\frac{500}{15}\right]-\left[\frac{500}{10}\right]+\left[\frac{500}{30}\right]=366.$ $\Box$

Với mỗi số nguyên dương $m$ , ký hiệu $\varphi (m)$ là số các số nguyên dương không vượt quá $m$ và nguyên tố cùng nhau với $m$ . Hàm số $\varphi:\mathbb{N}^*\to\mathbb{N}^*$ được gọi là hàm phi của Euler.

Ví dụ 3. Tính $\varphi (180)$ .

Lời giải. Vì $180=2^23^25$ nên $X$ chính là tập các số trong $S$ không chia hết cho $2,3$ và $5$ . Suy ra $S\setminus X=X_1\cup X_2\cup X_3$ với $X_1$ là tập các số trong $S$ chia hết cho $2$ , $X_2$ là tập các số trong $S$ chia hết cho $3$ , và $X_3$ là tập các số trong $S$ chia hết cho $5.$ Tương tự như bài toán trên ta có

$\displaystyle |X_1\cup X_2\cup X_3|=|X_1|+|X_2|+|X_3|-|X_1\cap X_2|-|X_2\cap X_3|-|X_3\cap X_1|+|X_1\cap X_2\cap X_3|$

$\displaystyle =\left[\frac{180}{2}\right]+\left[\frac{180}{3}\right]+\left[\frac{180}{5}\right]-\left[\frac{180}{6}\right]-\left[\frac{180}{15}\right]-\left[\frac{180}{10}\right]+\left[\frac{180}{30}\right]=132.$ Do đó $\varphi (180)=|X|=|S|-|S\setminus X|=180-132=48.$ $\Box$

Làm tương tự như trên ta có nếu $n$ có phân tích chính tắc $\displaystyle n=\prod p_i^{k_i}$ thì $\displaystyle\varphi (n)=n\prod \left(1-\frac{1}{p_i}\right).$

Ví dụ 4. Tìm số các lời giải nguyên không âm của phương trình $x_1+x_2+x_3=15$ với $x_1\leq 5,x_2\leq 6$ và $x_3\leq 7$ .

Lời giải. Gọi $A$ là tập các nghiệm nguyên không âm của phương trình $x_1+x_2+x_3=15,$ và $B$ là tập các nghiệm nguyên không âm của phương trình thỏa mãn $x_1\leq 5,x_2\leq 6$ và $x_3\leq 7.$ Ta cần tính $\mid B\mid.$ Ta có $A\setminus B=B_1\cup B_2\cup B_3,$ trong đó: $B_1$ là tập các nghiệm nguyên không âm của phương trình thỏa mãn $x_1>5.$ $B_2$ là tập các nghiệm nguyên không âm của phương trình thỏa mãn $x_2>6.$ $B_3$ là tập các nghiệm nguyên không âm của phương trình thỏa mãn $x_3>7.$

Theo nguyên lý bù-trừ, ta có $C^2_{17}-\mid B\mid =\mid A\mid -\mid B\mid =\mid A\setminus B\mid =\sum \mid B_i\mid -\sum \mid B_i\cap B_j\mid+\mid B_1\cap B_2\cap B_3\mid. \quad (*)$

Bộ số tự nhiên $(x_1,x_2,x_3)$ thuộc $B_1$ khi và chỉ khi $(x_1-6)+x_2+x_3=9,$ do đó $\mid B_1\mid =C^2_{11}.$ Hoàn toàn tương tự, ta có $\mid B_2\mid =C^2_{10}$ và $\mid B_3\mid = C_9^2.$

Bộ số tự nhiên $(x_1,x_2,x_3)$ thuộc $B_1\cap B_2$ khi và chỉ khi $(x_1-6)+(x_2-7)+x_3=2,$ do đó $\mid B_1\cap B_2\mid =C^2_{4}.$ Hoàn toàn tương tự, ta có $\mid B_2\cap B_3\mid =1,$ $\mid B_3\cap B_1\mid = C_3^2,$ và $\mid B_1\cap B_2\cap B_3\mid =0.$

Bây giờ thay các kết quả trên vào $(*)$ ta có $\mid B\mid =10.$ $\Box$

Ví dụ 5. Tìm số nghiệm nguyên của phương trình $x_1+x_2+x_3=28$ với $3\leq x_1\leq 9,0\leq x_2\leq 8$ và $7\leq x_3\leq 17$ .

Hướng dẫn. Đáp số: $28.$ Đặt $y_1=x_1-3,$ $y_2=x_2,$ và $y_3=x_3-7.$ Ta cần tính số nghiệm tự nhiên của phương trình $y_1+y_2+y_3=18$ thỏa mãn $y_1\leq 6,$ $y_2\leq 8$ và $y_3\leq 10.$ Đến đây làm như ví dụ trên. $\Box$

Ví dụ 6. Với $k=1,2,\ldots,1992$ cho $A_k$ là một tập với $44$ phần tử. Giả sử rằng $|A_i\cap A_j|=1$ với mỗi $i,j$ khác nhau trong $\{1,2,\ldots,1992\}.$ Tính $\displaystyle \left|\bigcup_{i=1}^{1992}A_i\right|.$