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

Một cách toán học, ta có bài toán sau:

Bài toán Frobenius. Cho tập A=\{a_1,a_2,\ldots,a_d\} gồm d>1 số nguyên dương lớn hơn 1 sao cho \gcd (a_1,a_2,\ldots,a_d)=1. Một số tự nhiên n được gọi là biểu diễn được theo tập A nếu tồn tại các số tự nhiên m_1,m_2,\ldots,m_d sao cho \displaystyle n=\sum_{i=1}^d m_ia_i. Tìm số tự nhiên lớn nhất không biểu diễn được theo tập A.

Kết quả của bài toán này được gọi là số Frobenius của A và được ký hiệu bởi g(a_1,a_2,\ldots,a_d). Định lí sau chứng tỏ các số này tồn tại.

Định lí 2. Tồn tại số nguyên N sao cho mọi số nguyên s\geq N đều biểu diễn được theo A.

Chứng minh. Ta sẽ chứng minh bằng quy nạp theo d.

Do định lí 1 nên khẳng định đúng với d=2.

Giả sử khẳng định đúng với d=k-1\,(k>2,k\in\mathbb{Z}). Ta đi chứng minh khẳng định đúng với d=k.

Đặt x=\gcd (a_1,a_2,\ldots,a_{k-1})a'_i=a_i/x. Vì \gcd (a'_1,a'_2,\ldots,a'_{k-1})=1 nên theo giả thiết quy nạp, tồn tại số nguyên \alpha sao cho mọi số nguyên y\geq\alpha đều biểu diễn được theo A'=\{a'_i\}.

Chọn N=\alpha x+(x-1)a_k và cố định một số nguyên s\geq N.

Do \gcd (a_1,a_2,\ldots,a_k)=1 nên \gcd (x,a_k)=1, suy ra tồn tại số tự nhiên x_k<x sao cho s\equiv a_kx_k\pmod{x}. Ta thấy \dfrac{s-a_kx_k}{x} là số nguyên không bé hơn \displaystyle \frac{\alpha x+(x-1)a_k-a_kx_k}{x}=\alpha+\frac{a_k(x-1-x_k)}{x}\geq\alpha suy ra tồn tại các số tự nhiên x_1,x_2,\ldots,x_{k-1} để \displaystyle \frac{s-a_kx_k}{x}=a'_1x_1+a'_2x_2+\cdots+a'_{k-1}x_{k-1}, do đó s=a_1x_1+a_2x_2+\cdots+a_kx_k. Vậy khẳng định đúng với d=k và bởi thế nó đúng với mọi số nguyên d>1. \Box

Không có công thức tính các số Frobenius với d>2 trong trường hợp tổng quát. Ở phần tiếp theo của bài chúng tôi sẽ giới thiệu công thức tính các số Frobenius với d=2.

Định lí 3. Nếu a_1,a_2>1 là hai số nguyên dương nguyên tố cùng nhau thì

g(a_1,a_2)=a_1a_2-a_1-a_2.

Để chứng minh định lí này ta cần bổ đề sau.

Bổ đề. Cho a,b là hai số nguyên dương nguyên tố cùng nhau và n\in [ab-1]. Khi đó nếu n không chia hết cho a và không chia hết cho b thì N(a,b; n)+N(a,b; ab-n)=1.

Chứng minh của bổ đề. Dùng kết quả \{x\}+\{-x\}=1,\quad \forall x\in\mathbb{R}\setminus\mathbb{Z} và định lí 1 ta có

\displaystyle N(a,b; ab-n)=\frac{ab-n}{ab}-\left\{\frac{b^{-1}(ab-n)}{a}\right\}-\left\{\frac{a^{-1}(ab-n)}{b}\right\}+1

\displaystyle =2-\frac{n}{ab}-\left\{\frac{-b^{-1}n}{a}\right\}-\left\{-\frac{a^{-1}n}{b}\right\}

\displaystyle =-\frac{n}{ab}+\left\{\frac{b^{-1}n}{a}\right\}+\left\{\frac{a^{-1}n}{b}\right\}

=1-N(a,b;n). \Box

Ta quay lại chứng minh định lí.

Chứng minh của định lí 3.a_1+a_2 là số nguyên dương không chia hết cho a_1, không chia hết cho a_2 và bé hơn a_1a_2 nên theo bổ đề ta có N(a_1,a_2;a_1+a_2)+N(a_1,a_2; a_1a_2-a_1-a_2)=1,

N(a_1,a_2;a_1+a_2)=1, suy ra N(a_1,a_2; a_1a_2-a_1-a_2)=0 hay a_1a_2-a_1-a_2 không biểu diễn được theo \{a_1,a_2\}.

Với mọi số nguyên n> a_1a_2-a_1-a_2 ta có

\displaystyle N(a_1,a_2; n)=\frac{n}{a_1a_2}-\left\{\frac{a_1^{-1}n}{a_2}\right\}-\left\{\frac{a_2^{-1}n}{a_1}\right\}+1

\displaystyle >\frac{a_1a_2-a_1-a_2}{a_1a_2}-\left(1-\frac{1}{a_1}\right)-\left(1-\frac{1}{a_2}\right)+1=0,

suy ra n biểu diễn được theo \{a_1,a_2\}. \Box

Ta tiếp tục xét trường hợp d=2. Từ các kết quả trên ta thấy nếu số nguyên dương n không biểu diễn được theo \{a_1,a_2\} thì n\leq a_1a_2-a_1-a_2 và có ít nhất hai số nguyên dương không biểu diễn được theo \{a_1,a_2\}1a_1a_2-a_1-a_2. Vậy có tất cả bao nhiêu số nguyên dương không biểu diễn được theo \{a_1,a_2\}? Định lí sau trả lời câu hỏi đó.

Định lí 4. (Silvester) Nếu a_1,a_2>1 là hai số nguyên dương nguyên tố cùng nhau thì số các số nguyên dương không biểu diễn được theo \{a_1,a_2\}\dfrac{(a_1-1)(a_2-1)}{2}.

Chứng minh. Xét số nguyên dương n\in [a_1a_2-a_1-a_2]\subset [a_1a_2-1]. Nếu n chia hết cho a_1 hoặc a_2 thì n biểu diễn được theo \{a_1,a_2\}, trong trường hợp còn lại, theo bổ đề thì đúng một trong hai số na_1a_2-n biểu diễn được theo \{a_1,a_2\}. Mặt khác, có đúng (a_1-1)(a_2-1) số trong [a_1a_2-1] không chia hết cho a_1 và không chia hết cho a_2, suy ra số các số nguyên dương không biểu diễn được theo \{a_1,a_2\}\dfrac{(a_1-1)(a_2-1)}{2}. \Box

Chú ý. Không dùng công thức Popoviciu ta vẫn chứng minh được các định lí 3 và 4. Ta cần các bổ đề sau:

Bổ đề 1. Với mỗi số nguyên n, tồn tại duy nhất cặp

(\alpha_n,\beta_n)\in\mathbb{Z}\times \{0,1,\ldots,a_1-1\} sao cho n=a_1\alpha_n+a_2\beta_n.

Chứng minh. Với mọi số nguyên n, cố định nó.

\gcd (a_1,a_2)=1 nên tập \{n-\beta a_2|\beta=0,1,\ldots,a_1-1\} là một hệ thặng dư đầy đủ modulo a_1, suy ra tồn tại \beta_n\in \{0,1,\ldots,a_1-1\} để n-\beta_n a_2 chia hết cho a_1. Do đó tồn tại cặp (\alpha_n,\beta_n)\in\mathbb{Z}\times \{0,1,\ldots,a_1-1\} sao cho n=a_1\alpha_n+a_2\beta_n. Nếu cặp (\alpha'_n,\beta'_n)\in\mathbb{Z}\times \{0,1,\ldots,a_1-1\} cũng thỏa mãn n=a_1\alpha'_n+a_2\beta'_n thì ta có a_2\beta_n\equiv a_2\beta'_n\pmod{a_1}, do \gcd (a_1,a_2)=1 nên từ đây ta có \beta_n\equiv\beta'_n\pmod{a_1}, suy ra \beta_n=\beta'_n (vì \beta_n,\beta'_n\in \{0,1,\ldots,a_1-1\}), và bởi thế \alpha_n=\alpha'_n. \Box

Bổ đề 2. Với mỗi số nguyên n, n biểu diễn được theo tập \{a_1,a_2\} khi và chỉ khi \alpha_n\geq 0.

Chứng minh. Với mọi số nguyên n, cố định nó. Nếu \alpha_n\geq 0 thì n biểu diễn được theo tập \{a_1,a_2\}.

Bây giờ ta giả sử n biểu diễn được theo tập \{a_1,a_2\}. Tồn tại các số tự nhiên \alpha'_n,\beta'_n sao cho n=\alpha'_na_1+\beta'_na_2. Chia \beta'_n cho a_1 ta được \beta'_n=qa_1+\beta_n, suy ra \alpha_n=\alpha'_n+qa_2\geq 0. \Box

Bổ đề 3. Với mỗi số tự nhiên n\in\{0,1,\ldots,a_1a_2-a_1-a_2\}, đúng một trong hai số na_1a_2-a_1-a_2-n biểu diễn được theo tập \{a_1,a_2\}.

Chứng minh. Với mỗi số tự nhiên n\in\{0,1,\ldots,a_1a_2-a_1-a_2\}, cố định nó. Vì a_1a_2-a_1-a_2=a_1(-1)+a_2(a_1-1)-1<0 nên theo bổ đề 2, số a_1a_2-a_1-a_2 không biểu diễn được theo tập \{a_1,a_2\}.

Hai số na_1a_2-a_1-a_2-n không thể cùng biểu diễn được theo tập \{a_1,a_2\}, vì nếu ngược lại, tổng của chúng bằng a_1a_2-a_1-a_2 cũng biểu diễn được theo tập \{a_1,a_2\}.

Bây giờ ta giả sử n không biểu diễn được theo tập \{a_1,a_2\}.

Viết n=\alpha_na_1+\beta_na_2 với (\alpha_n,\beta_n)\in\mathbb{Z}\times \{0,1,\ldots,a_1-1\}. Theo bổ đề 2 ta có ngay \alpha_n<0, suy ra a_1a_2-a_1-a_2-n biểu diễn được theo tập \{a_1,a_2\}a_1a_2-a_1-a_2-n=a_1(-1-\alpha_n)+a_2(a_1-1-\beta_n)-1-\alpha_n\geq 0,\, 0\leq a_1-1-\beta_n\leq a_1-1. \Box

Bây giờ ta quay trở lại chứng minh định lí 3 và 4.

Chứng minh thứ hai của định lí 3. Trong chứng minh của bổ đề 3 ta đã thấy a_1a_2-a_1-a_2 không biểu diễn được theo tập \{a_1,a_2\}.

Bây giờ ta còn phải chỉ ra mọi số nguyên n>a_1a_2-a_1-a_2 đều biểu diễn được theo tập \{a_1,a_2\}.

Cố định số nguyên n>a_1a_2-a_1-a_2. Theo bổ đề 1, tồn tại duy nhất cặp

(\alpha_n,\beta_n)\in\mathbb{Z}\times \{0,1,\ldots,a_1-1\} sao cho n=a_1\alpha_n+a_2\beta_n. Ta có

a_1\alpha_n=n-a_2\beta_n>a_1a_2-a_1-a_2-a_2(a_1-1)=-a_1, suy ra \alpha_n>-1, do đó \alpha_n\geq 0. Từ bổ đề 2 ta có n biểu diễn được theo tập \{a_1,a_2\}. \Box

Chứng minh thứ hai của định lí 4.0 và các số tự nhiên n>a_1a_2-a_1-a_2 đều biểu diễn được theo tập \{a_1,a_2\} nên số các số nguyên dương không biểu diễn được theo tập \{a_1,a_2\} bằng số phần tử của \{0,1,\ldots,a_1a_2-a_1-a_2\} không biểu diễn được theo tập \{a_1,a_2\}.

Tập hợp \{0,1,\ldots,a_1a_2-a_1-a_2\} có thể phân hoạch thành các khối

\displaystyle \left\{n,a_1a_2-a_1-a_2-n\right\},\,\, n=0,1,\ldots, \frac{(a_1-1)(a_2-1)}{2}-1.

Theo bổ đề 3, mỗi khối này chứa đúng một phần tử không biểu diễn được theo tập \{a_1,a_2\}, suy ra số các số nguyên dương không biểu diễn được theo \{a_1,a_2\}\dfrac{(a_1-1)(a_2-1)}{2}. \Box

3. Bài tập

Bài 1. Cho a,b là hai số nguyên dương nguyên tố cùng nhau. Một số nguyên n được gọi là tốt nếu tồn tại các số nguyên dương x,y sao cho ax+by=n.

1) Tìm số nguyên lớn nhất không là số tốt;

2) Có bao nhiêu số nguyên dương không là số tốt?

Bài 2. Trên đường thẳng thực, tô đỏ tất cả các điểm ứng với các số nguyên có dạng 81x+100y, ở đây xy là các số nguyên dương. Tô các điểm nguyên còn lại màu xanh. Tìm điểm P trên đường thẳng sao cho với mỗi số nguyên T, đối xứng của T qua P là một điểm nguyên có màu khác T.

Bài 3. Cho các số nguyên dương a,bc đôi một nguyên tố cùng nhau. Chứng minh rằng 2abc-ab-bc-ca là số nguyên lớn nhất không viết được dưới dạng xab+ybc+zca, ở đây x,y,z là các số tự nhiên.

Bài 4. Cho hai số nguyên dương a,b>1. Chứng minh rằng nếu \gcd (a,b)=1 thì N(a,b;a+b)=1.

Bài 5. Cho hai số nguyên dương a,b>1. Chứng minh rằng nếu \gcd (a,b)=1 thì N(a,b;n+ab)=1+N(a,b;n),\quad\forall n\in\mathbb{N}.

Bài 6.

1) Cho hai điểm nguyên khác nhau A(a_1;a_2)B(b_1;b_2). Chứng minh rằng trên đoạn thẳng AB có đúng 1+\gcd (b_1-a_1,b_2-a_2) điểm nguyên.

2) Chứng minh rằng nếu ab là các số nguyên dương thì

\displaystyle \gcd (a,b)=2\sum_{k=1}^{b-1}\left[\frac{ka}{b}\right]+a+b-ab.

Bài 7. Cho hai số nguyên dương a,b không nguyên tố cùng nhau. Tìm một công thức tính số nghiệm tự nhiên của phương trình ax+by=n, ở đây n là số tự nhiên cho trước.

Bài 8.  Với các số nguyên dương an. Xét phương trình a^2x+6ay+36z=n trên \mathbb{N}.

1) Tìm tất cả a để mỗi n\geq 250, phương trình có nghiệm;

2) Cho a>1a nguyên tố cùng nhau với 6. Tìm n lớn nhất để phương trình vô nghiệm.

Bài 9. Cho a, b, c là các số nguyên dương đôi một nguyên tố cùng nhau. Số nguyên dương n được gọi là bướng bỉnh nếu nó không có dạng n = bcx+cay+abz, với x, y, z \in\mathbb{N}^*. Hỏi có tất cả bao nhiêu số bướng bỉnh?

Bài 10. Cho các số nguyên dương a,\ b,\ c đôi một nguyên tố cùng nhau. Gọi g(a, b, c) là số nguyên lớn nhất không biểu diễn được dưới dạng xa+yb+zc với các số nguyên dương x,\ y,\ z. Tìm hằng số k lớn nhất sao cho g(a, b, c)\ge k\sqrt{abc} với mọi a,\ b,\ c nguyên dương và đôi một nguyên tố cùng nhau.

Bài 11. Cho S là một tập các số nguyên thỏa mãn đồng thời hai điều kiện

1) tồn tại a,b \in S sao cho \gcd(a,b)=\gcd(a-2,b-2)=1;

2) nếu xy là các phần tử của S (có thể bằng nhau ), thì x^2-y cũng là phần tử của S.

Chứng minh rằng S=\mathbb{Z}.

Bài 12. Cho F là một tập con của tập các số nguyên dương với ít nhất hai phần tử và P(x) \in \mathbb Z[X] thỏa mãn: Với mọi a,b\in F, ta có a+b \in F\gcd(P(a),P(b))=1. Chứng minh P(x) là đa thức hằng.

Bản pdf có thể có tại https://nttuan.org/download/

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s