Can we find an integer N such that if a and b are integers which are equally spaced either side of N/2 (so that N/2 - a = b - N/2), then exactly one of a, b can be written as 19m + 85n for some positive integers m, n?
Solution
Answer: yes, N = 1719,
If 1615 = 19·85 = 19m + 85n with m, n positive, then 19 divides n, so n ≥ 19, so 19m + 85n > 85n ≥ 85·19 = 1615. Contradiction. Hence 1615 cannot be expressed in this form. But all numbers > 1615 can. Adding 1 = 9·19 - 2·85 to 9·85 repeatedly gives: 1615 + 1 = 9·19+17·85, ... , 1615 + 9 = 81·19 + 1·85. Then 1615 + 10 = 90·19 - 85 = 5·19 + 18·85. Continuing to add 1 gives: 1616 + 11 = 14·19 + 16·85, ... , 1615 + 18 = 77·19 + 2·85. Finally, 1615 + 19 = 1·19 + 19·85. Then adding multiples of 19 gives all higher numbers. Obviously 104 = 1·19 + 1·85 and no integer < 104 has the desired form.
So N ≥ 1720 is ruled out, because both 104 and N - 104 have the desired form and are equally spaced about N/2. Similarly, N ≤ 1718 is ruled out, because neither 1615 nor N - 1615 have the desired form. So the only possible candidate for N is 1719.
We have already shown that for N = 1719, just one of a, 1719 - a has the desired form for a ≤ 104 and a ≥ 1615. So it remains to consider 104 < a < 1615. Using 1 = 9,19 - 2·85, we may write a = 19m + 85n with m and n integers (but possibly negative). Then adding and subtracting multiples of 19·85 we may take 1 ≤ m ≤ 85. Then 104 < a < 1615 implies that -17 ≤ n ≤ 18. If 1 ≤ n ≤ 18, then a has the desired form. If not then -17 ≤ n ≤ 0, so 1719 - a = (86·19 + 85) - (19m + 85n) = 19(86 - m) + 85(1 - n), which has the desired form. Thus in any case at least one of a, 1719 - a has the desired form.
Suppose both have the desired form, so that a = 19m + 85n, 1719 - a = 19m' + 85n', with m, n, m', n' all positive integers. Then, adding, 1719 = 19(m + m') + 85(n + n'), so 1615 = 19(m + m' - 1) + 85(n + n' - 1), where m + m' - 1 and n + n' - 1 are positive integers. But we have already shown that is impossible. So a and 1719 - a cannot both have the desired form. So 1719 meets the criterion.
Thanks to Demetres Christofides for pointing out the error in my original solution.
© John Scholes
jscholes@kalva.demon.co.uk
8 Sep 2002