Let $a_{1}, \ldots, a_{n} \in \mathbb{Z}$. Construct a number $a>1$ such that for all $i \in\{1, \ldots, n\}, a_{i} \wedge a=1$.

(Note: Here, $a_{i} \wedge a$ denotes the greatest common divisor (gcd) of $a_i$ and $a$.)
Let's start with the case where $n=1$. We are then simply looking for a number $a$ that is coprime with $a_{1}$. According to Bézout's Theorem 24, it suffices to write a Bézout relation to find such a number. Let's look for a Bézout relation with the simplest coefficients possible, for example $u=1$ and $v=-1$, which gives $a-a_{1}=1$, or $a=a_{1}+1$.

Now let's move on to the general case. If the number $a$ is coprime with $a_{i}$ for all $i$, it is coprime with their product $b=a_{1} \ldots a_{n}$. This is even a sufficient condition according to Proposition 22. We are thus reduced to the case $n=1$ and we know that we can take $a=b+1=a_{1} \ldots a_{n}+1$ which works.

Remark 27 (Extended Euclidean Algorithm in Practice).

1. The Extended Euclidean Algorithm 2 actually consists of keeping four additional numbers $\left(u_{n}, v_{n}, u_{n-1}, v_{n-1}\right)$ at each step of the Euclidean Algorithm. It is quite easy to apply by hand from two given numbers $a$ and $b$, and allows finding the GCD and the pair $(u, v)$ at the same time.
2. If we find the GCD $d$ by another means, we can apply the algorithm to $k=a / d$ and $l=b / d$ which are coprime and smaller, thus easier to handle. According to Proof 2 of the theorem, a Bézout pair $(u, v)$ for $k$ and $l$ also satisfies $d=a u+b v$.