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(a,b)=1$ 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