Problem:
Find the number of rational numbers r,0<r<1, such that when r is written as a fraction in lowest terms, the numerator and denominator have a sum of 1000.
Solution:
Let r=baβ be a rational number in lowest terms with a+b=1000. If gcd(a,1000)=d>1, then d is also a factor of b=1000βa so baβ is not in lowest terms. On the other hand if gcd(a,1000)=1 and b=1000βa, then gcd(a,b)=1, and baβ is in lowest terms. Because 1000=23β
53, the number of positive integers less than 1000 and relatively prime to 1000 is
Ο(1000)=1000β21000ββ51000β+101000β=400.
Half of these numbers (i.e. 200β) are less than 21ββ
1000, and these are the possible numerators for a fraction of the desired type.
The problems on this page are the property of the MAA's American Mathematics Competitions