Skip to content

Bézout's Theorem & Linear Diophantine Equations

Bézout's Lemma reveals the profound connection between the greatest common divisor and integer linear combinations, and is one of the most fundamental and important conclusions in number theory. Based on this, this article further discusses the method for solving linear Diophantine equations.

Bézout's Lemma

Bézout's Lemma, also known as Bézout's identity, provides a necessary and sufficient condition for an integer to be expressed as an integer linear combination of two integers.

Bézout's Lemma

Let \(a,b\) be integers not both zero. Then, for any integers \(x,y\), we have \(\gcd(a,b)\mid ax+by\); moreover, there exist integers \(x,y\) such that \(ax+by=\gcd(a,b)\).

Proof

Let \(d=\gcd(a,b)\). Since \(d\mid a,b\), there exist integers \(u,v\) such that \(a=du,~b=dv\). Therefore, we always have

\[ ax + by = d(ux+vy). \]

This shows \(d\mid ax+by\).

Conversely, we need to show the existence of \(x,y\) such that the equality holds. If one of \(a,b\) is \(0\), without loss of generality let \(b=0\), then their greatest common divisor is \(d=a\), and clearly \((x,y)=(1,0)\) satisfies the equality. Next, consider the case where both \(a\) and \(b\) are nonzero. Since \(\gcd(a,b)=\gcd(-a,b)=\gcd(a,-b)\), we may assume \(a,b\) are both positive.

Consider the process of the Euclidean algorithm:

\[ \begin{aligned} a &= q_1b + r_1, && 0\le r_1 < b,\\ b &= q_2r_1 + r_2, && 0\le r_2 < r_1,\\ r_1 &= q_3r_2 + r_3, && 0\le r_3 < r_2,\\ & \cdots \\ r_{n-3} &= q_{n-1}r_{n-2} + r_{n-1}, && 0\le r_{n-1} < r_{n-2},\\ r_{n-2} &= q_nr_{n-1} + r_n, && 0\le r_n < r_{n-1},\\ r_{n-1} &= q_{n+1}r_n. \end{aligned} \]

Since the greatest common divisor is \(d\), at the last step of the Euclidean algorithm, we must have \(r_n=d\). Therefore, the second-to-last equation can be written as

\[ d = r_n = r_{n-2} - q_nr_{n-1}. \]

Solving for \(r_{n-1}\) from the third-to-last equation:

\[ r_{n-1} = r_{n-3} - q_{n-1}r_{n-2} \]

and substituting into the above equation, we can eliminate \(r_{n-1}\):

\[ \begin{aligned} d &= r_{n-2} - q_n(r_{n-3} - q_{n-1}r_{n-2}) \\ &= (1 + q_nq_{n-1})r_{n-2} - q_nr_{n-3}. \end{aligned} \]

Similarly, we can gradually eliminate all \(r_{n-2},r_{n-3},\cdots,r_2,r_1\), eventually obtaining

\[ d = xa + yb. \]

This proves the existence of \(x,y\) such that \(ax+by=d\) holds. From the previous analysis, this also proves the original proposition.

Here, the proof of existence is constructive, and it simultaneously gives a method for computing these coefficients. This computation method is the Extended Euclidean Algorithm.

Considering the special case of Bézout's Lemma when \(\gcd(a,b)=1\), we obtain the following corollary:

Corollary

Integers \(a,b\) are coprime if and only if there exist integers \(x,y\) such that \(ax+by=1\).

Case of Multiple Integers

Bézout's Lemma can be generalized to the case of multiple integers.

Theorem

Let \(a_1,a_2,\cdots,a_n\) be integers not all zero. Then, for any integers \(x_1,x_2,\cdots,x_n\), we have \(\gcd(a_1,a_2,\cdots,a_n)\mid a_1x_1+a_2x_2+\cdots+a_nx_n\); moreover, there exist integers \(x_1,x_2,\cdots,x_n\) such that \(\gcd(a_1,a_2,\cdots,a_n)=a_1x_1+a_2x_2+\cdots+a_nx_n\).

Proof

Using the fact that \(\gcd(a_1,a_2,\cdots,a_n)=\gcd(\gcd(a_1,a_2,\cdots,a_{n-1}),a_n)\), perform induction on \(n\).

Example Problem

Codeforces 510 D. Fox And Jumping

Given \(n\le 300\) cards, each with \(l_i\) and \(c_i\). On an infinitely long paper tape, you can choose to spend \(c_i\) to purchase card \(i\), after which you can jump left or right by \(l_i\) units any number of times. Ask the minimum amount of money you need to spend to be able to jump to every position on the tape. If impossible, output \(-1\).

Solution

Analyzing the problem, we find that to jump to every grid, the selected numbers \(l_{i_1}, \cdots, l_{i_k}\) must yield an absolute value of \(1\) through several additions or subtractions. That is, there exist integers \(x_1, \cdots, x_k\) such that \(l_{i_1} x_1 + \cdots + l_{i_k} x_k = 1\). By the generalization of Bézout's Lemma to multiple integers, this is equivalent to selecting several numbers from the array \(l_1, \cdots, l_n\) such that their greatest common divisor is \(1\), while minimizing the total cost.

Solution 1: Treat the minimum cost as a shortest path problem, which can be solved using Dijkstra's algorithm. The vertices of the graph store the current value of the greatest common divisor. The starting point of the graph is \(0\), and the target point to reach is \(1\). At each step, from the current vertex \(x\), follow an edge of length \(c_i\) to the vertex \(\gcd(x,l_i)\). The time complexity of this algorithm is \(O(n^2\log n)\).

Solution 2: Selecting several numbers from the array \(l_1, \cdots, l_n\) such that their greatest common divisor is \(1\) and the total cost is minimized reminds us of the 0-1 knapsack problem.

Let \(f_{i, j}\) denote the minimum cost considering the first \(i\) numbers with greatest common divisor \(j\). Then the transition equation is:

\[ f_{i, j} = \min_{\gcd(k, l_i) = j} f_{i - 1, k} + c_i. \]

After DP, the final total cost is \(f_{n, 1}\).

As with the general 0-1 knapsack problem, we can optimize using a rolling array to remove the first dimension. Here, the possible greatest common divisors \(j\) formed by 300 numbers are sparse, so a hash table can be used for storage.

In fact, the graph constructed in Solution 1 is exactly the state transition graph of the dynamic programming in Solution 2. Solution 2 is equivalent to finding the shortest path in a directed acyclic graph using dynamic programming. Therefore, Solution 1 and Solution 2 are equivalent. However, Solution 2 does not need to store the entire graph, and the DP time complexity is \(O(n + m)\), which is lower than Dijkstra's algorithm. Thus, Solution 2 is more efficient in both time and space.

Linear Diophantine Equations

A linear Diophantine equation is an indeterminate equation of the form

\[ a_1x_1 + a_2x_2 + \cdots + a_nx_n = b \]

where \(a_1,a_2,\cdots,a_n\) are integers. The goal of this section is to find all its integer solutions.

Case of Two Variables

First consider the binary linear Diophantine equation:

\[ a_1x_1 + a_2x_2 = b. \]

Bézout's Lemma states that this equation has a solution if and only if

\[ d = \gcd(a_1,a_2) \mid b. \]

Next, assume this condition holds. Using the extended Euclidean algorithm, we can find a particular integer solution \((x_1^*,x_2^*)\) to the equation \(a_1x_1 + a_2x_2 = d\). From this, we obtain a particular solution to the original equation:

\[ (x_1^\circ,x_2^\circ) = \left(\frac{b}{d}x_1^*,\frac{b}{d}x_2^*\right). \]

To obtain all solutions, consider subtracting the original equation from the identity \(a_1x_1^\circ+a_2x_2^\circ = b\), yielding

\[ a_1(x_1 - x_1^\circ) + a_2(x_2 - x_2^\circ) = 0. \]

This is a homogeneous linear Diophantine equation in \((x_1-x_1^\circ,x_2-x_2^\circ)\), with general solution

\[ (x_1-x_1^\circ,x_2-x_2^\circ) = \left(t\dfrac{a_2}{d},-t\dfrac{a_1}{d}\right).\quad(t\in\mathbf Z) \]

Therefore, the general solution of the original equation is

\[ (x_1,x_2) = \left(x_1^\circ + t\dfrac{a_2}{d},x_2^\circ - t\dfrac{a_1}{d}\right).\quad(t\in\mathbf Z) \]

This represents a series of equally spaced integer points on the line \(a_1x_1+a_2x_2 = b\).

Case of Multiple Variables

Having solved the binary case, the multivariate case becomes easier. For the \(n\)-variable linear Diophantine equation

\[ a_1x_1 + a_2x_2 + \cdots + a_nx_n = b,\quad (n>3) \]

Bézout's Lemma implies that the equation has a solution if and only if

\[ \gcd(a_1,a_2,\cdots,a_n) \mid b. \]

Similar to the binary case, the general solution of a multivariate linear Diophantine equation can also be written as

\[ (x_1^\circ,x_2^\circ,\cdots,x_n^\circ) + \sum_{k=1}^{n-1} t_k(x_1^{(k)},x_2^{(k)},\cdots,x_n^{(k)}) \]

where \(x^\circ\) is a particular solution, and \(x^{(k)}\) are \((n-1)\) solutions to the corresponding homogeneous equation.

To obtain the specific form of the general solution, we can reduce the \(n\)-variable equation to an \((n-1)\)-variable equation. Without loss of generality, let \(d_1 = \gcd(a_1,a_2)\). Then, by Bézout's Lemma, the set of all values of \(a_1x_1+a_2x_2\) is exactly all multiples of \(d_1\). Therefore, we can first solve the \((n-1)\)-variable linear Diophantine equation:

\[ d_1y_1 + a_3x_3 + a_4x_4 + \cdots + a_nx_n = b. \]

Suppose its general solution is

\[ \begin{aligned} y_1 &= y_1^\circ + \sum_{k=2}^{n-1}t_ky_1^{(k)}, \\ x_i &= x_i^\circ + \sum_{k=2}^{n-1}t_kx_i^{(k)},\quad i=3,\cdots,n. \end{aligned} \]

Let \((x_1^*,x_2^*)\) be a particular solution to \(a_1x_1+a_2x_2=d_1\). Then, according to the discussion in the previous section, the general solution to the binary linear Diophantine equation \(a_1x_1+a_2x_2=d_1y_1\) for \(x_1,x_2\) is

\[ x_1 = x_1^*y_1 + t_1\dfrac{a_2}{d_1},~x_2 = x_2^*y_1 - t_1\dfrac{a_1}{d_1}. \]

Substituting the expression for \(y_1\), we obtain the general solution of the original equation:

\[ \begin{aligned} x_1 &= x_1^*y_1^\circ + t_1\dfrac{a_2}{d_1} + \sum_{k=2}^{n-1}t_kx_1^*y_1^{(k)}, \\ x_2 &= x_2^*y_1^\circ - t_1\dfrac{a_1}{d_1} + \sum_{k=2}^{n-1}t_kx_2^*y_1^{(k)}, \\ x_i &= x_i^\circ + \sum_{k=2}^{n-1}t_kx_i^{(k)},\quad i=3,\cdots,n. \end{aligned} \]

Frobenius Coin Problem

Bézout's Lemma gives a necessary and sufficient condition for an integer to be linearly expressed by several integers. Closely related is the Frobenius coin problem:

  • If coins have integer denominations \(a_1,a_2,\cdots,a_n\), and \(\gcd(a_1,a_2,\cdots,a_n)=1\), what is the largest integer that cannot be formed by these coins?

This also examines when an integer \(k\) can be expressed in the form \(a_1x_1+a_2x_2+\cdots+a_nx_n\). In Bézout's Lemma, \(x_i\) can be any integer, while in the Frobenius coin problem, \(x_i\) must be natural numbers.

The case with only one coin is trivial because we must have \(a_1=1\), and all natural numbers can be formed. The case \(n>2\) is too complex, so this section only discusses the case \(n=2\).

Sylvester's Theorem

In 1882, Sylvester completely solved the Frobenius coin problem for \(n = 2\):

Theorem (Sylvester)

For coprime positive integers \(a_1,a_2\), the largest integer that cannot be written as \(a_1x_1+a_2x_2~(x_1,x_2\in\mathbf N)\) is \(C = a_1a_2 - a_1 - a_2\). Moreover, for all \(k\in\mathbf Z\), exactly one of the integers \(k\) and \(C-k\) can be written in this form.

For convenience, integers that can be written as \(a_1x_1+a_2x_2~(x_1,x_2\in\mathbf N)\) are called representable.

Proof 1

Since \(a_1,a_2\) are coprime, for any integer \(k\), the equation \(a_1x_1+a_2x_2=k\) must have a solution, with general solution

\[ (x_1,x_2) = (x_1^\circ + ta_2, x_2^\circ - ta_1).\quad(t\in\mathbf Z) \]

Take \(t\) as the quotient when \(x_2^\circ\) is divided by \(a_1\) with remainder. Then the remainder \(x_2 = x_2^\circ-ta_1\) lies between \(0\) and \(a_1-1\). Consider the resulting solution \((x_1,x_2)\) at this point. Since \(x_2\) is the smallest non-negative integer value it can take, \(n\) is representable if and only if \(x_1\ge 0\).

Step 1: Prove that integers greater than \(C\) are representable.

When \(k > C\), we have

\[ a_1x_1 = k - a_2x_2 > C - a_2(a_1-1) = -a_1. \]

So, \(x_1 > -1\), meaning \(x_1\ge 0\). This shows that \((x_1,x_2)\) is a pair of natural numbers. Thus, \(k\) can be written in the required form.

Step 2: Prove that \(C\) is not representable. Consequently, \(C\) is the largest non-representable integer, and \(k\) and \(C-k\) cannot both be representable.

By contradiction. Assume \(C\) is representable, i.e., there exist \(x_1,x_2\in\mathbf N\) such that \(a_1x_1+a_2x_2=C\). Substituting the expression for \(C\), we have

\[ a_1a_2 = a_1(x_1+1) + a_2(x_2+1). \]

Therefore, \(a_2\mid (x_1+1)\) and \(a_1\mid (x_2+1)\). Since \(x_1+1,x_2+1\) are positive, we have

\[ a_1a_2 \ge a_1a_2 + a_2a_1 = 2a_1a_2. \]

Contradiction. This shows \(C\) is not representable. Combined with Step 1, it is the largest non-representable integer.

If both \(k\) and \(C-k\) were representable, then adding the coefficients from the representations of \(k\) and \(C-k\) would yield coefficients for a representation of \(C\), contradicting the non-representability of \(C\). Hence, at most one of \(k\) and \(C-k\) can be representable.

Step 3: Prove that if \(k\) is not representable, then \(C-k\) must be representable.

Let \((x_1,x_2)\) be the integer solution to the equation \(a_1x_1+a_2x_2=k\) as set earlier. Then, as previously stated, \(k\) not being representable is equivalent to \(x_1<0\). Therefore,

\[ C - k = a_1a_2 - a_1 - a_2 - a_1x_1 - a_2x_2 = a_1(-1-x_1) + a_2(a_1-1-x_2). \]

Here, \(-1-x_1\) and \(a_1-1-x_2\) are both non-negative integers, so \(C-k\) is representable.

Proof 2

Here we only prove that \(C=a_1a_2-a_1-a_2\) is the largest non-representable natural number; the proof of the remaining parts is similar to Proof 1.

Consider the smallest representable natural number in each residue class modulo \(a_2\). Since different natural numbers in the same residue class can be transformed by adding or subtracting multiples of \(a_2\), when discussing the smallest representable number, we only need to consider the possibility of adding or subtracting \(a_1\). Since \(a_1\) and \(a_2\) are coprime, the smallest representable natural number in each residue class is exactly the multiples of \(a_1\):

\[ 0,~a_1,~2a_1,~\cdots,~(a_2-1)a_1. \]

Therefore, the largest non-representable number is

\[ \max_{0\le i < a_2} ia_1 - a_2 = (a_2-1)a_1 - a_2 = C. \]

Geometric Interpretation

Consider the equation \(a_1x_1 + a_2x_2 = k\) as a line. Then, \(k\) is representable if and only if this line passes through an integer point in the first quadrant (including the axes). When \(k < ab\), this line can pass through at most one integer point in the first quadrant. Therefore, for \(0\le k < ab\), the integer \(k\) is representable if and only if the line passes through exactly one integer point in the first quadrant.

Thus, the number of natural numbers less than or equal to \(k < ab\) that are representable is exactly the number of integer points (including boundary points) below the line \(a_1x_1 + a_2x_2 = k\) in the first quadrant. This number equals

\[ \sum_{i=0}^{\lfloor k / a_1 \rfloor} \left\lfloor\dfrac{k-ia_1}{a_2}\right\rfloor. \]

This is the classic integer points under a line problem, which can be solved in \(O(\log\min\{a_1,a_2,k\})\) time using the Euclidean-like algorithm.

Exercises

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用