Show that we can link any two integers m, n greater than 2 by a chain of positive integers m = a1, a2, ... , ak+1 = n, so that the product of any two consecutive members of the chain is divisible by their sum. [For example, 7, 42, 21, 28, 70, 30, 6, 3 links 7 and 3.]
Solution
We write a ↔ b if (a + b) divides ab. The starting point is that for n > 1 we have n ↔ n(n - 1). As slight variants we also have 2n ↔ n(n - 2) for n > 2, and in any case where a ↔ b, then also ma ↔ mb (for m > 0). That allows us to link n > 2 and 2n, thus: n ↔ n(n - 1) ↔ n(n - 1)(n - 2) = n(n - 2) ↔ 2n.
To go much further we need some inspiration. Note that n(n - 3) + 2 = (n - 1)(n - 2). So 2(n - 1)(n - 2) ↔ n(n - 3)(n - 1)(n - 2). That is critical, for it is a general way of allowing us to reduce the largest factor. Thus for n > 3, n ↔ n(n - 1) ↔ n(n - 1)(n - 2) ↔ n(n - 1)(n - 2)(n - 3) ↔ 2(n - 1)(n - 2) ↔ (n - 1)(n - 2) ↔ n - 1. But linking n and n-1 obviously allows us to link any two integers > 3. That leaves 3 itself, but the question already shows how to link that to at least one integer > 3, which is all we need.
© John Scholes
jscholes@kalva.demon.co.uk
11 May 2002