Problem:
Find the number of ordered pairs such that and are positive integers in the set and the greatest common divisor of and is not .
Solution:
We are asked to find the number of ordered pairs with such that .
Let and . We want , i.e., there exists an integer dividing both and .
Suppose a prime divides both and . Then:
and .
Squaring the first congruence gives , so the order of modulo divides both and , but not (otherwise we would have , a contradiction). Therefore, the order of modulo is even.
While this provides structure, it is hard to count such pairs directly without overcounting. So instead, we perform a brute-force computation for all and count the number of pairs where .
Checking all possibilities, we find that exactly ordered pairs satisfy the condition.
The problems on this page are the property of the MAA's American Mathematics Competitions