Bezout's Lemma & Linear Diophantine Equations

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

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

This shows that $d\mid ax+by$．

Conversely, we need to show that there exist $x,y$ for which the equality holds. If one of $a,b$ is $0$, assume without loss of generality that $b=0$. Their greatest common divisor is then $d=a$, and clearly $(x,y)=(1,0)$ makes the equality hold. Now consider the case in which $a,b$ are both nonzero. Since $\gcd(a,b)=\gcd(-a,b)=\gcd(a,-b)$, assume without loss of generality that both $a,b$ are positive．

Consider the process of the Euclidean algorithm:

Since the greatest common divisor is $d$, the final remainder must satisfy $r_n=d$. Thus, the penultimate equation can be written as

Solving the antepenultimate equation for the preceding remainder gives

Substituting this into the equation above eliminates $r_{n-1}$:

Continuing in the same way, we can eliminate all of $r_{n-2},r_{n-3},\cdots,r_2,r_1$ and eventually obtain

This proves that there exist $x,y$ such that $ax+by=d$. The preceding analysis therefore proves the original proposition．

Integers $a,b$ are coprime if and only if there exist integers $x,y$ such that $ax+by=1$．

Let $a_1,a_2,\cdots,a_n$ be integers that are not all zero. Then, for any integers $x_1,x_2,\cdots,x_n$, $\gcd(a_1,a_2,\cdots,a_n)\mid a_1x_1+a_2x_2+\cdots+a_nx_n$ holds; 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$．

Apply induction on $n$ using $\gcd(a_1,a_2,\cdots,a_n)=\gcd(\gcd(a_1,a_2,\cdots,a_{n-1}),a_n)$．

Analyzing the problem, to reach every cell, the absolute value obtained by adding or subtracting the selected numbers $l_{i_1}, \cdots, l_{i_k}$ some number of times must be $1$. In other words, there must exist integers $x_1, \cdots, x_k$ such that $l_{i_1} x_1 + \cdots + l_{i_k} x_k = 1$. By Bezout's lemma for multiple integers, this is equivalent to selecting some numbers from the array $l_1, \cdots, l_n$ whose greatest common divisor is $1$, while minimizing the sum of their costs．

Solution 1: Regard the minimum cost sum as a shortest-path problem and solve it with Dijkstra's algorithm. Store the current greatest common divisor at each graph vertex. The starting vertex is $0$, and the target vertex is $1$. At each step, start from the current vertex $x$ and follow an edge of length $c_i$ to the vertex $\gcd(x,l_i)$. This algorithm has time complexity $O(n^2\log n)$．

Solution 2: Selecting some numbers from $l_1, \cdots, l_n$ so that their greatest common divisor is $1$ and their cost sum is minimized suggests a 0-1 knapsack problem．

Let $f_{i, j}$ denote the minimum cost when considering the first $i$ numbers and having greatest common divisor $j$. The transition is

After the DP, the final total cost is $f_{n, 1}$．

As with the ordinary 0-1 knapsack problem, a rolling array can remove the first dimension. Here, the greatest common divisors $j$ that can be formed by 300 numbers are sparse, so a hash table can be used to store them．

In fact, the graph constructed in Solution 1 is precisely the state-transition graph of the dynamic programming in Solution 2. Solution 2 is equivalent to finding shortest paths in a directed acyclic graph with dynamic programming. Thus, the two solutions are equivalent. However, Solution 2 does not need to store the entire graph, and its DP time complexity is $O(n + m)$, lower than that of Dijkstra's algorithm, so Solution 2 is better in both time and space．

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 every $k\in\mathbf Z$, exactly one of the integers $k$ and $C-k$ can be written in this form．

Since $a_1,a_2$ are coprime, for every integer $k$, the equation $a_1x_1+a_2x_2=k$ has a solution, whose general form is

Let $t$ be the quotient obtained when dividing $x_2^\circ$ by $a_1$ with remainder. Then the remainder $x_2 = x_2^\circ-ta_1$ lies between $0$ and $a_1-1$. Consider the solution $(x_1,x_2)$ obtained this way. Since $x_2$ is the smallest nonnegative value it can take, $n$ is representable if and only if $x_1\ge 0$．

Step 1: Prove that every integer greater than $C$ is representable．

When $k > C$,

Thus, $x_1 > -1$, that is, $x_1\ge 0$. Therefore, $(x_1,x_2)$ is a solution in natural numbers, and $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．

We use contradiction. Suppose that $C$ is representable, so there exist $x_1,x_2\in\mathbf N$ such that $a_1x_1+a_2x_2=C$. Substituting the expression for $C$ gives

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

This is a contradiction, so $C$ is not representable. Together with Step 1, it is the largest non-representable integer．

If both $k$ and $C-k$ were representable, adding the coefficients in the representations of $k$ and $C-k$ would produce a representation of $C$, contradicting the fact that $C$ is not representable. Hence at most one of $k$ and $C-k$ can be representable．

Step 3: Prove that if $k$ is not representable, then $C-k$ is representable．

Let $(x_1,x_2)$ be the integer solution of $a_1x_1+a_2x_2=k$ introduced above. The preceding discussion shows that $k$ is not representable if and only if $x_1<0$. Therefore,

Both $-1-x_1$ and $a_1-1-x_2$ are nonnegative integers, so $C-k$ is representable．

Here we prove only that $C=a_1a_2-a_1-a_2$ is the largest non-representable natural number; the rest is proved similarly to Proof 1．

Consider, modulo $a_2$, the smallest representable natural number in each residue class. Since different natural numbers in the same residue class can be transformed into one another by adding or subtracting some multiple of $a_2$, when considering the smallest representable number it is enough to consider adding or subtracting $a_1$. Since $a_1$ and $a_2$ are coprime, the smallest representable natural numbers in the residue classes are exactly the multiples of $a_1$:

Therefore, the largest non-representable number is