Đẳng thức Bézout

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