TAOCP 5.2.1 Exercise 21

Let \(h\) and \(k\) be relatively prime positive integers.

taocpmathematicsalgorithmsvolume-3math-medium

Section 5.2.1: Sorting by Insertion

Exercise 21. [M25] Let $h$ and $k$ be relatively prime positive integers, and say that an integer is generable if it equals $xh + yk$ for some nonnegative integers $x$ and $y$. Show that $n$ is generable if and only if $hk - h - k - n$ is not generable. (Since 0 is the smallest generable integer, the largest nongenerable integer is $K_1 = hk - h - k$.) It follows that $K_1 \le K_j$ defined in the text, in any file that is both $h$-ordered and $k$-ordered.)

Verified: no
Solve time: 1m51s

Solution

Let (h) and (k) be relatively prime positive integers. An integer (n) is called generable if there exist nonnegative integers (x,y) such that (n = xh + yk). Define [ g = hk - h - k. ] We must prove that for every integer (n), [ n \text{ is generable } \iff g - n \text{ is not generable}. ]

Unique representation modulo (k)

Because (\gcd(h,k)=1), (h) is invertible modulo (k). For any integer (n) there is a unique integer (x) with (0 \le x < k) such that (n \equiv xh \pmod{k}). Then (n - xh) is a multiple of (k); write (n - xh = yk) with (y \in \mathbb{Z}). Hence every integer (n) can be written uniquely as [ n = xh + yk \qquad (0 \le x < k). ] In this representation, (n) is generable iff (y \ge 0) (the condition (x \ge 0) is already guaranteed by the choice (0 \le x < k)).

Transforming (g - n)

Observe that [ g = hk - h - k = (k-1)h - k. ] Subtracting the representation of (n) gives [ g - n = \bigl((k-1)h - k\bigr) - (xh + yk) = (k-1-x)h + (-1-y)k. ] Since (0 \le x < k), the coefficient (k-1-x) also satisfies (0 \le k-1-x < k). Thus the above is exactly the unique representation of (g - n) with the coefficient of (h) in the interval ([0, k-1]).

Equivalence

By the criterion above, (g - n) is generable iff the coefficient of (k) in this representation is (\ge 0), i.e. iff (-1-y \ge 0), which is equivalent to (y \le -1) or (y < 0).

Therefore:

  • (n) is generable (\iff y \ge 0);
  • (g - n) is generable (\iff y < 0).

These two conditions are complementary for every integer (y). Hence [ n \text{ is generable } \iff g - n \text{ is not generable}. ]

This completes the proof. ∎

Notes

The same proof works using the unique representation (n = xh + yk) with (0 \le y < h) (which exists because (k) is invertible modulo (h)). The symmetry then reads (g - n = (-1-x)h + (h-1-y)k), and generability of (g-n) is equivalent to (x < 0).