Possible HCF?

Number Theory Level pending

The sum of two positive numbers is 629 629 and their greatest common divisor is 37 37 .

What is the total number of possible pairs satisfying the conditions?

Note: Possible pairs mean unordered pairs, where ( a , b ) (a,b) and ( b , a ) (b,a) are counted as 1 1 pair.


The answer is 8.

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.

2 solutions

Mahdi Raza
Apr 19, 2020

If the greatest common divisor of two numbers is 37, both numbers are divisible by 37. \therefore Let the numbers be a = 37 x , b = 37 y a = 37x, b = 37y . We are given that the sum of a and b = 629. \therefore 37 ( x + y ) = 629 x + y = 17 37(x+y) = 629 \implies x + y = 17 . There are total 16 unordered pairs since both a , b a, b are positive. But since ( a , b ) (a,b) is the same as ( b , a ) (b,a) . There are half as many pairs = 8 = \boxed{8}

Chew-Seong Cheong
Apr 19, 2020

Let the two numbers be m m and n n . Since their greatest common divisor is 37 37 , which is a prime. Then m = 37 a m=37a and n = 37 b n=37b , where a a and b b are positive integers. Then m + n = 37 ( a + b ) = 629 m+n = 37(a+b) = 629 a + b = 17 \implies a+b = 17 and there are 8 \boxed 8 possible pairs ( 1 , 16 ) (1,16) , ( 2 , 15 ) (2,15) , ( 3 , 14 ) (3,14) , \cdots , ( 8 , 9 ) (8,9) .

@Sahar Bano , you have to mention the two numbers are positive, because GCD applies to negative numbers too, then the number of possible pairs is infinitely large.

Chew-Seong Cheong - 1 year, 1 month ago

Log in to reply

Please edit the problem for this

Sahar Bano - 1 year, 1 month ago

Log in to reply

I have done it before I wrote the above comments.

Chew-Seong Cheong - 1 year, 1 month ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...