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

VMO training 2017 – Part 5


Các bạn có thể xem phần trước ở https://nttuan.org/2017/01/06/topic-852/


Trong bài viết này tôi sẽ giới thiệu một số lời giải của bài toán sau: Cho (s_n)_{n\geq 1}(t_n)_{n\geq 1} là hai dãy các số hữu tỷ thỏa mãn đồng thời các điều kiện sau:

1) (s_n)_{n\geq 1}(t_n)_{n\geq 1} không phải là dãy hằng;

2) \forall i,j\in\mathbb{N}^*,\quad (s_i-s_j)(t_i-t_j)\in\mathbb{Z}.

Chứng minh rằng tồn tại số hữu tỷ r sao cho r(s_i-s_j)\in\mathbb{Z}\dfrac{t_i-t_j}{r}\in\mathbb{Z},\quad\forall i,j\in\mathbb{N}^*.

Đây là bài toán số 6 trong đề thi chọn HSG QG của Mĩ năm 2009 (USAMO 2009).

Lời giải 1. Ta có ba nhận xét sau:

1) Nếu \sigma:\mathbb{N}^*\to \mathbb{N}^* là một song ánh thì hai dãy (s_{\sigma(n)})_{n\geq 1}(t_{\sigma(n)})_{n\geq 1} cũng thỏa mãn các giả thiết của bài toán;

2) Nếu s,t là các số hữu tỷ thì hai dãy (s_{n}+s)_{n\geq 1}(t_{n}+t)_{n\geq 1} cũng thỏa mãn các giả thiết của bài toán.

3) Tồn tại cặp chỉ số (i,j) sao cho (s_i-s_j)(t_i-t_j)\not=0.

Thật vậy, do dãy (s_i) không phải dãy hằng nên tồn tại (i,j) sao cho s_i\not=s_j. Nếu t_i\not=t_j thì (i,j) là cặp phải tìm. Nếu t_i=t_j, ta chọn k sao cho t_k\not=t_i, khi s_k=s_i ta chọn (j,k), khi s_k\not=s_i ta chọn (k,i).

Trở lại bài toán.

Bởi các nhận xét trên ta có thể giả sử s_1=t_1=0,s_2\not=0t_2\not=0.

Ta sẽ chứng minh tồn tại các số hữu tỷ dương  A,B sao cho AB, As_jBt_j là các số nguyên với mọi j.

Với mọi i,j ta có (s_i-s_1)(t_i-t_1)=s_it_i(s_i-s_j)(t_i-t_j)=s_it_i+s_jt_j-(s_it_j+s_jt_i), suy ra s_it_is_it_j+s_jt_i là các số nguyên. Viết s_j,t_j dưới dạng tối giản ta được \displaystyle s_j=\frac{p_j}{q_j},t_j=\frac{u_j}{v_j},\quad\forall j. Theo trên ta có s_2t_j+s_jt_2 là số nguyên với mọi j, suy ra với mọi j ta có q_j|u_2q_2. Chọn A=|q_2u_2|>0 ta có As_j là số nguyên với mọi j. Tương tự ta cũng tìm được số nguyên dương B sao cho Bt_j là số nguyên với mọi j.

Chọn cặp (A,B) như trên sao cho AB nhỏ nhất, ta thấy AB phải bằng 1 và khi đó bài toán sẽ được giải. Thật vậy, nếu AB>1 thì nó có ước nguyên tố p, suy ra ABs_jt_j=(As_j)(Bt_j) chia hết cho p với mọi j, do đó với mọi j thì As_j hoặc Bt_j sẽ chia hết cho p. Xét các trường hợp:

Trường hợp 1: p chia hết As_j với mọi j.

Ta thấy cặp (A/p,B) cũng thỏa mãn và có tích bằng \dfrac{AB}{p}<AB, vô lí.

Trường hợp 2: Tồn tại j để p không chia hết As_j.

Khi đó ta có Bt_j chia hết cho pBt_i không chia hết cho p với i nào đấy (do cách chọn (A,B)), suy ra AB(s_it_j+s_jt_i)-(As_i)(Bt_j)=(As_j)(Bt_i) không chia hết cho p, vô lí.

Lời giải 2. Đây là lời giải của Paul Christiano, huy chương Bạc tại IMO 2008.

Ta cho các số hữu tỷ trong lời giải này đều ở dạng tối giản.

Không mất tính tổng quát ta có thể giả sử s_1=t_1= 0, t_2\not=0s_2 = 1. Khi đó t_2=k là số nguyên (vì (s_2 - s_1)(t_2 - t_1) là số nguyên), và

(s_i - 1)(t_i - k) = s_it_i + k - (t_i + ks_i) \in \mathbb{Z},\quad i\in\mathbb{N}^*.s_it_i = (s_i - 0)(t_i - 0) = (s_i - s_1)(t_i - t_1)\in\mathbb{Z},\quad\forall i\in\mathbb{N}^*, suy ra t_i + ks_i \in \mathbb{Z},\quad \forall i\in\mathbb{N}^*. Ta thấy ks_i phải là số nguyên với mọi số nguyên dương i, thật vậy nếu tồn tại số nguyên dương i sao cho ks_i \not\in \mathbb{Z} thì mẫu của s_i có ước nguyên tố p không chia hết k, suy ra t_i+ks_i không phải là số nguyên vì mẫu của t_i cũng không chia hết cho p (do s_it_i là số nguyên), vô lí. Từ đó ta có t_i \in \mathbb{Z} với mỗi số nguyên dương i.

Nếu cần thì chia các số hạng của dãy (t_i) cho cùng một số nguyên dương và nhân các số hạng của dãy (s_i) với số nguyên dương đó, ta có thể coi ước chung lớn nhất của tất cả các số hạng của dãy (t_i) bằng 1, và tất nhiên, vẫn có số nguyên k\not=0 thỏa mãn ks_i\in\mathbb{Z} với mọi số nguyên dương i.

Ta sẽ chứng minh rằng s_i\in\mathbb{Z} với mọi số nguyên dương i, và khi đó bài toán sẽ được giải hoàn toàn. Thật vậy, giả sử tồn tại số nguyên dương i sao cho s_i không phải là số nguyên. Khi đó có số nguyên tố p là ước của mẫu của s_i. Gọi j là số nguyên dương thỏa mãn p không chia hết t_j (tồn tại j như thế vì ước chung lớn nhất của các t_n bằng 1). Vì s_it_i là số nguyên nên p chia hết t_i, do đó t_i - t_j không chia hết cho p. Vì s_jt_j là số nguyên và p không chia hết t_j nên p không chia hết mẫu của s_j, do đó s_i - s_j có mẫu không chia hết cho p. Nhưng khi đó (s_i - s_j)(t_i-t_j) có mẫu chia hết cho p, và bởi thế nó không phải là số nguyên, vô lí.

Continue reading “VMO training 2017 – Part 5”

Kiểm tra tháng 1/2017


Dành cho các bạn học sinh lớp 9.

Bài 1.

1) Cho các số thực a,bc thỏa mãn a^2-b^2=4c^2. Chứng minh rằng (5a-3b+8c)(5a-3b-8c)=(3a-5b)^2.

2) Cho x,yz là các số thực thoả mãn

(x-y)^2+(y-z)^2+(z-x)^2=(x+y-2z)^2+(y+z-2x)^2+(z+x-2y)^2. Chứng minh rằng x=y=z.

3) Chứng minh rằng nếu x,yz là các số thực có tổng bằng 0 thì 2(x^5+y^5+z^5)=5xyz(x^2+y^2+z^2).

Bài 2.

1) Tìm tất cả các số nguyên dương n sao cho n^4+4 là số nguyên tố.

2) Cho các số nguyên dương a,b,cd thỏa mãn ab=cd. Chứng minh rằng số a^{3}+b^3+c^3+d^3 không phải là số nguyên tố.

3) Cho hai số hữu tỷ p<q. Hỏi có bao nhiêu số nguyên z thỏa mãn p\leq z\leq q?

Bài 3. Cho đường thẳng d cố định và điểm A cố định không nằm trên d. Gọi BC là hai điểm di động trên d sao cho tam giác ABC là tam giác nhọn và AB<AC. Gọi I là tâm đường tròn nội tiếp tam giác ABCD là giao điểm của hai đường thẳng AIBC. Đường thẳng AD cắt đường tròn ngoại tiếp tam giác ABC tại hai điểm phân biệt AJ.

1) Chứng minh JI^2=JD.JA;

2) Gọi E là tâm của đường tròn đi qua hai điểm A,D và tiếp xúc với BC tại D. Gọi M là hình chiếu vuông góc của D trên EBN là hình chiếu vuông góc của D trên EC. Chứng minh các điểm B,I,C,MN cùng nằm trên một đường tròn;

3) Gọi K là điểm đối xứng với I qua BC. Đường thẳng AI cắt đường tròn ngoại tiếp tam giác BIC tại hai điểm phân biệt IG. Chứng minh đường thẳng GK luôn đi qua một điểm cố định khi  BC di động trên d sao cho tam giác ABC là tam giác nhọn và AB<AC.

Tính rời rạc của tập số nguyên (2)


Các bạn có thể xem phần đầu ở https://nttuan.org/2016/12/15/topic-845/

Bài 8. Tìm nghiệm nguyên dương của phương trình

\left(1+\frac{1}{x}\right)\left(1+\frac{1}{y}\right)\left(1+\frac{1}{z}\right)=2.

Bài 9. Cho x,yn là các số nguyên dương thỏa mãn \dfrac{xy}{x+y}>n. Chứng minh rằng \dfrac{xy}{x+y}\geq n+\dfrac{1}{n^2+2n+2}.

Bài 10. Cho a,bc là các số nguyên dương thỏa mãn ab chia hết c(c^{2}-c+1)a+b chia hết cho c^{2}+1. Chứng minh rằng \{a,b\}=\{c,c^{2}-c+1\}.

Bài 11. Tìm nghiệm nguyên dương của các phương trình

1/. 3(xy+yz+zx)=4xyz;

2/. xy+yz+zx-xyz=2;

3/. (x+y)^2+3x+y+1=z^2;

4/. x^2+y^2+z^2+w^2=3(x+y+z+w).

Bài 12. Tìm nghiệm nguyên của phương trình (x+1)^4-(x-1)^4=y^3.

Bài 13. Cho các số nguyên a\in\{3,4,5\}, b\in\{4,5,\cdots,12\}c\in\{1,2,\cdots,8\}. Tìm nghiệm nguyên dương của phương trình

x^6+ax^4+bx^2+c=y^3.

Continue reading “Tính rời rạc của tập số nguyên (2)”