# A calculus of the absurd

##### 19.1.3 Bezout’s lemma
• Theorem 19.1.2 Let $$a, b \in \mathbb {Z}$$, then there exists some integers $$x$$ and $$y$$ such that $$\gcd (a, b) = xa + yb$$.

TODO: proof

• Example 19.1.1 Prove that for all $$a, b, c \in \mathbb {N} - \{0\}$$ it is true that

$$\gcd (a, bc) | \gcd (a, b) \times \gcd (a, c)$$

We know using Bezout’s lemma that there exist some $$w, z, y, z \in \mathbb {Z}$$ such that $$\gcd (a, b) = wa + xb$$ and $$\gcd (a, c) = ya + zc$$, and therefore

\begin{align} \gcd (a, b) \times \gcd (a, c) &= (wa + xb)(ya + zc) \\ &= waya + wazc + xbya + xbzc \\ &= (way + wzc + xby)a + (xz)bc \end{align}

and therefore as $$\gcd (a, bc)$$ divides both $$a$$ and $$bc$$ it divides the expression we are after.

$$\Box$$