Maclaurin 2015 Q3
3. Two integers are relatively prime if their highest common factor is 1.
I choose six different integers between 90 and 99 inclusive.
(a)Prove that two of my chosen integers are relatively prime.
(b)Is it also true that two are not relatively prime?
Maclaurin Olympiad 2015, Question 3. © UK Mathematics Trust. Original paper on ukmt.org.uk
(a)Consider the five pairs (90, 91), (92, 93), (94, 95), (96, 97), and (98, 99); each is a pair of relatively prime integers. Since we are selecting six numbers, we have to choose two from one pair; thus there is a relatively prime pair.
(b)If two or more of the six numbers chosen are even, then they have a common factor of 2.
If only one is even, then the others are 91, 93, 95, 97 and 99. Therefore two of the chosen numbers (93 and 99) have a common factor of 3.
In either case, two of my six chosen numbers have a common factor greater than 1, so are not relatively prime.
If only one is even, then the others are 91, 93, 95, 97 and 99. Therefore two of the chosen numbers (93 and 99) have a common factor of 3.
In either case, two of my six chosen numbers have a common factor greater than 1, so are not relatively prime.
Solution © UK Mathematics Trust, from the Maclaurin Olympiad 2015 solutions.