A set of integers is such that if a and b belong to it, then so do a2 - a, and a2 - b. Also, there are two members a, b whose greatest common divisor is 1 and such that a - 2 and b - 2 also have greatest common divisor 1. Show that the set contains all the integers.
Solution
Suppose 1 belongs to the set. Then so does 0 = 12 - 1.We have 02 - 1 = -1, 12 - (-1) = 2, 22 - 1 = 3, 22 - 0 = 4, 22 - (-1) = 5. Now given that we have every integer up to k2 we can get the integers from k2 + 1 to (k + 1)2 using (k + 1)2 - h for h = 0, 1, ... , 2k (assuming that k ≥ 2). Hence we can get all positive integers. Now to get any negative integer -k just take 02 - k.
Now if a, b, c belong to the set, then so do (a2 - b2) + c = a2 - (b2 - c) and -(a2 - b2) + c. So by induction n(a2 - b2) + c belongs for any integer n. Put A = a2 - b2. Now if a' and b' are two other numbers in the set, put B = a'2 - b'2. Then mA + nB + c belongs to the set for all integers m and n. If we could find A and B which were relatively prime, then we would be home, because we could find m, n for which mA + nB = 1 and hence we could find m, n for which mA + nB = -(c - 1), so that mA + nB + c = 1.
It is not obvious how to find such A, B. But we can find A, B, C such that the greatest common divisor is 1 and that is sufficient. Let A = a2 - b2, where a, b are the two given numbers. Let B = a3(a - 2) and let C = b3(b - 2). Since a is in the set so is a2 - a and B = (a2 - a)2 - a2. Similarly C. So certainly all numbers mA + nB + rC + a are in the set for any integers m, n, r. If a prime p divides B, then it must divide a or a - 2. If it also divides A, then it cannot divide a, for then it would also divide b2 and hence b, but we are told that a and b have no common factor. So any prime dividing all of A, B and C must divide a - 2. Similarly, it must divide b - 2. But we are told that a - 2 and b - 2 have no common factor. Hence A, B, C have no common factor. So we can find m, n, r such that mA + nB + rC = 1, and hence m, n, r such that mA + nB + rC = -(a - 1) and hence such that mA + nB + rC + a = 1.
© John Scholes
jscholes@kalva.demon.co.uk
11 May 2002