GCD

The lcm \text{lcm} of two positive integers is 7 times their gcd \gcd . If the sum of the two integers is 56, what is the value of their gcd \gcd ?

This problem was collected from Bangladesh Regional Olympiad


The answer is 7.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Somoy Subandhu
Nov 17, 2014

Note that, if a,b are two integers such that, lcm is their least common multiple and gcd is their greatest common divisor then, l c m × g c d = a × b lcm\quad \times \quad gcd\quad =\quad a\quad \times \quad b

and , a,b can also be written as a=gx * [here,g stands for gcd] and * b=gy

Now , we know that their lcm = 7g

hence, from the points above we can say ,

7 g × g = g x × g y 7g\quad \times \quad g\quad =\quad gx\quad \times \quad gy

or, 7 = x × y 7\quad =\quad x\quad \times \quad y

as x and y must be integers , either one of them must be 1 and the other one should be 7

now we also know that a+b=56 so,

gx+gy=56

g(x+y)=56

Hence g=7 [as x+y must be 8]

Nice solution

Sushree Snehaja Biswal - 6 years, 6 months ago
Abdullah Shahriar
Nov 18, 2014

g c d ( a , b ) l c m [ a , b ] = 7 k gcd(a,b)*lcm[a,b]=7k

\Rightarrow There are 7 possible pairs.

\Rightarrow ( 1 , 7 ) , ( 2 , 14 ) , ( 3 , 21 ) , ( 4 , 28 ) , ( 5 , 35 ) , ( 6 , 42 ) , ( 7 , 49 ) (1,7),(2,14),(3,21),(4,28),(5,35),(6,42),(7,49)

\Rightarrow From the pairs 7 + 49 = 56 7+49=56 satisfies the condition.
Thus the answer is g c d ( 7 , 49 ) = gcd(7,49)= 7 \boxed{7}

Kumar Shashwat
Nov 17, 2014

Product of lcm and hcf is equal to the product of numbers. hcf cannot be greater than any of the two numbers. The numbers will be multiples of 7.
Cases will be 7,49 14,42 21,35 and 28,28. Checking hcf lcm for the pairs 7 is the answer.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...