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$
3
  • $\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
    Commented Jun 9, 2018 at 5:44
  • $\begingroup$ @bof Yes, you are right. They must be positive integers. $\endgroup$ Commented Jun 9, 2018 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
    Commented Jun 9, 2018 at 5:47

1 Answer 1

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$
1
  • $\begingroup$ How could I have overlooked this fact? Thanks for this "simply" beautiful answer. $\endgroup$ Commented Jun 9, 2018 at 5:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .