An Irish Set is a set of positive integers such that each pair of integers in the set has a common factor greater than , and there is no prime number that divides all integers in this set. Is there an Irish Set that contains exactly integers, all smaller than ?
Solution
A key observation is that when we add to the Irish Set any positive multiple of an element that is not yet contained in we obtain an Irish Set with elements.
One possibility then is to start with an Irish Set of length and add multiples of these three numbers to the set. One may pick prime numbers and form the Irish Set of cardinality . For example, using the primes we obtain the set which is Irish.
We can extend to a larger Irish Set by including as many positive integers of the form , and as we wish. The requirement that all members of the set are smaller than then leads to the conditions , , and .
Because the lowest common multiple of any two of the three numbers is equal to , we multi-count all multiples of but no other number when we add and . Each multiple of appears three times. Since , we have constructed an Irish set that contains exactly
elements. We can now remove any members from this set to get a set that contains exactly elements, all smaller than , such that no pair of members of this set is coprime. Is it still true that no prime number divides all integers in this set? This can easily be achieved by leaving in the set. However, this is true in general, because after removing any members from this set, there will be at least one pair of consecutive multiples of left in the set, and similarly for multiples of and . Since , we see that after removing any numbers we indeed get an Irish Set.