Trong phần này ta bàn đến các phương trình dạng $ax+by=c$, (với $a,\,b,\,c$ là những hằng số nguyên) và một số vấn đề xoay quanh chủ đề đó như điều kiện có nghiệm, cấu trúc tập nghiệm hay các số Frobenius.
Trước tiên, từ Định lý4.4 ta có ngay định lý sau đây.
Định lý 8.1. Điều kiện cần và đủ cho phương trình \[ax+by=n\] để có nghiệm nguyên $x,\,y$ là $\gcd\left(a,\,b\right)\mid n$
Đồng thời ta cũng có khẳng định sau
Định lý 8.2. Với $\gcd\left(a,\,b\right)=1$ và $x_0,\,y_0$ là một tập của các nghiệm để \[ax+by=n,\,\quad\quad (1)\] lúc đó mọi tập của (1) được cho bởi \[x=x_0+bt,\, \quad y=y_0-at.\] Tuy nhiên cho số nguyên $t$ bất kì thì chúng là nghiệm của $1$.
Chứng minh. Từ $ax+by=n$ và $ax_0+by_0=n$ ta có $a\left(x-x_0\right)+b\left(y-y_0\right).$ Khi $\gcd\left(a,\,b\right)=1$ chúng ta kết luận rằng $a\mid \left(y-y_o\right).$ Chọn $y=y_0-at,$ tức là $x=x_0+bt.$ Kế quả cần tìm ở việc loại bỏ chúng ra khỏi $\left(1\right)$.
$\square$
Bây giờ là bài toán với số Frobenius.
Định lý 8.3. Với $\gcd\left(a,\,b\right)=1,\ a>0,\, b>0$ lúc đó mọi số nguyên lớn hơn $ab-a-b$ là biểu diễn ở dạng $ax+by(x\ge 0,\,y\ge 0).$ Tuy nhiên, $ab-a-b$ không biểu diễn ở dạng đó.
Chứng minh. Từ Định lý 8.2 ta biết được những nghiệm của phương trình $ax+by=n$ như sau \[x=x_0+bt,\, \quad y=y_0-at.\] Giờ ta chọn những $t$ sao cho $x,\,y$ không âm. Ta có thể chọn $t$ sao cho $0\le y_0-at<a,\,$ hoặc $0\le y_0-at<a_{-1}.$ Từ giả thiết ta có \[\left(x_0+bt\right)a=n-\left(y_0-at\right)b>ab-a-b-\left(a-1\right)b=\left(-a\right)\] hoặc \[x_0+bt>\left(-1\right)\] vậy \[x_0+bt\ge 0.\] Cuối cùng giả sử điều không thể là \[ab-a-b=ax+by,\,\quad x\ge 0,\,y\ge 0.\] Từ đó ta có \[ab=(x+1)a+(y+1)b\ge 2ab,\] vô lý.
$\square$
Định lý trên có thể hiểu như sau: Nếu $a>0,\, b>0,\,\gcd\left(a,\,b\right)=1,$ lúc đó $ab-a-b$ là số nguyên lớn nhất không thể biểu diễn ở dạng $ax+by; \left(x\ge 0,\,y\ge 0\right)$ ta có thể tổng quát hoá thành vấn đề sau: Với $a,\,b,\,c$ là ba số nguyên dương thoả mãn $\gcd\left(a,\,b,\,c\right)=1.$ Xác định số nguyên lớn nhất không biểu diễn được ở dạng $ax+by+cz$ với $x\ge 0,\,y\ge 0,\,z\ge 0)$. Đây là một vấn đề cực khó!
Phần cuối của mục này tôi đưa ra một số bài tập sau:
Bài tập 1. Với $a>0,\, b>0,\,\gcd\left(a,\,b\right)=1.$ Lúc đó số những nghiệm nguyên dương của phương trình $ax+by=n$ bằng \[\left\lfloor {\dfrac{n}{{ab}}} \right\rfloor \;\text{hoặc}\; \left\lfloor {\dfrac{n}{{ab}}} \right\rfloor + 1. \]
(Gợi ý: $\left\lfloor \alpha \right\rfloor – \left\lfloor \beta \right\rfloor = \left\lfloor {\alpha – \beta } \right\rfloor $ hoặc $\left\lfloor {\alpha – \beta } \right\rfloor + 1$)
Bài tập 2. Với $a,\,b,\,c$ là những số nguyên dương sao cho chúng đôi một nguyên tố cùng nhau. Xác định số nguyên dương lớn nhất sao cho nó không biểu diễn được dưới dạng \[bcx+cay+abz,\,\quad x\ge 0,\,y\ge 0,\,z\ge 0.\]
(\textit{Đáp án:} Số nguyên dương cần tìm đó là $2abc-ab-bc-ca.$)
Bài tập 3. Xác định số nghiệm của phương trình sau \[x+2y+3z=n,\,\quad\;x\ge 0,\,y\ge 0,\,z\ge 0.\]
(Gợi ý: Số nghiệm phải tìm là hệ số của $x^{n}$ trong khai triển chuỗi luỹ thừa sau \[\dfrac{1}{{(1 – x)(1 – {x^2})(1 – {x^3})}}.\] Chuỗi luỹ thừa có thể thu được nhờ một phương pháp của phân thức đơn giản. Đáp án: \[\dfrac{{{{(n + 3)}^2}}}{{12}} – \dfrac{7}{{72}} + \dfrac{{{{( – 1)}^n}}}{8} + \dfrac{2}{8}\cos \dfrac{{2n\pi }}{3}\]
Bài tập 4. Một con gà trống, năm cent; một con gà mái, ba cent; ba con gà con, một cent. Một trăm con gà, (cả gà trống gà mái và gà con) là một trăm cent hỏi có bao nhiêu con gà trống bao nhiêu con gà mái và bao nhiêu con gà con?
No comments
Comments feed for this article
Trackback link: http://songha.maths.vn/cac-phuong-trinh-tuyen-tinh-bat-dinh/trackback/