Editing Bézout's identity (section)

== Structure of solutions ==

If {{math|''a''}} and {{math|''b''}} are not both zero and one pair of Bézout coefficients {{math|(''x'', ''y'')}} has been computed (for example, using the [[extended Euclidean algorithm]]), all pairs can be represented in the form
<math display=block>\left(x-k\frac{b}{d},\ y+k\frac{a}{d}\right),</math>
where {{math|''k''}} is an arbitrary integer, {{math|''d''}} is the greatest common divisor of {{math|''a''}} and {{math|''b''}}, and the fractions simplify to integers.

If {{mvar|a}} and {{mvar|b}} are both nonzero and none of them divides the other, then exactly two of the pairs of Bézout coefficients satisfy 
<math display="block"> |x| < \left |\frac{b}{d}\right |\quad \text{and}\quad |y| < \left |\frac{a}{d}\right |.</math> If {{mvar|a}} and {{mvar|b}} are both positive, one has <math>x>0</math> and <math>y<0</math> for one of these pairs, and <math>x<0</math> and <math>y>0</math> for the other. If {{math|''a'' > 0}} is a divisor of {{mvar|b}} (including the case <math>b=0</math>), then one pair of Bézout coefficients is {{math|(1, 0)}}.

This relies on a property of [[Euclidean division]]: given two non-zero integers {{math|''c''}} and {{math|''d''}}, if {{mvar|d}} does not divide {{mvar|c}}, there is exactly one pair {{math|(''q'', ''r'')}} such that {{math|1=''c'' = ''dq'' + ''r''}} and {{math|0 < ''r'' < {{abs|''d''}}}}, and another one such that {{math|1=''c'' = ''dq'' + ''r''}} and {{math|1=−{{abs|''d''}} < ''r'' < 0}}.

The two pairs of small Bézout's coefficients are obtained from the given one {{math|(''x'', ''y'')}} by choosing for {{mvar|k}} in the above formula either of the two integers next to {{math|{{sfrac|''x''|''b''/''d''}}}}.

The extended Euclidean algorithm always produces one of these two minimal pairs.

=== Example ===

Let {{math|1=''a'' = 12}} and {{math|1=''b'' = 42}}, then {{math|1=gcd (12, 42) = 6}}. Then the following Bézout's identities are had, with the Bézout coefficients written in red for the minimal pairs and in blue for the other ones.

<math display="block">\begin{align}
\vdots \\
12 &\times ({\color{blue}{-10}}) & + \;\; 42  &\times \color{blue}{3} &= 6 \\
12 &\times ({\color{red}{-3}}) & + \;\;42  &\times \color{red}{1} &= 6 \\
12 &\times \color{red}{4}  & + \;\;42  &\times({\color{red}{-1}}) &= 6 \\
12 &\times \color{blue}{11} & + \;\;42  &\times ({\color{blue}{-3}}) &= 6 \\
12 &\times \color{blue}{18} & + \;\;42  &\times ({\color{blue}{-5}}) &= 6 \\
\vdots
\end{align}</math>

If {{math|1=(''x'', ''y'') = (18, −5)}} is the original pair of Bézout coefficients, then {{math|{{sfrac|18|42/6}} ∈ [2, 3]}} yields the minimal pairs via {{math|1=''k'' = 2}}, respectively {{math|1=''k'' = 3}}; that is, {{math|1=(18 − 2 ⋅ 7, −5 + 2 ⋅ 2) = (4, −1)}}, and {{math|1=(18 − 3 ⋅ 7, −5 + 3 ⋅ 2) = (−3, 1)}}.