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},$