The Bézout's theorem and its corollary

From left to right implication

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

In other words,

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

Reciprocal

Conversely, let now assume that:

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

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

Well, \(au + bv = 1\), so \( d \mid 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 \).

Thus,

Equivalence

And as a result of both implications,

From left to right implication

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

As a result we do notice that:

And finally,

Reciprocal

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

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

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

Thus,

Equivalence

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

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.04em}\mathbb{Z}^2, \enspace abu + cdv = 1 $$

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

   $$ \left \{ \begin{gather*} 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{gather*} \right \}$$

   As a result we obtain,

   $$ \forall (a, b, c, d) \in \hspace{0.04em}\mathbb{Z}^4, $$
   $$ ab \wedge cd = 1 \hspace{0.2em} \Longrightarrow \hspace{0.2em} \left \{ \begin{gather*} a \wedge c = 1 \\ a \wedge d = 1 \\ b \wedge c = 1 \\ b \wedge d = 1 \\ \end{gather*} \right \} $$

2. Reciprocal

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

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

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

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

   $$ \exists (u_1, v_1, u_2, v_2, u_3, v_3, u_4, v_4) \in \hspace{0.04em}\mathbb{Z}^8, \enspace \left \{ \begin{gather*} au_1 + cv_1 = 1 \\ au_2 + dv_2 = 1 \\ bu_3 + cv_3 = 1 \\ bu_4 + dv_4 = 1 \\ \end{gather*} \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 \(\textcolor{rgb(232 124 124)}{ab}\) or \(\textcolor{rgb(93 183 129)}{cd}\):

   $$ \begin{gather*} au_1 \hspace{4em} cv_1 \\ \hspace{1em} \downarrow \hspace{0.04em} \searrow \hspace{0.04em} \swarrow \hspace{0.04em} \downarrow \\ \hspace{1em} \downarrow \hspace{0.04em} \swarrow \hspace{0.04em} \searrow \hspace{0.04em} \downarrow \\ au_2 \hspace{4em} dv_2 \\ \hspace{1em} \downarrow \hspace{0.04em} \searrow \hspace{0.04em} \swarrow \hspace{0.04em} \downarrow \\ \hspace{1em} \downarrow \hspace{0.04em} \swarrow \hspace{0.04em} \searrow \hspace{0.04em} \downarrow \\ bu_3 \hspace{4em} cv_3 \\ \hspace{1em} \downarrow \hspace{0.04em} \searrow \hspace{0.04em} \swarrow \hspace{0.04em} \downarrow \\ \hspace{1em} \downarrow \hspace{0.04em} \swarrow \hspace{0.04em} \searrow \hspace{0.04em} \downarrow \\ bu_4 \hspace{4em} dv_4 \\ \end{gather*} $$

   $$ \begin{gather*} \ \ \ \ \textcolor{rgb(232 124 124)}{a} u_1 au_2 \textcolor{rgb(232 124 124)}{b} u_3 b u_4 \qquad (1^{\text{st}} \text{ column}) \\ + \ \textcolor{rgb(232 124 124)}{a} u_1 au_2 \textcolor{rgb(232 124 124)}{b} u_3 d v_4 \qquad (3 \text{ first elements of the } 1^{\text{st}} \text{ column} - \ 4^{\text{th}} \text{ element of the } 2^{\text{nd}}) \\ + \ \textcolor{rgb(232 124 124)}{a} u_1 au_2 c v_3 \textcolor{rgb(232 124 124)}{b} u_4 \qquad (2 \text{ first elements of the } 1^{\text{st}} \text{ column} - \ 3^{\text{rd}} \text{ element of the } 2^{\text{nd}} - \ 4^{\text{th}} \text{ element of the } 1^{\text{st}} ) \\ + \ ... \\ + \ \textcolor{rgb(93 183 129)}{c} v_1 \textcolor{rgb(93 183 129)}{d} v_1 b u_3 dv_4 \qquad (2 \text{ first elements of the } 2^{\text{nd}} \text{ column} - \ 3^{\text{rd}} \text{ element of the } 1^{\text{st}} - \ 4^{\text{th}} \text{ element of the } 2^{\text{nd}} ) \\ + \ \textcolor{rgb(93 183 129)}{c} v_1 \textcolor{rgb(93 183 129)}{d} v_1 cv_3 b u_4 \qquad (3 \text{ first elements of the } 2^{\text{nd}} \text{ column} - \ 4^{\text{th}} \text{ element} \ of \ the \ 1^{\text{st}}) \\ + \ \textcolor{rgb(93 183 129)}{c} v_1 \textcolor{rgb(93 183 129)}{d} v_1 cv_3 dv_4 \qquad (2^{\text{nd}} \text{ column}) \\ \end{gather*} $$

   such as, after having gathered all these terms according to \(\textcolor{rgb(232 124 124)}{ab}\) or \(\textcolor{rgb(93 183 129)}{cd}\): \(\exists (U, V) \in \hspace{0.04em} \mathbb{Z}^2, \ abU + cdV = 1\).

   Indeed, to demonstrate more simply that all possible paths of multiplication sequences will contain at least once \(\textcolor{rgb(232 124 124)}{ab}\) or \(\textcolor{rgb(93 183 129)}{cd}\), we can use the Boolean logic rules:

   With the diagram above showing all possible paths, we see that \(\mathbb{E}\), the set of all possible paths is:

   $$ \mathbb{E} = (a \lor c) \land (a \lor d) \land (b \lor c) \land (b \lor d) $$

   Both expressions \(\lor\) and \(\land\) being associative, we can write that:

   $$ \mathbb{E} = \Bigl[ (a \lor c) \land (a \lor d) \Bigr] \land \Bigl[ (b \lor c) \land (b \lor d) \Bigr] $$

   We now factorize the two expressions in brackets:

   $$ \mathbb{E} = \Bigl[ a \lor (c \land d) \Bigr] \land \Bigl[ b \lor (c \land d) \Bigr] $$

   We factor it a second time:

   $$ \mathbb{E} = ( a \land b ) \land ( c \land d ) $$

   We will have at least once for each term \(\textcolor{rgb(232 124 124)}{ab}\) or \(\textcolor{rgb(93 183 129)}{cd}\).

3. Equivalence

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

   $$ \forall (a, b, c, d) \in \hspace{0.04em}\mathbb{Z}^4, $$
   $$ ab \wedge cd = 1 \hspace{0.2em} \Longleftrightarrow \hspace{0.2em} \left \{ \begin{gather*} a \wedge c = 1 \\ a \wedge d = 1 \\ b \wedge c = 1 \\ b \wedge d = 1 \\ \end{gather*} \right \} $$

Generalization for any product

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