The sum of two positive integers is 2310 and 11 is their g.c.d. How many pairs of such numbers are possible?
Since 11 has been given as the g.c.d of the two numbers, we can write the numbers as 11a and 11b such that (a,b)=1
As per the question's statement 11a+11b=2310
a+b=210
The question has been reduced till the point where it needs (as per this approach) brute force calculation (making the pairs and checking whether they are co-primes). But this question was given to me by a friend who is preparing for an exam where questions are to be solved (usually) in around a minute. Does there exist a way in which this problem can be solved with a better approach?
Answer
Pairs (a,b) with a+b=210 and gcd are equivalent to pairs (a,b) with a+b=210 and \gcd(a,a+b) = \gcd(a,210) = 1, since \gcd(x,y) = \gcd(x,x+y) in general.
There are \phi(210) integers a between 1 and 210 such that \gcd(a,210)=1, giving us \phi(210) pairs (a,b).
No comments:
Post a Comment