Editing Bézout's identity (section)

== Existence proof ==

Given any nonzero integers {{mvar|a}} and {{mvar|b}}, let {{math|1=''S'' = {{mset|''ax'' + ''by'' | ''x'', ''y'' ∈ '''Z''' and ''ax'' + ''by'' > 0}}}}. The set {{mvar|S}} is nonempty since it contains either {{mvar|a}} or {{math|–''a''}} (with {{math|1=''x'' = ±1}} and {{math|1=''y'' = 0}}). Since {{mvar|S}} is a nonempty set of positive integers, it has a minimum element {{math|1=''d'' = ''as'' + ''bt''}}, by the [[well-ordering principle]]. To prove that {{mvar|d}} is the greatest common divisor of {{mvar|a}} and {{mvar|b}}, it must be proven that {{mvar|d}} is a common divisor of {{mvar|a}} and {{mvar|b}}, and that for any other common divisor {{mvar|c}}, one has {{math|''c'' ≤ ''d''}}.

The [[Euclidean division]] of {{mvar|a}} by {{mvar|d}} may be written as
<math display="block">a=dq+r\quad\text{with}\quad 0\le r<d.</math>
The remainder {{mvar|r}} is in {{math|''S'' ∪ {{mset|0}}}}, because
<math display="block">\begin{align}
r  & = a - qd \\
& = a - q(as+bt)\\
& = a(1-qs) - bqt.
\end{align}</math>
Thus {{mvar|r}} is of the form {{math|''ax'' + ''by''}}, and hence {{math|''r'' ∈ ''S'' ∪ {{mset|0}}}}. However, {{math|0 ≤ ''r'' < ''d''}}, and {{mvar|d}} is the smallest positive integer in {{mvar|S}}: the remainder {{mvar|r}} can therefore not be in {{mvar|S}}, making {{mvar|r}} necessarily 0. This implies that {{mvar|d}} is a divisor of {{mvar|a}}. Similarly {{mvar|d}} is also a divisor of {{mvar|b}}, and therefore {{mvar|d}} is a common divisor of {{mvar|a}} and {{mvar|b}}.

Now, let {{mvar|c}} be any common divisor of {{mvar|a}} and {{mvar|b}}; that is, there exist {{mvar|u}} and {{mvar|v}} such that {{math|1=''a'' = ''cu''}} and {{math|1=''b'' = ''cv''}}. One has thus
<math display="block">\begin{align}
d&=as + bt\\
& =cus+cvt\\
&=c(us+vt).
\end{align} </math>
That is, {{mvar|c}} is a divisor of {{mvar|d}}. Since {{math|''d'' > 0}}, this implies {{math|''c'' ≤ ''d''}}.