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$

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

The Chinese Remainder Theorem and Its Generalization

Định lý (Định lý phần dư Trung Hoa). Cho các số nguyên dương $r$ ; $n_1$ , $n_2$ , $\ldots$ , $n_r$ thỏa mãn $(n_i,n_j)=1$ với mọi chỉ số khác nhau $i$ và $j$ . Khi đó hệ phương trình đồng dư

$\displaystyle x\equiv a_1\pmod{n_1},x\equiv a_2\pmod{n_2},\ldots,x\equiv a_r\pmod{n_r}$

có nghiệm duy nhất modulo $\prod n_i$ với mỗi $r$ số nguyên $a_1$ , $a_2$ , $\ldots$ , $a_r$ .

Chúng tôi giới thiệu hai chứng minh của định lí này.

Chứng minh thứ nhất. Phần duy nhất là đơn giản, sau đây ta chứng minh phần tồn tại. Với mỗi $i$ , tồn tại số nguyên $k_i$ để

$\displaystyle x_i:=k_i\prod _{j\not =i}n_j\equiv 1\pmod{n_i}.$

Ta thấy $x=\sum a_ix_i$ là một nghiệm của hệ. $\blacksquare$

Chứng minh thứ hai. Đặt $N=\prod n_i$ . Dễ thấy ánh xạ

$\displaystyle x \pmod N\mapsto (x\pmod{n_1}, x\pmod{n_2}, \ldots, x\pmod{n_r})$

là một song ánh từ tập các lớp $\pmod N$ đến bộ các lớp $\pmod{n_i}$ . $\blacksquare$

Hệ quả. Cho các số nguyên dương $r$ ; $n_1$ , $n_2$ , $\ldots$ , $n_r$ và các số nguyên $a_1,$ $a_2,$ $\ldots,$ $a_r$ . Khi đó hệ phương trình đồng dư

$\displaystyle x\equiv a_1\pmod{n_1},x\equiv a_2\pmod{n_2},\ldots,x\equiv a_r\pmod{n_r}$

có nghiệm khi và chỉ khi $(n_i,n_j)\mid a_i-a_j$ với mọi cách chọn hai chỉ số phân biệt $i$ và $j$ .

Chứng minh. Điều kiện cần là hiển nhiên, ta chứng minh $(n_i,n_j)\mid a_i-a_j$ với mọi $i < j$ là điều kiện đủ để hệ có nghiệm.

Nếu $\prod n_i=1$ thì khẳng định đúng, nếu không, gọi $p_1,p_2,\ldots,p_k$ là các ước nguyên tố của $\prod n_i$ . Với mỗi $i$ , gọi $j(i)$ là chỉ số thỏa mãn

$\displaystyle s_i:=v_{p_i}(n_{j(i)})=\max (v_{p_i}(n_1),v_{p_i}(n_2),\ldots,v_{p_i}(n_r)).$

Theo định lý phần dư Trung Hoa, tồn tại số nguyên $x$ sao cho

$\displaystyle x\equiv a_{j(i)}\pmod{p_i^{s_i}}$

với mọi $i$ . Dễ thấy $x$ là nghiệm của hệ phương trình đồng dư đã cho. $\blacksquare$

A Proof of the Lifting The Exponent Lemma

Định lý 1 (Bổ đề nâng số mũ). Cho hai số nguyên lẻ $a,b$ và số nguyên dương $n$ . Khi đó:

(1) nếu $n$ là số lẻ thì $\displaystyle v_2(a^n-b^n)=v_2(a-b).$

(2) nếu $n$ là số chẵn thì $\displaystyle v_2(a^n-b^n)=v_2\left(\frac{a^2-b^2}{2}\right)+v_2(n).$

Chứng minh. (1) đúng hiển nhiên. Bây giờ ta chứng minh (2).

Viết $n=2^kx$ với $k$ là số nguyên dương và $x$ là số nguyên lẻ. Ta có:

$a^n-b^n=(a^x-b^x)(a^x+b^x)(a^{2x}+b^{2x})\cdots (a^{2^{k-1}x}+b^{2^{k-1}x})$

và trong các thừa số ở vế phải, trừ hai thừa số đầu, tất cả các thừa số còn lại đều chia cho $4$ dư $2$ , suy ra:

$v_2(a^n-b^n)=v_2(a^{2x}-b^{2x})+k-1=v_2(a^2-b^2)+v_2(n)-v_2(2).$

Định lý được chứng minh. $\Box$

Định lý 2 (Bổ đề nâng số mũ). Cho số nguyên tố lẻ $p$ và hai số nguyên $a,b$ không chia hết cho $p$ thỏa mãn $p\mid a-b$ . Khi đó:

$\forall n\in\mathbb{N}^*,\quad v_p\left(a^n-b^n\right)= v_p\left(a-b\right)+v_p(n).$

Chứng minh. Với mỗi số nguyên tố lẻ $p$ , cố định nó. Gọi $S$ là tập tất cả các số nguyên dương $n$ sao cho:

$v_p\left(a^n-b^n\right)= v_p\left(a-b\right)+v_p(n)$

với mọi $a,b$ thỏa mãn các giả thiết của định lý. Ta cần chứng minh $S=\mathbb{N}^*$ .

Khẳng định 1. $1\in S$ .

Chứng minh. Hiển nhiên. $\Box$

Khẳng định 2. Với mỗi hai số nguyên dương $m$ và $n$ , nếu $m\in S$ và $n\in S$ thì $mn\in S$ .

Chứng minh. Với $m,n\in S$ và $a,b$ thỏa mãn các giả thiết của định lí, ta có:

$\begin{aligned} v_p(a^{mn}-b^{mn}) &=v_p((a^m)^n-(b^m)^n)\\ &=v_p(a^m-b^m)+v_p(n)\\ &=v_p(a-b)+v_p(m)+v_p(n)\\ &=v_p(a-b)+v_p(mn), \end{aligned}$

suy ra $mn\in S$ . $\Box$

Khẳng định 3. Nếu $q$ là một số nguyên tố thì $q\in S$ .

Chứng minh. Cố định số nguyên tố $q$ và hai số nguyên $a, b$ thỏa mãn các điều kiện của định lý. Xét hai trường hợp:

Trường hợp 1. $q\not=p$ .

Ta có $a^q-b^q=(a-b)(a^{q-1}+a^{q-2}b+\cdots+b^{q-1})$ và thừa số thứ hai không chia hết cho $p$ nên có ngay $q\in S$ .

Trường hợp 2. $q=p$ .

Viết $a=b+p^kc$ với $k\in\mathbb{N}^*$ và $c$ là số nguyên không chia hết cho $p$ . Theo định lí nhị thức, ta có:

$a^p-b^p=p^{k+1}b^{p-1}c+C_p^2b^{p-2}p^{2k}c^2+\cdots+p^{kp}c^p.$

Vì $p$ là số nguyên tố lẻ và $k\in\mathbb{N}^*$ nên trong tổng trên, trừ số hạng đầu, tất cả các số hạng còn lại đều chia hết cho $p^{k+2}$ , suy ra:

$v_p(a^p-b^p)=v_p(p^{k+1}b^{p-1}c)=k+1=v_p(a-b)+v_p(p),$

hay $q=p\in S$ . $\Box$

Từ ba khẳng định ta có $S=\mathbb{N}^*$ . $\Box$

Nhận xét. Nếu $p$ là số nguyên tố lẻ thỏa mãn $a \equiv -b \not\equiv 0 \pmod p$ và $n$ là số lẻ thì:

$v_p(a^n + b^n) = v_p(a + b) + v_p(n).$

A Proof of Beatty’s Theorem

Cho số thực $\alpha$ . Dãy Beatty của $\alpha$ là dãy $(a_n)_{n\geq 1}$ xác định bởi $a_n=[n\alpha],\quad \forall n\geq 1.$

Định lý (Beatty). Cho hai số thực dương $\alpha$ và $\beta$ . Khi đó các dãy Beatty của $\alpha$ và $\beta$ làm thành một phân hoạch của tập các số nguyên dương khi và chỉ khi $\alpha$ và $\beta$ là các số vô tỷ và

$\displaystyle \frac{1}{\alpha}+\frac{1}{\beta}=1.$

Chứng minh. Đặt $S_{\alpha}=\{[n\alpha]|n=1,2,\ldots\}$ và $\displaystyle S_{\beta}=\{[n\beta]|n=1,2,\ldots\}.$

Giả sử $S_{\alpha}$ và $S_{\beta}$ làm thành một phân hoạch của tập các số nguyên dương. Ta thấy ngay $\alpha$ và $\beta$ lớn hơn $1$ , suy ra hai dãy Beatty của hai số này là các dãy tăng. Ta sẽ sử dụng phương pháp mật độ trong lý thuyết số giải tích.

Với mỗi số nguyên dương $k$ , cố định nó. Xét một số nguyên dương $n$ , ta có

$\displaystyle [n\alpha]\leq k\Leftrightarrow n\alpha < k+1\Leftrightarrow n < \dfrac{k+1}{\alpha}.$

Suy ra $|S_{\alpha}\cap \{1, 2, \ldots, k\}|=\left[\dfrac{k+1}{\alpha}\right]$ hoặc $\left[\dfrac{k+1}{\alpha}\right]-1$ tùy theo $\dfrac{k+1}{\alpha}$ không nằm trong hay nằm trong $\mathbb{Z}$ . Chứng minh tương tự ta có $\displaystyle |S_{\beta}\cap \{1, 2, \ldots, k\}|=\left[\dfrac{k+1}{\beta}\right]$ hoặc $\left[\dfrac{k+1}{\beta}\right]-1$ tùy theo $\dfrac{k+1}{\beta}$ không nằm trong hay nằm trong $\mathbb{Z}$ .

Mà $|S_{\alpha}\cap \{1, 2, \ldots, k\}|+|S_{\beta}\cap \{1, 2, \ldots, k\}|=k$ , suy ra

$\displaystyle -2+\left[\dfrac{k+1}{\alpha}\right]+\left[\dfrac{k+1}{\beta}\right]\leq k\leq \left[\dfrac{k+1}{\alpha}\right]+\left[\dfrac{k+1}{\beta}\right].$

Kết hợp với định nghĩa phần nguyên ta được

$\displaystyle -4+\dfrac{k+1}{\alpha}+\dfrac{k+1}{\beta} < k\leq \dfrac{k+1}{\alpha}+\dfrac{k+1}{\beta}.$

Chia các vế cho $k$ và cho $k\to+\infty$ ta có $\dfrac{1}{\alpha}+\dfrac{1}{\beta}=1.$ Nếu $\alpha$ là số hữu tỷ thì từ đẳng thức này ta có $\beta$ cũng là số hữu tỷ. Viết $\displaystyle \alpha=\dfrac{p}{q},\quad \beta=\dfrac{r}{s},$ với $p$ , $q$ , $r$ , và $s$ là các số nguyên dương. Ta thấy $S_{\alpha}\cap S_{\beta}\not=\emptyset$ , chẳng hạn $pr$ thuộc cả hai tập này, suy ra vô lý. Bởi vậy $\alpha$ là số vô tỷ, và $\beta$ cũng thế.

Bây giờ giả sử ngược lại, $\alpha$ và $\beta$ là các số vô tỷ và $\dfrac{1}{\alpha}+\dfrac{1}{\beta}=1.$ Ta thấy ngay $\alpha$ và $\beta$ lớn hơn $1$ , suy ra hai dãy Beatty của hai số này là các dãy tăng. Nếu $S_{\alpha}\cap S_{\beta}\not=\emptyset$ thì tồn tại các số nguyên dương $k,m$ và $n$ sao cho $k=[m\alpha]=[n\beta]$ . Suy ra

$\displaystyle k\leq m\alpha < k+1,\quad k\leq n\beta < k+1.$

Vì $\alpha$ và $\beta$ là các số vô tỷ nên

$\displaystyle k < m\alpha < k+1,\quad k < n\beta < k+1,$

suy ra

$\displaystyle \frac{k}{\alpha} < m < \frac{k+1}{\alpha},\quad \frac{k}{\beta} < n < \frac{k+1}{\beta},$

cộng theo vế ta có $k < m+n < k+1$ , vô lý. Như vậy $S_{\alpha}\cap S_{\beta}=\emptyset$ .

Nếu tồn tại số nguyên dương $l$ sao cho $l\not\in S_{\alpha}\cup S_{\beta}$ thì tồn tại các số nguyên không âm $p$ và $q$ sao cho

$\displaystyle [p\alpha] < l < [(p+1)\alpha], \quad [q\beta] < l < [(q+1)\beta].$

Vì $l$ là số nguyên nên từ các bất đẳng thức trên ta suy ra $p\alpha < l$ , đồng thời $[(p+1)\alpha] \geq l+1$ kéo theo $(p+1)\alpha \geq l+1$ . Lập luận tương tự cho $\beta$ , ta được