Phương trình nghiệm nguyên bậc nhất

Nó cho thấy ước chung lớn nhất không chỉ là "thừa số chung lớn nhất" mà thực sự đạt được như một tổ hợp nguyên của $a$ và $b$ — sự kiện then chốt khiến tiêu chuẩn giải được của $ax+by=c$ hoạt động.

Xét tập $S=\{au+bv : u,v\in\mathbb{Z}\}\cap\mathbb{Z}_{>0}$ gồm mọi tổ hợp nguyên dương thực sự của $a$ và $b$. Vì $a,b$ không đồng thời bằng $0$, $S$ khác rỗng (chứa $|a|$ hoặc $|b|$), nên theo nguyên lý sắp thứ tự tốt, $S$ có phần tử nhỏ nhất $d=au_0+bv_0>0$.

Ta chứng minh $d\mid a$: chia $a=qd+r$ với $0\le r<d$. Khi đó $r=a-qd=a-q(au_0+bv_0)=a(1-qu_0)+b(-qv_0)$ chính là một tổ hợp nguyên của $a,b$. Nếu $r>0$ thì $r$ thuộc $S$ và nhỏ hơn $d$, mâu thuẫn với tính nhỏ nhất; vậy $r=0$, tức $d\mid a$. Lập luận y hệt với $b$ thay cho $a$ cho $d\mid b$.

Vì $d$ là ước chung của $a$ và $b$, $d\le \gcd(a,b)$. Ngược lại, mọi ước chung $e$ của $a$ và $b$ đều chia hết $au_0+bv_0=d$, nên $e\le d$; lấy $e=\gcd(a,b)$ cho $\gcd(a,b)\le d$.

Kết hợp hai bất đẳng thức, $d=\gcd(a,b)$, và theo cách xây dựng $d=au_0+bv_0$, đó chính xác là đẳng thức Bézout với $u=u_0,v=v_0$.

Nó giải quyết trọn vẹn bài toán: chỉ một phép kiểm tra chia hết quyết định tính giải được, và khi đã có một nghiệm bất kỳ, một họ một tham số theo $t$ cho ta mọi nghiệm khác — không cần đoán mò.

($\Rightarrow$) Nếu $(x,y)$ là nghiệm nguyên thì $d=\gcd(a,b)$ chia hết cả $ax$ và $by$, nên chia hết $ax+by=c$. Vậy $d \mid c$ là điều kiện cần.

($\Leftarrow$) Giả sử $d \mid c$, viết $c=de$. Theo đẳng thức Bézout tồn tại $u_0,v_0$ với $au_0+bv_0=d$. Nhân với $e$ cho $a(u_0e)+b(v_0e)=de=c$, nên $(x_0,y_0)=(u_0e,\,v_0e)$ là một nghiệm nguyên. Điều này chứng minh tính giải được.

Bây giờ cố định một nghiệm $(x_0,y_0)$ và cho $(x,y)$ là một nghiệm khác bất kỳ. Trừ $ax_0+by_0=c$ khỏi $ax+by=c$ cho $a(x-x_0)+b(y-y_0)=0$, tức $a(x-x_0)=-b(y-y_0)$. Chia cả hai vế cho $d$: $\frac{a}{d}(x-x_0)=-\frac{b}{d}(y-y_0)$, và vì $\gcd(a/d,\,b/d)=1$, thừa số $\frac{b}{d}$ phải chia hết $x-x_0$ (một hệ quả chuẩn của tính nguyên tố cùng nhau: nếu $p\mid mn$ và $\gcd(p,m)=1$ thì $p\mid n$). Vậy $x-x_0=\frac{b}{d}t$ với $t$ nguyên nào đó, và thay lại cho $y-y_0=-\frac{a}{d}t$.

Ngược lại, với mọi số nguyên $t$, thay $x=x_0+\frac{b}{d}t,\ y=y_0-\frac{a}{d}t$ vào $ax+by$ cho $ax_0+by_0+t\left(\frac{ab}{d}-\frac{ab}{d}\right)=c+0=c$, xác nhận mọi cặp như vậy đều là nghiệm. Vậy tập nghiệm chính xác là $x=x_0+\dfrac{b}{d}t,\ \ y=y_0-\dfrac{a}{d}t\ \ (t\in\mathbb{Z})$.