Interesting or creative applications of Bezout’s (Bachet’s) Identity

Question

Bezout’s Identity (but discovered earlier, in a restricted form, by Bachet) is the following result.

Theorem: Let $a$ and $b$ be nonzero integers and let $d$ be their greatest common divisor. Then there exist integers $x$ and $y$ such that $$ax+by=d.$$ In addition, the greatest common divisor $d$ is the smallest positive integer that can be written as $ax + by$, and every integer of the form $ax + by$ is a multiple of the greatest common divisor $d$.

Many theorems in elementary number theory are a result of this one (e.g., Euclid's lemma, the Chinese remainder theorem).

I’m looking for interesting or creative applications of Bezout’s Identity to prove number theory results. One example is Catalan’s “complete integer solution” of the 2.2.3 equation $$X_1^2+X_2^2=Y_1^2+Y_2^2+Y_3^2, \tag{1}$$ which he gave as follows.

Choose relatively prime integers $\alpha$ and $\beta$, and integers $u$ and $v$ such that $\beta u - \alpha v = 1$. Then all integer solutions of (1) are given, without repetition, by the formulas \begin{align*} x_1 &= \tfrac{1}{2}(\alpha^2 + \beta^2 + y_3^2)u + \beta \theta, & y_1 &= x_1 + \alpha, \\ x_2 &= \tfrac{1}{2}(\alpha^2 + \beta^2 + y_3^2)v + \alpha \theta, & y_2 &= x_2 - \beta, \end{align*} where $\theta$ is an arbitrary integer.

[cf. Dickson’s History, Vol II, p. 268; orig: Assoc franç., av. sc. 12, 1883, 98–101]

What other clever applications are there?

Answer 1

Here’s one: Dickson proved that all primitive integral solutions of the equation $$x^2-my^2=zw$$ are given by \begin{align} z &= el^2 + 2flq + gq^2, \\ w &= en^2 - 2fnr + gr^2, \\ x &= \pm (eln+fnq-flr-gqr), \\ y &= lr + nq, \end{align} where $f^2-eg=m$. Dickson says “Since $y=l$ and $w=g$ are relatively prime, there exist integers $f$ and $q$ such that $x=fl+gq$”, and then goes on to prove the theorem.

[@BillDubuque: If you stumble back on this post, I’d love for you to discuss it with respect to your comments under the main post. Thanks!]

Answer 2

Lemma: If $p$ is a prime number and $k$ is a positive integer not equal to $p$, then $\displaystyle p \mid \dbinom{p}{k}$.

Proof: For $k>p$, $\dbinom{p}{k} = 0$. Hence $p \mid \dbinom{p}{k}$.

For $0<k<p$, we have,

\begin{align*} 1&=ap+bk \ ; \ a, b \in \mathbb{Z} \\ \implies\dbinom{p}{k} &= (ap+bk)\dbinom{p}{k} \\ &= ap\dbinom{p}{k} + bk\dbinom{p}{k} \\ &= ap\dbinom{p}{k} + bp\dbinom{p-1}{k-1} \ \left(\because \dbinom{n}{r} = \dfrac{n}{r} \dbinom{n-1}{r-1}\right) \\ &= p\left(a\dbinom{p}{k} + b\dbinom{p-1}{k-1}\right) \\ \implies p&\mid \dbinom{p}{k} \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \square \end{align*}

This can be extended for composite $n$ with $\gcd (n,k) = d$ to show that $n \mid d \dbinom{n}{k}$.