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

    \begin{equation} \gcd (a, bc) | \gcd (a, b) \times \gcd (a, c) \end{equation}

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 \)