How many pairs of positive integers x, y exist such that HCF (x, y) +

Question

How many pairs of positive integers x, y exist such that HCF (x, y) + LCM (x, y) = 91?

A. 10
B. 9
C. 8
D. 6
E. 7

Are You Up For the Challenge: 700 Level Questions

nick1816 · Accepted Answer

x=ka
y=kb

GCD(x,y) = k
LCM(x,y) = k*a*b

k(1+ab) = 91

k must be a factor of 91. As, a and b are non-zero, k can't be 91.

k= 1, 7 or 13

Case 1 -

k= 1; LCM=x*y = 90= 2*3^2*5
Number of possible solutions = 2^2 = 4

Case 2- k =7; a*b = 12= 2^2*3
Number of possible solutions = 2^1 =2

Case 2- k =13; a*b = 6= 2*3
Number of possible solutions = 2^1 =2

Total unordered solutions = 4+2+2=8

nick1816 · Answer

firas92   AnirudhaS   AdiBatman   jackfr2

a*b = 90= 2*3^2*5

a and b are co-primes. Hence, these 2 numbers have no shared factors. So either a or b is a multiple of  3^2 . (You can't split it between a and b)

So we can write a as  2^x*(3^2)^y*(5)^z

x,y and z can be 0 or 1

Total possible values of a = 2*2*2=8

This will give you number of ordered pairs of (a,b).

For example- 
i) when x=y=z=0; a=1 and b= 90

ii) when x=y=z=1; a=90 and b= 1

Number of unordered pairs =  \frac{2^3}{2}=2^2 =4

If number of prime factors of a*b is n, and a and b are coprimes, then number of possible ordered pair of (a,b) =  2^n  and number of unordered pair of (a,b) is  2^{n-1}

preetamsaha · Answer

Let us x = h * a; y = h * b (h= HCF )
a and b are co-prime. 
So, LCM of (x, y) = h * a * b

by given condition, h + h * a * b = 91. 
Or,h* (ab + 1) = 91
Now, 91 can be written as 1 * 91 or 7 * 13
Or, we can have HCF as 1, LCM as 90 - 
There are 4 pairs of numbers like this (2, 45), (9, 10), (1, 90) and (5, 18)

We can have HCF as 7, ab + 1 = 13 => ab = 12 => 1 * 12 or 4 * 3

Or, the pairs of numbers are (7, 84) or (21, 28)

The third option is when HCF = 13, ab + 1 = 7 => ab = 6
Or (a, b) can be either (1, 6) or (2, 3)
The pairs possible are (13, 78) and (26, 39)
There are totally 8 options possible - (2, 45), (9, 10), (1, 90), (5, 18), (7, 84), (21, 28), (13, 78) and (26, 39).
8 Pairs.

correct answer C

chetan2u · Answer

The very first number that would come is if HCF is 1, LCM will be 90, as 1+90=91...
Product = 1*90=90=2*45=3*30=5*18=6*15=9*10
Now HCF and LCM have to be co-prime here, so possibilities
1*90
2*45
5*18
9*10

Now to check other possibilities, let us use the formula HCF*LCM=x*y
Now, let HCF=z, so x=az and y=bz, where a and b are co-prime..
 z*LCM=x*y=az*bz........LCM=abz

Now  HCF (x, y) + LCM (x, y) = 91........z+abz=91........z(1+ab)=91 
z is a positive number, as also ab+1
so .z(1+ab)=91=1*91=7*13

First case ----1*91 
So  z=1 , and  ab+1=91....ab=90 
Now we have already seen ab=90 gives us 4 possibilities above

Second case ----7*13 
So  z=7 , and  ab+1=13.........ab=12=3*4=1*12 
when a=3 and b=4, x=7*3 and y=4*7...(21,28)
when a=1 and b=12, x=7*1 and y=12*7...(7,84)

Third case ----7*13 
So  z=13 , and  ab+1=7.........ab=6=2*3=1*6 
when a=2 and b=3, x=13*2 and y=13*3...(26,39)
when a=1 and b=6, x=13*1 and y=13*6...(13,78)

So total 4+2+2=8 pairs.. But if (x,y) is different from (y,x), double that.

C

Note - although it will not show up in GMAT in present form, but the concept of HCF and LCM is surely tested..

firas92 · Answer

Hi  nick1816

Can you explain how you get the highlighted parts?

AnirudhaS · Answer

Hi  nick1816 , can you please explain how are you getting the number of possible solutions please?

Also I think when k=1, you should have prime factorisation  2^1.3^2.5^1  (instead of  2^2.3^2.5^1 )

AdiBatman · Answer

Hi can you please explain how do you get the possible solutions, Thanks in advance!!

jackfr2 · Answer

k= 1; LCM=x*y = 90= 2^2*3^2*5
Number of possible solutions = 2^2 = 4

in this line how are you getting that 2^2 number ? and in the following lines it is 2^1 but I'm not getting why. please explain

jackfr2 · Answer

Hey, thanks . but can you post or link more similar questions for practice?

ryorye · Answer

Did anyone explain the highlighted parts?

I don't understand how you come up with 8 x,y pairs.

I understand up to k(1+ab) = 91, and that (1+ab) = 7, 13 or 91.

So therefore I understand that (ab) = 6,12 or 90.

So, how do you go from (ab = 6,12 or 90) to 8 possible pairs of x,y?

I keep getting lost from there, sorry

Really would appreciate if someone can help on this.

Thanks

Really would appreciate if someone can help on this. Thanks

bumpbot · Answer

Automated notice from GMAT Club BumpBot:

A member just gave Kudos to this thread, showing it’s still useful. I’ve bumped it to the top so more people can benefit. Feel free to add your own questions or solutions.

This post was generated automatically.

How many pairs of positive integers x, y exist such that HCF (x, y) +

Prep Toolkit

Top 5 GMAT Debrief Videos

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

GMAT Problem Solving (PS) Questions

How many pairs of positive integers x, y exist such that HCF (x, y) +

Prep Toolkit

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia