X is a finite set of integers greater than 1 such that for any positive integer n, we can find m ∈ X such that m divides n or is relatively prime to n. Show that X contains a prime or two elements whose greatest common divisor is prime.
Solution
There are elements not relatively prime to any element of X (for example, the product of all elements of X). Take the smallest such, n. Then there must be m ∈ X which divides n. If m is prime we are home. If not, take a prime p which divides m. p must also divide n (a multiple of m). Set n' = n/p, then n' < n, so we can find m' ∈ X which is relatively prime to n'. n = n'p is not relatively prime to m', so p must divide m'. So p divides both m and m'. Moreover, it must be the greatest common divisor. For if pd divides m and m', then it divides n and m' and hence d divides n' and m' which are relatively prime. So we have found two elements of X (m and m') whose greatest common divisor is prime.
© John Scholes
jscholes@kalva.demon.co.uk
14 Dec 1999