The Bézout's theorem and its corollary

The Bézout's theorem

Bézout's theorem tells us that:

$$ a \wedge b = 1 \Longleftrightarrow \exists (u, v) \in \hspace{0.05em}\mathbb{Z}^2, \enspace au + bv = 1 \qquad (Bézout) $$

Corollary of the Bézout's theorem

Bézout's theorem corollary tells us that::

$$ a \wedge bc = 1 \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} \Biggl \{ \begin{align*} a \wedge b = 1 \\ a \wedge c = 1 \end{align*} \qquad \bigl(Bézout \enspace (corollary)\bigr) $$

As well, for a simple product:

$$ ab \wedge cd = 1 \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} \left \{ \begin{align*} a \wedge c = 1 \\ a \wedge d = 1 \\ b \wedge c = 1 \\ b \wedge d = 1 \\ \end{align*} \right \} $$

And it is possible to generalize it for any product of integers:

$$ \left[ \ \prod_{i = 0}^n a_i \ \right] \wedge \Biggl[ \ \prod_{j = 0}^m b_j \ \Biggr] = 1 \Longleftrightarrow \forall (i, j) \in [\![1, n ]\!] \times [\![1, m ]\!], \enspace \Bigl \{a_i \wedge b_j = 1 \Bigr \} $$

Demonstration

The Bézout's theorem

Let \((a, b) \in \hspace{0.05em} \mathbb{Z}^2 \) be two integers.

1. From left to right implication

Let us assume that \(a \) and \(b \) are coprime.

In other words,

$$a \wedge b = 1 \Longleftrightarrow PGCD(a , b) = 1 $$

We know from the Bézout's identity that:

$$ \forall (a, b) \in \hspace{0.05em}\mathbb{N}^2, \enspace a > b, $$

$$ \delta = a \wedge b \hspace{0.2em} \Longrightarrow \hspace{0.2em} \exists (u, v) \in \hspace{0.05em}\mathbb{Z}^2, \enspace au + bv = \delta $$

Since we have assumed that \( a \wedge b = 1\), as a result we get:

$$ \forall (a, b) \in\hspace{0.1em}\mathbb{Z}^2, $$
$$ a \wedge b = 1 \Longrightarrow \exists (u, v) \in \hspace{0.05em}\mathbb{Z}^2, \enspace au + bv = 1 $$



2. Reciprocal

Conversely, let now assume that:

$$\exists (u, v) \in\hspace{0.1em}\mathbb{Z}^2, \enspace au + bv = 1 $$

Let consider \( d \), a common divisor of \( a \) and \( b\).

We know from the properties of divisibility that:

$$ \forall a \in (\mathbb{Z}^*), \enspace \forall (b , c) \in \hspace{0.05em} \mathbb{Z}^2, \enspace \exists (u , v) \in\hspace{0.1em}\mathbb{Z}^2, $$

$$ a/b \enspace et \enspace a/c \hspace{0.2em} \Longrightarrow \hspace{0.2em} a/(ub + vc) $$

\( d \) being a common divisor of \( a \) and \( b\), it divides \( a \), \( b \) as well as all the linear combinations of \( a \) and \( b \).

$$ d/a \enspace and \enspace d/b \hspace{0.2em} \Longrightarrow \hspace{0.2em} d/(au + bv) $$

Well, \(au + bv = 1\), so \( d / 1\).

The only number which divides \( 1\) is itself, then \( d = 1\).

It is the only common divisor of \( a \) and \( b\), so \( a \wedge b = 1 \).

$$ a \wedge b = 1 $$

Thus,

$$ \forall (a, b) \in\hspace{0.1em}\mathbb{Z}^2, $$
$$ \exists (u, v) \in\hspace{0.1em}\mathbb{Z}^2, \enspace au + bv = 1 \Longrightarrow a \wedge b = 1 $$



3. Equivalence

And as a result of both implications,

$$ \forall (a, b) \in \hspace{0.05em}\mathbb{Z}^2, $$

$$ a \wedge b = 1 \Longleftrightarrow \exists (u, v) \in \hspace{0.05em}\mathbb{Z}^2, \enspace au + bv = 1 \qquad (Bézout) $$

Corollary of the Bézout's theorem

Let \((a, b, c) \in \hspace{0.05em} \mathbb{Z}^3 \) be three integers.

1. From left to right implication

If \(a \wedge bc = 1 \), then with the Bézout's theorem, we do have this:

$$ a \wedge bc = 1 \Longleftrightarrow \exists (u, v) \in \hspace{0.05em}\mathbb{Z}^2, \enspace au + bcv = 1 $$

As a result we do notice that:

$$ au + b (cv) = 1 \Longleftrightarrow a \wedge b = 1 $$
$$ au + c (bv) = 1 \Longleftrightarrow a \wedge c = 1 $$

And finally,

$$ \forall (a, b, c) \in \hspace{0.1em}\mathbb{Z}^3, $$

$$ a \wedge bc = 1 \hspace{0.2em} \Longrightarrow \hspace{0.2em} \Biggl \{ \begin{align*} a \wedge b = 1 \\ a \wedge c = 1 \end{align*} $$

2. Reciprocal

If we do have this: \(\Biggl \{ \begin{align*} a \wedge b = 1 \\ a \wedge c = 1 \end{align*} \)

Then, still with the Bézout's theorem,

$$ \exists (u, v, u', v') \in \hspace{0.05em}\mathbb{Z}^4, \enspace \Biggl \{ \begin{align*} au + bv = 1 \hspace{2.8em} (1) \\ au' + cv' = 1 \qquad (2) \end{align*} $$

Performing the product \((1) \times (2) \), we do have this:

$$ (au + bv)(au' + cv') = 1 $$
$$ auau' + aucv' + bvau' + bv cv' = 1 $$
$$ a \hspace{0.1em} \underbrace { (uau' + ucv' + bvu')} _\text{ \(= \hspace{0.1em} U \)} \hspace{0.1em} + \hspace{0.1em} bc \hspace{0.1em} \underbrace { (vv') } _\text{ \(= \hspace{0.1em} V \)} \hspace{0.1em} = 1 $$

$$ a U + bcV = 1 \Longleftrightarrow a \wedge bc = 1 , \enspace with \enspace \Biggl \{ \begin{align*} U = uau' + ucv' + bvu'\\ V = vv' \end{align*} $$

Thus,

$$ \forall (a, b, c) \in \hspace{0.1em}\mathbb{Z}^3, $$

$$ \Biggl \{ \begin{align*} a \wedge b = 1 \\ a \wedge c = 1 \end{align*} \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \wedge bc = 1 $$




3. Equivalence

And as a result of both implications, we do obtain the following equivalence:

$$ \forall (a, b, c) \in \hspace{0.05em}\mathbb{Z}^3, $$

$$ a \wedge bc = 1 \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} \Biggl \{ \begin{align*} a \wedge b = 1 \\ a \wedge c = 1 \end{align*} \qquad \bigl(Bézout \enspace (corollary)\bigr) $$




4. Product of two numbers

1. From left to right implication

If we now take the hypothesis where \(ab \wedge cd = 1 \), then again with the Bézout's theorem, we do have:

$$ ab \wedge cd = 1 \Longleftrightarrow \exists (u, v) \in \hspace{0.05em}\mathbb{Z}^2, \enspace abu + cdv = 1 $$

Now, we can apply the theorem four times from this equivalence and:

$$ \left \{ \begin{align*} a(bu) + c(dv) = 1 \Longleftrightarrow a \wedge c = 1 \\ a(bu) + d(cv) = 1 \Longleftrightarrow a \wedge d = 1 \\ b(au) + c(dv) = 1 \Longleftrightarrow b \wedge c = 1 \\ b(au) + d(cv) = 1 \Longleftrightarrow b \wedge d = 1 \end{align*} \right \}$$

As a result we obtain,

$$ \forall (a, b, c, d) \in \hspace{0.05em}\mathbb{Z}^4, $$

$$ ab \wedge cd = 1 \hspace{0.2em} \Longrightarrow \hspace{0.2em} \left \{ \begin{align*} a \wedge c = 1 \\ a \wedge d = 1 \\ b \wedge c = 1 \\ b \wedge d = 1 \\ \end{align*} \right \} $$




2. Reciprocal

If we retrieve the previous ipplication and we try to verify its reciprocal, we do startfrom this hypothesis:

$$ \left \{ \begin{align*} a \wedge c = 1 \\ a \wedge d = 1 \\ b \wedge c = 1 \\ b \wedge d = 1 \\ \end{align*} \right \} $$

By applying the Bézout's theorem, we do have this:

$$ \left \{ \begin{align*} a \wedge c = 1 \\ a \wedge d = 1 \\ b \wedge c = 1 \\ b \wedge d = 1 \\ \end{align*} \right \} \Longleftrightarrow $$

$$ \exists (u_1, v_1, u_2, v_2, u_3, v_3, u_4, v_4) \in \hspace{0.05em}\mathbb{Z}^8, \enspace \left \{ \begin{align*} au_1 + cv_1 = 1 \\ au_2 + dv_2 = 1 \\ bu_3 + cv_3 = 1 \\ bu_4 + dv_4 = 1 \\ \end{align*} \right \}$$

Indeed, by performing the product of these four expressions, we do obtain:

$$(au_1 + cv_1)(au_2 + dv_2)(bu_3 + cv_3)( bu_4 + dv_4) = 1 $$

Now, when distributing all this, we do obtain a kind of tree, when each term will contain either \(ab\), nor \(cd\):

$$ \begin{align*} au_1 \hspace{4em} cv_1 \\ \hspace{1em} \downarrow \hspace{0.05em} \searrow \hspace{0.05em} \swarrow \hspace{0.05em} \downarrow \\ \hspace{1em} \downarrow \hspace{0.05em} \swarrow \hspace{0.05em} \searrow \hspace{0.05em} \downarrow \\ au_2 \hspace{4em} dv_1 \\ \hspace{1em} \downarrow \hspace{0.05em} \searrow \hspace{0.05em} \swarrow \hspace{0.05em} \downarrow \\ \hspace{1em} \downarrow \hspace{0.05em} \swarrow \hspace{0.05em} \searrow \hspace{0.05em} \downarrow \\ bu_3 \hspace{4em} cv_3 \\ \hspace{1em} \downarrow \hspace{0.05em} \searrow \hspace{0.05em} \swarrow \hspace{0.05em} \downarrow \\ \hspace{1em} \downarrow \hspace{0.05em} \swarrow \hspace{0.05em} \searrow \hspace{0.05em} \downarrow \\ bu_4 \hspace{4em} dv_4 \\ \end{align*} $$

$$ \begin{align*} \ \ \ \ \textcolor{#8E5B5B}{a} u_1 au_2 \textcolor{#8E5B5B}{b} u_3 b u_4 \qquad (1^{st} \ column) \\ + \ \textcolor{#8E5B5B}{a} u_1 au_2 \textcolor{#8E5B5B}{b} u_3 d v_4 \qquad (3 \ first \ elements \ of \ the \ 1^{st} \ column - \ 4^{th} \ element \ of \ the \ 2^{nd}) \\ + \ \textcolor{#8E5B5B}{a} u_1 au_2 c v_3 \textcolor{#8E5B5B}{b} u_4 \qquad (2 \ first \ elements \ of \ the \ 1^{st} \ column - \ 3^{rd} \ element \ of \ the \ 2^{nd} - \ 4^{th} \ element \ of \ the \ 1^{st} ) \\ + \ ... \\ + \ \textcolor{#446e4f}{c} v_1 \textcolor{#446e4f}{d} v_1 b u_3 dv_4 \qquad (2 \ first \ elements \ of \ the \ 2^{nd} \ column - \ 3^{rd} \ element \ of \ the \ 1^{st} - \ 4^{th} \ element \ of \ the \ 2^{nd} ) \\ + \ \textcolor{#446e4f}{c} v_1 \textcolor{#446e4f}{d} v_1 cv_3 b u_4 \qquad (3 \ first \ elements \ of \ the \ 2^{nd} \ column - \ 4^{th} \ element \ of \ the \ 1^{st}) \\ + \ \textcolor{#446e4f}{c} v_1 \textcolor{#446e4f}{d} v_1 cv_3 dv_4 \qquad (2^{nd} \ column) \\ \end{align*} $$

such as, after having gathered all these terms according to \(ab\) or \(cd\): \(\exists (U, V) \in \hspace{0.05em} \mathbb{Z}^2, \ abU + cdV = 1\)




3. Equivalence

And as a result of both implications, we do obtain the following equivalence:

$$ \forall (a, b, c, d) \in \hspace{0.05em}\mathbb{Z}^4, $$

$$ ab \wedge cd = 1 \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} \left \{ \begin{align*} a \wedge c = 1 \\ a \wedge d = 1 \\ b \wedge c = 1 \\ b \wedge d = 1 \\ \end{align*} \right \} $$




5. Generalization for any product

By applying the previous reasoning, but for any product of integers, we can generalize this corollary by claiming that:

$$ \forall (n,m) \in \hspace{0.05em}\mathbb{N}^2, \ \forall (a_1, a_2,... \ a_n) \in \hspace{0.05em}\mathbb{Z}^n, \ \forall (b_1, b_2,... \ b_m) \in \hspace{0.05em}\mathbb{Z}^m, $$

$$ \left[ \ \prod_{i = 0}^n a_i \ \right] \wedge \Biggl[ \ \prod_{j = 0}^m b_j \ \Biggr] = 1 \Longleftrightarrow \forall (i, j) \in [\![1, n ]\!] \times [\![1, m ]\!], \enspace \Bigl \{a_i \wedge b_j = 1 \Bigr \} $$