0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I hope it was given that the two numbers are positive integers, otherwise I'm afraid the number of solutions is infinite. $\endgroup$ – bof Jun 9 '18 at 5:44
  • $\begingroup$ @bof Yes, you are right. They must be positive integers. $\endgroup$ – Harsh Sharma Jun 9 '18 at 5:45
  • 1
    $\begingroup$ $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.$ $\endgroup$ – bof Jun 9 '18 at 5:47
2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.