Prove that we can find an infinite set of positive integers of the form 2n - 3 (where n is a positive integer) every pair of which are relatively prime.
Solution
We show how to enlarge a set of r such integers to a set of r+1. So suppose 2n1 - 3, ... , 2nr - 3 are all relatively prime. The idea is to find 2n - 1 divisible by m = (2n1 - 3) ... (2nr - 3), because then 2n - 3 must be relatively prime to all of the factors of m. At least two of 20, 21, ... , 2m must be congruent mod m. So suppose m1 > m2 and 2m1 = 2m2 (mod m), then we must have 2m1 - m2 - 1 = 0 (mod m), since m is odd. So we may take nr+1 to be m1 - m2.
Solutions are also available in: Samuel L Greitzer, International Mathematical Olympiads 1959-1977, MAA 1978, and in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.
© John Scholes
jscholes@kalva.demon.co.uk
8 Oct 1998
Last updated/corrected 14 Mar 03