Problem:
Find the number of ordered pairs (m,n) such that m and n are positive integers in the set {1,2,…,30} and the greatest common divisor of 2m+1 and 2n−1 is not 1.
Solution:
Answer (295):
Note that
gcd(2p−1,2q−1)=gcd((2q−1)2p−q+2p−q−1,2q−1)=gcd(2p−q−1,2q−1)
Repeatedly applying this procedure, which is just the Euclidean algorithm applied to the exponents p and q, yields gcd(2p−1,2q−1)=2gcd(p,q)−1. Because 2m+1 and 2m−1 are coprime and 2m+1=2m−122m−1, it follows that
gcd(2m+1,2n−1)=gcd(2m−1,2n−1)gcd(22m−1,2n−1)=2gcd(m,n)−12gcd(2m,n)−1
If the power of 2 that divides n is greater than the power of 2 that divides m, then gcd(2m,n)=2gcd(m,n). Otherwise, gcd(2m,n)=gcd(m,n). Therefore an ordered pair (m,n) satisfies the required condition precisely when the power of 2 that divides n is greater than the power of 2 that divides m.
Break the given set into five subsets S0={1,3,5,…,29},S1={2,6,10,…,30},S2={4,12,20,28},S3={8,24},S4={16}, where positive integer x≤30 belongs to set Sk if k is the greatest exponent of a power of 2 dividing x. The desired number of ordered pairs is equal to
∣S0∣⋅(∣S1∣+∣S2∣+∣S3∣+∣S4∣)+∣S1∣⋅(∣S2∣+∣S3∣+∣S4∣)+∣S2∣⋅(∣S3∣+∣S4∣)+∣S3∣⋅∣S4∣=15⋅15+8⋅7+4⋅3+2⋅1=295.
The problems and solutions on this page are the property of the MAA's American Mathematics Competitions