Problem 319: Bounded Sequences

Detailed mathematical approach

Problem Summary

We count the sequences of integers \(x_1,x_2,\dots,x_n\) that satisfy three conditions: the first term is \(x_1=2\); the sequence is strictly increasing, so \(x_{i-1}\lt x_i\) for every \(1\lt i\le n\); and for every pair of indices \(1\le i,j\le n\),

$$(x_i)^j\lt(x_j+1)^i.$$

Let \(t(n)\) be the number of such sequences. The statement lists the five sequences of length two, \(\{2,4\}\), \(\{2,5\}\), \(\{2,6\}\), \(\{2,7\}\) and \(\{2,8\}\); it gives \(t(5)=293\) with the examples \(\{2,5,11,25,55\}\), \(\{2,6,14,36,88\}\) and \(\{2,8,22,64,181\}\); and it gives \(t(10)=86195\) and \(t(20)=5227991891\). We must find \(t(10^{10})\) modulo \(10^9\). ^[1]

The whole solution in one sentence: every admissible sequence is the list of integer parts of the powers of one real number between \(2\) and \(3\), so \(t(n)\) counts the pieces into which the exact \(k\)-th roots of integers with \(k\le n\) cut that interval, and counting each boundary only once collapses the count into a sum over about \(2\sqrt n\) blocks.

Mathematical Approach

1. Two free consequences of the condition

The third condition covers all \(n^2\) ordered pairs \((i,j)\), but the pairs with an index equal to \(1\) already bound every term. Taking \(i=1\) gives \(2^j\lt x_j+1\), that is \(x_j\ge 2^j\). Taking \(j=1\) gives \(x_i\lt 3^i\). So every admissible sequence satisfies

$$2^i\le x_i\le 3^i-1\qquad(1\le i\le n).$$

For \(n=2\) this leaves the five candidates \(4\le x_2\le8\), and all five are admissible: the five sequences of the statement.

2. One real number behind the whole sequence

Every quantity in \((x_i)^j\lt(x_j+1)^i\) is positive, so taking \(ij\)-th roots preserves the inequality:

$$x_i^{1/i}\lt (x_j+1)^{1/j}.$$

The left side depends only on \(i\), the right only on \(j\), so the third condition says one thing: the largest \(x_i^{1/i}\) is smaller than the smallest \((x_j+1)^{1/j}\). Put

$$y=\max_{1\le i\le n}x_i^{1/i}.$$

Then \(x_i^{1/i}\le y\lt(x_i+1)^{1/i}\) for every \(i\), and raising to the \(i\)-th power gives \(x_i\le y^i\lt x_i+1\), the definition of the integer part:

$$x_i=\lfloor y^i\rfloor\qquad(1\le i\le n).$$

The case \(i=1\) reads \(x_1\le y\lt x_1+1\), so \(x_1=2\) is the same as \(2\le y\lt 3\).

3. The converse, and free growth

Conversely, take any \(y\in[2,3)\) and set \(x_i=\lfloor y^i\rfloor\). Then \(x_i\le y^i\lt x_i+1\), hence \(x_i^{1/i}\le y\lt(x_j+1)^{1/j}\) for all \(i,j\), which is the third condition, and \(\lfloor y\rfloor=2\) is the first.

The second condition comes for free. For \(i\ge2\) we have \(y^{i-1}\ge y\ge2\), so

$$\begin{aligned}y^i&=y\cdot y^{i-1}\ge 2y^{i-1}\\&=y^{i-1}+y^{i-1}\ge y^{i-1}+2,\end{aligned}$$

and taking integer parts gives \(x_i\ge x_{i-1}+2\): the strict growth demanded by the statement is already implied by the other two conditions, and a search from the definition confirms that dropping it changes no count for \(n\le8\). So we have a bijection: the admissible sequences of length \(n\) are exactly the distinct lists \(\bigl(\lfloor y\rfloor,\dots,\lfloor y^n\rfloor\bigr)\) with \(y\in[2,3)\).

4. Counting the pieces of an interval

Let \(F(y)=\bigl(\lfloor y\rfloor,\dots,\lfloor y^n\rfloor\bigr)\) on \([2,3)\). Each coordinate is a non-decreasing step function, so \(F\) is constant on each piece of a partition of \([2,3)\) into finitely many half-open intervals, and takes a different value on each, because a coordinate that has increased never comes back down. With \(C_n\) the set of points of \((2,3)\) at which some coordinate jumps, there is one piece more than there are jumps:

$$t(n)=1+|C_n|.$$

Now \(\lfloor y^k\rfloor\) jumps exactly where \(y^k\) reaches an integer, so \(C_n\) consists of the \(y\in(2,3)\) with \(y^k\) integral for at least one \(k\le n\). We call these the cut points; counting sequences has become counting them.

5. Where the cuts are

Fix \(k\). The \(y\in(2,3)\) with \(y^k=m\) integral are the roots \(m^{1/k}\) with \(2^k\lt m\lt 3^k\), one per such \(m\), so their number is the count of integers strictly between \(2^k\) and \(3^k\):

$$f(k)=3^k-2^k-1.$$

The first values are \(f(1)=0\), \(f(2)=4\), \(f(3)=18\), \(f(4)=64\), \(f(5)=210\), \(f(6)=664\), \(f(7)=2058\) and \(f(8)=6304\). ^[8] That \(f(1)=0\) records that no integer lies strictly between \(2\) and \(3\).

For \(n=2\) the only cut points are the four square roots \(\sqrt5\approx2.236068\), \(\sqrt6\approx2.449490\), \(\sqrt7\approx2.645751\) and \(\sqrt8\approx2.828427\). They cut \([2,3)\) into five pieces, and picking one \(y\) from each piece gives \(2\mapsto\{2,4\}\), \(2.3\mapsto\{2,5\}\), \(2.5\mapsto\{2,6\}\), \(2.7\mapsto\{2,7\}\) and \(2.9\mapsto\{2,8\}\), which is exactly the list in the statement, so \(t(2)=5\). The same count with \(n=3\) finds \(22\) cut points and so \(t(3)=23\); the pieces begin \(\{2,4,8\}\), \(\{2,4,9\}\), \(\{2,4,10\}\) and end with \(\{2,8,26\}\).

The three length-five examples arise the same way, their exact ranges being the largest lower bound and the smallest upper bound among the five inequalities \(x_i\le y^i\lt x_i+1\): \(\{2,5,11,25,55\}\) occurs for \(y\in[\sqrt5,56^{1/5})\), \(\{2,6,14,36,88\}\) for \(y\in[\sqrt6,89^{1/5})\) and \(\{2,8,22,64,181\}\) for \(y\in[\sqrt8,182^{1/5})\). Rounded decimals must not be used for such endpoints: \(2.82842712\) is below \(\sqrt8\) and already gives \(\{2,7,22,63,181\}\).

6. One cut point, several exponents

Adding up \(f(1)+\dots+f(n)\) overcounts, because one cut point can be reached through several exponents: \(\sqrt5\) is \(5^{1/2}\), but also \(25^{1/4}\) and \(125^{1/6}\), so it is counted again at every even exponent. We must know exactly when this happens.

For a fixed \(y\gt0\) let \(D=\{k\ge1:y^k\in\mathbb Z\}\) and suppose \(D\) is not empty; write \(d\) for its smallest element, the degree of the cut point. We claim \(D\) is precisely the set of multiples of \(d\). One direction is clear: if \(d\mid k\) then \(y^k=(y^d)^{k/d}\) is an integer. For the other, take \(k\in D\) and let \(g=\gcd(d,k)\). By Bézout's identity a greatest common divisor is an integer combination, so there are integers \(u,v\), possibly negative, with \(ud+vk=g\). ^[10] Then

$$y^g=(y^d)^u(y^k)^v$$

is a ratio of integers, hence rational, and \((y^g)^{d/g}=y^d\) is an integer. A rational number with an integral power is itself an integer, being a root of the monic polynomial \(T^{d/g}-y^d\), where the rational root theorem forces the denominator to divide the leading coefficient \(1\). ^[6] So \(g\in D\), which gives \(g\ge d\); since \(g\) divides \(d\) we get \(g=d\) and therefore \(d\mid k\).

One warning: a degree of \(d\) does not make the base power-free. The point \(16^{1/3}\) lies in \((2,3)\) and has degree \(3\), although \(16=2^4\). Writing \(y^d=p_1^{a_1}\cdots p_s^{a_s}\), the right criterion is \(\gcd(d,a_1,\dots,a_s)=1\): the power \(y^k\) is integral exactly when \(d\mid ka_i\) for every \(i\), that is when \(d\) divides \(k\gcd(a_1,\dots,a_s)\). ^[7]

7. Möbius inversion and the primitive counts

Let \(g(d)\) be the number of cut points of degree exactly \(d\). By Section 6, \(f(k)\) counts a cut point precisely when its degree divides \(k\), so

$$f(k)=\sum_{d\mid k}g(d)\qquad(k\ge1).$$

This is the standard shape for Möbius inversion, which gives ^[3]

$$g(k)=\sum_{d\mid k}\mu(d)\,f\!\left(\frac kd\right),$$

where \(\mu\) is the Möbius function, equal to \(1\) at \(1\), to \((-1)^r\) at a product of \(r\) distinct primes, and to \(0\) at any number divisible by the square of a prime. ^[2] What makes the inversion work is that \(\sum_{d\mid k}\mu(d)\) is \(1\) for \(k=1\) and \(0\) otherwise: for \(k\gt1\) with \(r\) distinct prime factors only the square-free divisors contribute, each such divisor is a choice of some of those \(r\) primes, and the signed count of the choices is the expansion of \((1-1)^r=0\).

The first primitive counts are \(g(1)=0\), \(g(2)=4\), \(g(3)=18\), \(g(4)=60\), \(g(5)=210\), \(g(6)=642\), \(g(7)=2058\) and \(g(8)=6240\). The gap \(f(4)-g(4)=4\) is visible by hand: among the \(64\) integers strictly between \(16\) and \(81\), exactly \(25\), \(36\), \(49\) and \(64\) are squares, and their fourth roots are the degree-two points \(\sqrt5,\dots,\sqrt8\) counted a second time.

Because each cut point is counted once, under its own degree,

$$t(n)=1+\sum_{k=1}^{n}g(k).$$

For \(n=5\) this gives \(1+(0+4+18+60+210)=293\), as stated.

8. The Mertens form of the sum

Substituting the inversion formula and writing \(k=dj\) turns this into a sum over pairs:

$$\sum_{k\le n}g(k)=\sum_{dj\le n}\mu(d)\,f(j).$$

Collecting the pairs by their second entry rewrites the right side as

$$\sum_{j=1}^{n}f(j)\sum_{d\le n/j}\mu(d).$$

The inner sum is a value of the Mertens function \(M(x)=\sum_{m\le x}\mu(m)\), ^[4] and for integers \(d\le n/j\) means \(d\le\lfloor n/j\rfloor\). Hence the formula the programs evaluate:

$$t(n)=1+\sum_{k=1}^{n}f(k)\,M\bigl(\lfloor n/k\rfloor\bigr),$$

with \(f(k)=3^k-2^k-1\) from Section 5.

The first Mertens values are \(M(1)=1\), \(M(2)=0\), \(M(3)=-1\), \(M(4)=-1\) and \(M(5)=-2\). ^[5] For \(n=5\), the term \(k=1\) gives \(0\cdot M(5)=0\), the term \(k=2\) gives \(4\cdot M(2)=0\), and \(k=3,4,5\) all have \(\lfloor5/k\rfloor=1\) and give \(18\), \(64\) and \(210\): total \(1+292=293\) again, by a different route.

9. Why only about \(2\sqrt n\) blocks are needed

The sum still has \(n=10^{10}\) terms, but \(M(\lfloor n/k\rfloor)\) takes few distinct values. If \(k\le\sqrt n\) there are at most \(\sqrt n\) choices of \(k\); if \(k\gt\sqrt n\) then \(\lfloor n/k\rfloor\lt\sqrt n\), so again at most \(\sqrt n\) values occur. Fewer than \(2\sqrt n\) values therefore occur, and the \(k\) sharing one value \(q\) form a consecutive block \(l\le k\le r\) ending at \(r=\lfloor n/q\rfloor\). For \(n=10^{10}\) there are exactly \(199\,999\) blocks.

Inside a block only the sum of the coefficients matters, and two geometric series give it in closed form:

$$\begin{aligned}A(m)&=\sum_{k=1}^{m}\bigl(3^k-2^k-1\bigr)\\&=\frac{3^{m+1}-3}2-\bigl(2^{m+1}-2\bigr)-m.\end{aligned}$$

For example \(A(10)=86516\). Summing over the blocks \((l,r,q)\), the whole sum becomes

$$t(n)=1+\sum_{(l,r,q)}\bigl(A(r)-A(l-1)\bigr)M(q).$$

Once the Mertens values are known, each block needs the two prefix values \(A(r)\) and \(A(l-1)\), and each of those costs two modular exponentiations, one of \(3\) and one of \(2\): four per block, except for the first, where \(l-1=0\) and \(A(0)=0\) is returned at once. The outer accumulation is therefore \(O(\sqrt n\log n)\) work.

10. Halving modulo \(10^9\)

The closed form divides by \(2\), and the modulus \(10^9\) is even, so \(2\) has no inverse modulo \(10^9\) and there is no modular half to multiply by. The way out is to reduce the numerator modulo \(2\cdot10^9\) first. Let \(X=3^{m+1}-3\), which is even, and let \(r=X\bmod(2\cdot10^9)\). Both \(X\) and \(2\cdot10^9\) are even, so \(r\) is even, and from \(X=2\cdot10^9q+r\) we get

$$\frac X2=10^9q+\frac r2\equiv\frac r2\pmod{10^9},$$

with \(0\le r/2\lt10^9\). A single integer halving of a residue modulo \(2\cdot10^9\) therefore yields the right residue modulo \(10^9\); the pieces \(2^{m+1}-2\) and \(m\) are reduced modulo \(10^9\) directly.

11. The Mertens function in sublinear time

We still need \(M(q)\) at every block quotient, including \(q=n=10^{10}\), far beyond a sieve's reach. The key identity is

$$\sum_{l=1}^{x}M\!\left(\left\lfloor\frac xl\right\rfloor\right)=1\qquad(x\ge1),$$

which follows by expanding each \(M\): the double sum counts each \(k\le x\) with the weight \(\sum_{d\mid k}\mu(d)\), which is \(1\) for \(k=1\) and \(0\) otherwise. ^[4] Moving the \(l=1\) term to the left gives a recursion,

$$M(x)=1-\sum_{l=2}^{x}M\!\left(\left\lfloor\frac xl\right\rfloor\right),$$

and the block grouping of Section 9 evaluates the right side with \(O(\sqrt x)\) terms. Values up to a sieve limit \(B\) are read from the table instead, and the larger ones are cached, so each is computed only once.

Take \(B\ge\sqrt n\). Every argument the recursion reaches is again a quotient of \(n\), because

$$\bigl\lfloor\lfloor n/a\rfloor/b\bigr\rfloor=\lfloor n/(ab)\rfloor,$$

and only the \(O(n/B)\) quotients \(\lfloor n/a\rfloor\) with \(a\lt n/B\) exceed \(B\). Each is evaluated once at a cost of \(O(\sqrt x)\) blocks, so the recursive work is

$$\sum_{a\le n/B}O\bigl(\sqrt{n/a}\bigr)=O\bigl(n/\sqrt B\bigr).$$

The sieve adds \(O(B)\), and balancing \(B\) against \(n/\sqrt B\) gives \(B\asymp n^{2/3}\) and \(O(n^{2/3})\) arithmetic operations for sieve and recursion together, assuming constant-time arithmetic and table lookups. This is the elementary bound for the cached quotient recurrence, not the sharper and far more elaborate Deléglise–Rivat algorithm, which reaches \(O(x^{2/3}(\log\log x)^{1/3})\). ^[4] For \(n=10^{10}\) the limit is \(4\,641\,589\), only \(2154\) quotients exceed it, and the recursion performs \(18\,269\,186\) inner steps in all.

12. How large the answer is

The reduction modulo \(10^9\) is not a decoration, and the cut-point picture bounds the size on both sides with no appeal to the signs of the Mertens values. The \(f(n)\) cuts from the exponent \(n\) alone are distinct and all counted, and no cut is counted more than once per exponent, so

$$3^n-2^n\le t(n)\le 1+A(n),$$

and \(A(n)\lt\tfrac32\cdot3^n\). Both bounds grow on the scale of \(3^n\), so the number of decimal digits grows like \(n\log_{10}3\), about \(4.77\cdot10^9\) digits at \(n=10^{10}\). Writing such a number out is hopeless, whereas the formula only adds and multiplies integers, so reducing every one of those operations modulo \(10^9\) keeps exactly the residue we are asked for.

How the Code Works

All three programs implement Sections 8 to 11 in the same order. In the C++ file, ^[9] mod_norm normalises a residue into \([0,10^9)\), mul_mod multiplies through a 128-bit intermediate, and pow_mod is binary exponentiation. sum_a_prefix is \(A(m)\) with the halving of Section 10: it raises \(3\) to the power \(m+1\) modulo \(2\cdot10^9\), subtracts \(3\), halves the residue by integer division, then subtracts \(2^{m+1}-2\) and \(m\) modulo \(10^9\).

The class Mertens holds the sieve. Its constructor truncates a floating-point estimate of \(n^{2/3}\), adds \(1\) and enforces a minimum of \(1\) to obtain limit_. The sieve init_mu starts from \(\mu(1)=1\), gives each new prime the value \(-1\), and for a product \(ip\) sets \(\mu(ip)=0\) when \(p\mid i\), since then \(p^2\mid ip\), and \(\mu(ip)=-\mu(i)\) otherwise. Breaking the inner loop at the first prime divisor of \(i\) generates every composite exactly once, from its smallest prime factor, which makes the sieve linear in limit_. Then prefix_ accumulates the values, so prefix_[x] is \(M(x)\) across the table, and get returns that entry when it can, otherwise applying the recursion of Section 11 with block grouping and caching the result in cache_.

In compute_t_mod the loop l = 1; q = n/l; r = n/q; l = r+1 enumerates the blocks of Section 9 and stores each as a Segment holding l, r, q and a slot mq. A second pass fills every mq from mertens.get, which is where all the recursion happens. The accumulation is a helper taking a start index and a stride that adds \(\bigl(A(r)-A(l-1)\bigr)M(q)\bmod 10^9\) over the segments it visits and reduces its running total only once that reaches \(10^9\); with fewer than \(1024\) segments the whole list is summed in one pass. Each segment is visited exactly once, so the order cannot change the result, and the final \(1\) of the formula is the initial value of total.

t_direct evaluates \(t(n)\) exactly for small \(n\): it sieves \(\mu\) up to \(n\), builds the prefix sums and sums \(f(k)M(\lfloor n/k\rfloor)\) over all \(k\) in 128-bit arithmetic, with no blocks, no closed form and no recursion. run_validation compares it with \(t(2)=5\), \(t(5)=293\), \(t(10)=86195\) and \(t(20)=5227991891\), and the modular path with the same values modulo \(10^9\); a mismatch aborts the program before the real computation starts.

The two ports share the mathematics but hold the blocks differently. Python's compute_t_mod collects every block as a triple in segs and then requests its Mertens value while accumulating it, keeping no mq field; Java's computeTMod accumulates each block as it is generated and stores no list. Python uses arbitrary-precision integers, the built-in three-argument pow, a bytearray for the sieve flags and a dictionary for the cache; it raises its recursion limit to \(20000\), although every recursive argument is at most half its parent, so the depth is only \(O(\log n)\). Java uses a HashMap, a byte[] for the flags and int[] arrays for the values and prefix sums, and needs no wide integer type: in powMod the modulus is at most \(2\cdot10^9\), so a product stays below \(4\cdot10^{18}\) and fits in a signed 64-bit long; in the accumulation both factors are below \(10^9\); the prefix sums obey \(|M(x)|\le x\); and the terms subtracted in the recursion total at most \(\sum_{l=2}^{x}\lfloor x/l\rfloor\lt x\ln x\). Neither port carries the C++ validation.

Complexity and Verification

The sieve costs \(O(n^{2/3})\) time and memory, the Mertens recursion \(O(n^{2/3})\) time and the outer loop \(O(\sqrt n\log n)\), so the method is \(O(n^{2/3})\) overall, against the \(10^{10}\) terms of the naive sum. For \(n=10^{10}\) the concrete figures are a sieve to \(4\,641\,589\), \(199\,999\) blocks, \(2154\) cached Mertens values above the sieve limit and \(18\,269\,186\) inner steps in the recursion. An optimised build finishes in well under a second in C++ and in Java, and in a few seconds in Python; the storage is dominated by the sieve, to which C++ and Python add \(O(\sqrt n)\) block records while Java generates its blocks as it goes. One small waste: the first block is \(k=1\) alone, whose Mertens factor is the most expensive value \(M(n)\), yet its coefficient is \(f(1)=0\), so the program pays for a value that contributes nothing.

Beyond the packaged checks, the following were verified for this article. A search straight from the definition, pruned by the bounds of Section 1 and testing the pairwise condition on every new term, gives \(1,5,23,83,293,935,2993,9233\) for \(n=1,\dots,8\), matching the formula of Section 8; repeating it without the growth condition gives the same eight numbers, confirming Section 3. An exact enumeration of the cut points, each reduced to its degree and base, reproduces \(t(n)\) for \(n\le12\), including \(t(10)=86195\) and \(t(12)=787913\). An independent implementation that sieves \(\mu\) up to \(n\) and sums all \(n\) terms one at a time, with no blocks, no closed form and no recursion, agrees with the three published programs at \(n=1000\), \(10^5\) and \(10^6\), where the residues modulo \(10^9\) are \(796154661\), \(455474245\) and \(585561545\). The closed form \(A(m)\) was checked against the direct sum for all \(m\le200\) and the halving of Section 10 against an independent evaluation up to \(m=10^{10}\). The degree lemma was tested for every cut point with \(k\le6\) and on a sample for \(k\le12\). The three programs also produce identical output at \(n=10^{10}\).

Footnotes and References

The references below supply the background facts used above. The reduction to one real number, the degree lemma, the divisor identity and every number quoted are derived or computed in this article.

1. Project Euler 319 — Bounded Sequences. The official statement asks for the number t(n) of sequences of length n with x₁ = 2, strictly increasing, and (xᵢ)ʲ < (xⱼ + 1)ⁱ for all 1 ≤ i, j ≤ n. It lists the five sequences of length 2 and three of length 5, gives t(5) = 293, t(10) = 86195 and t(20) = 5227991891, and asks for t(10¹⁰) modulo 10⁹.
2. Wikipedia — Möbius function. It defines μ(1) = 1, μ(n) = (−1)ᵏ for a product of k distinct primes and μ(n) = 0 when a square greater than 1 divides n, and states that the sum of μ(d) over the divisors of n is 1 for n = 1 and 0 otherwise, as used in Sections 7 and 11.
3. Wikipedia — Möbius inversion formula. If f(k) is the sum of g(d) over the divisors d of k for every k ≥ 1, then g(k) is the sum of μ(d) f(k/d) over those same divisors, the inversion applied in Section 7; the page derives it from the identity 1 ∗ μ = ε for Dirichlet convolution.
4. Wikipedia — Mertens function. M(n) is the sum of μ(k) for k ≤ n, with M(x) = M(⌊x⌋) for real x. The page states the identity that the sum of M(n/d) for d = 1 to n equals 1, used in Section 11, and reports that the Deléglise–Rivat method computes isolated values of M(x) in O(x^(2/3) (log log x)^(1/3)) time.
5. OEIS A002321 — Mertens's function. The entry lists 1, 0, −1, −1, −2, −1, −2, −2, −2, −1, … for n = 1, 2, 3, …, the values used in the worked check of Section 8, and notes that for n > 1 the first positive value occurs only at n = 94.
6. Wikipedia — Rational root theorem. A rational root p/q in lowest terms of an integer polynomial has p dividing the constant term and q dividing the leading coefficient, so in the monic case, which the page calls the integral root theorem, q = 1. Applied to Tᵉ − m this gives the step in Section 6.
7. Wikipedia — Perfect power. The page states the criterion that an integer is a perfect power exactly when the greatest common divisor of the exponents in its prime factorisation exceeds 1, the factorisation view used for the degree criterion of Section 6.
8. OEIS A362316 — 3ⁿ − 2ⁿ − 1. The entry lists 0, 0, 4, 18, 64, 210, 664, 2058, 6304, 19170, 58024, … and gives the closed form a(n) = 3ⁿ − 2ⁿ − 1 for n > 0, which confirms the values of f(k) listed in Section 5.
9. C++ — Euler319.cpp. The linked immutable revision contains sum_a_prefix, the Mertens class, compute_t_mod, t_direct and run_validation as described above, and is the implementation record for this article; the comparisons with the independent implementation are extra checks, not tests packaged in it.
10. Wikipedia — Bézout's identity. For integers a and b with greatest common divisor d there are integers x and y, not necessarily positive, with ax + by = d. Section 6 uses this to write g = ud + vk.