# The sum of two positive integers is $2310$ and $11$ is their g.c.d. How many pairs of such numbers are possible?

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?

• I hope it was given that the two numbers are positive integers, otherwise I'm afraid the number of solutions is infinite. – bof Jun 9 '18 at 5:44
• @bof Yes, you are right. They must be positive integers. – Harsh Sharma Jun 9 '18 at 5:45
• $1=(a,b)=(a,a+b)=(a,210).$ The number of positive integers less than $210$ and relatively prime to $210$ is $\varphi(210)=\varphi(2\cdot3\cdot5\cdot7)=\varphi(2)\varphi(3)\varphi(5)\varphi(7)=1\cdot2\cdot4\cdot6=48.$ – bof Jun 9 '18 at 5:47

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)$.

• How could I have overlooked this fact? Thanks for this "simply" beautiful answer. – Harsh Sharma Jun 9 '18 at 5:44