Số nghiệm của phương trình ax+by=n


Bài viết 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 và áp dụng công thức đó vào giải bài toán Frobenius với một tập có hai phần tử. Ở cuối bài viết chúng tôi cũng giới thiệu một số bài toán thi chọn học sinh giỏi liên quan.

1. Công thức Popoviciu

Trong mục 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 \gcd (a,b)=1n là số tự nhiên.

Định lí 1. (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 \gcd (a,b)=1n 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 ab^{-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)

\gcd (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}\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

2. Áp dụng vào bài toán Frobenius

Giả sử ở ngân hàng chỉ còn hai loại tiền 3 đồng và 5 đồng. Tôi có một tờ n\, (n\in\mathbb{N}^*) đồng. Liệu tôi có thể đem tờ n đồng đó đến ngân hàng để đổi lấy các tờ 3 hay 5 đồng được không? Rõ ràng không phải lúc nào cũng đổi được (chẳng hạn n=4) và với n đủ lớn ta luôn đổi được. Một câu hỏi tự nhiên là: n lớn nhất bằng bao nhiêu để không đổi được? (Câu hỏi này lần đầu tiên được đặt ra bởi Frobenius). Continue reading “Số nghiệm của phương trình ax+by=n”

Tính bất khả quy của các đa thức chia đường tròn


Các đa thức chia đường tròn là bất khả quy trên \mathbb{Q}. Bài viết sau của Steven H. Weintraub giới thiệu một số chứng minh cổ điển của kết quả này.

Các kết quả khác về các đa thức này có ở link https://nttuan.org/2017/02/09/topic-861/

Continue reading “Tính bất khả quy của các đa thức chia đường tròn”

Đa thức chia đường tròn và dạng yếu của định lí Dirichlet


Trong bài này, qua các bài toán tôi sẽ giới thiệu các tính chất của các đa thức chia đường tròn, từ các tính chất đó tôi giới thiệu dạng yếu của định lí Dirichlet. Phần cuối của bài viết là một số bài toán thi chọn học sinh giỏi liên quan. Bạn đọc có thể xem thêm về định lí Dirichlet tại https://nttuan.org/2016/02/11/topic-746/.

Định nghĩa. Cho số nguyên dương n. Đa thức chia đường tròn thứ n, ký hiệu \Phi_n, là đa thức monic có các nghiệm là các căn nguyên thủy bậc n của đơn vị, nghĩa là \displaystyle \Phi_n(x)=\prod_{\omega_n\in U_n}(x-\omega_n), ở đây U_n là tập tất cả các căn nguyên thủy bậc n của đơn vị.

|U_n|=\varphi (n)\,\,\forall n\geq 1 nên \deg\Phi_n=\varphi (n)\,\,\forall n\geq 1.

Ví dụ. 10 đa thức chia đường tròn đầu tiên là

\Phi_1(x)=x-1,\,\, \Phi_2(x)=x+1,\,\, \Phi_3(x)=x^2+x+1,\,\, \Phi_4(x)=x^2+1,

\Phi_5(x)=x^4+x^3+x^2+x+1,\,\, \Phi_6(x)=x^2-x+1,\,\,\Phi_7(x)=x^6+x^5+x^4+x^3+x^2+x+1,

\Phi_8(x)=x^4+1,\,\, \Phi_9(x)=x^6+x^3+1,\,\,\Phi_{10}(x)=x^4-x^3+x^2-x+1.

Bài 1. Chứng minh rằng với mỗi số nguyên dương n ta có \displaystyle x^n-1=\prod_{d|n}\Phi_d(x). Từ đó suy ra \displaystyle n=\sum_{d|n}\varphi (d).

Bài 2. Chứng minh \Phi_n(x)\in\mathbb{Z}[x]\,\,\forall n\geq 1.

Bài 3. Chứng minh rằng nếu an là các số nguyên dương nguyên tố cùng nhau thì \Phi_n(x^a)=\prod_{d|a}\Phi_{nd}(x).

Bài 4. Cho số nguyên dương n và số nguyên tố p. Chứng minh rằng

\displaystyle \Phi_{pn}(x)=\begin{cases}\Phi_n(x^p),\quad p|n\\ \frac{\Phi_n(x^p)}{\Phi_n(x)},\quad p\not|n.\end{cases}

Bài 5. Cho số nguyên dương n, d<n là một ước dương của n, và a là một số nguyên. Giả sử p là một ước nguyên tố chung của \Phi_n(a)\Phi_d(a). Chứng minh rằng p|n.

Bài 6. Cho mn là các số nguyên dương. Giả sử rằng tồn tại số nguyên a sao cho \gcd (\Phi_m(a),\Phi_n(a))>1. Chứng minh rằng \dfrac{m}{n} là lũy thừa nguyên của một số nguyên tố.

Bài 7. Cho số nguyên dương n và số nguyên a. Chứng minh rằng mỗi ước nguyên tố p của \Phi_n(a) phải thỏa mãn p|n hoặc p\equiv 1\pmod{n}.

Bài 8. (Dạng yếu của định lý Dirichlet) Cho số nguyên dương n. Chứng minh rằng có vô hạn số nguyên tố p thỏa mãn p\equiv 1\pmod{n}. Continue reading “Đa thức chia đường tròn và dạng yếu của định lí Dirichlet”

Orthocenter (1)


Tôi ghi ra đây một số kết quả về trực tâm của tam giác. Bạn nào biết kết quả khác thì đóng góp nhé!

Kết quả 1. Cho tam giác ABC không vuông với trực tâm H và tâm ngoại tiếp O. Khi đó \widehat{BAO}=\widehat{CAH},\quad \widehat{CBO}=\widehat{ABH},\quad \widehat{ACO}=\widehat{BCH}.

Kết quả 2. Cho tam giác ABC với trực tâm H và đường tròn ngoại tiếp (O). Nếu H_1 là điểm đối xứng với H qua BC thì H_1\in (O).

Kết quả 3. Cho tam giác ABC với trực tâm H và đường tròn ngoại tiếp (O). Nếu H_2 là điểm đối xứng với H qua trung điểm của BC thì H_2\in (O).

Kết quả 4. Cho tam giác ABC với trực tâm H và đường tròn ngoại tiếp (O;R). Khi đó HA^2=4R^2-BC^2,\quad HB^2=4R^2-CA^2,\quad HC^2=4R^2-AB^2.

Kết quả 5. Cho tam giác ABC với trực tâm H và tâm đường tròn ngoại tiếp O. Nếu A_1,B_1,C_1 lần lượt là trung điểm của BC,CA,AB thì AH=2OA_1,\quad BH=2OB_1,\quad CH=2OC_1.

Kết quả 6. Cho tam giác không vuông ABC với trực tâm H và các đường cao AA_1,BB_1,CC_1. Khi đó H, A,B,C là tâm đường tròn nội tiếp hoặc bằng tiếp (đỉnh thích hợp) của tam giác A_1B_1C_1.

Kết quả 7. Cho tam giác nhọn ABC với trực tâm H. Nếu AM,AN là các tiếp tuyến của đường tròn đường kính BC (M, N là các tiếp điểm) thì M, HN thẳng hàng.

USA TST 2017 (1)


Đề thi chọn đội tuyển Mĩ tham dự IMO 2017

Bài 1. Trong một giải đấu thể thao, mỗi đội sử dụng một bộ nhiều nhất t màu nhận dạng. Một tập hợp S của các đội được gọi là nhận dạng được nếu ta có thể gán cho mỗi đội trong S một màu trong bộ màu của họ sao cho, không có đội nào trong S mang cùng màu với một đội khác trong S. Với tất cả các số nguyên dương nt, xác định số nguyên lớn nhất g (n, t) sao cho: Trong bất kỳ giải đấu thể thao với đúng n màu nhận dạng các đội tuyển, ta có thể tìm được một tập nhận dạng được với ít nhất g(n, t) thành viên.

Bài 2. Cho tam giác nhọn ABC với tâm đường tròn ngoại tiếp O, và điểm T trên đường thẳng BC sao cho \angle TAO=90^{\circ}. Đường tròn đường kính AT cắt đường tròn ngoại tiếp của \Delta BOC tại hai điểm A_1A_2, trong đó OA_1 <OA_2. Các điểm B_1 , B_2 , C_1 , C_2 được định nghĩa tương tự. Continue reading “USA TST 2017 (1)”