# Solutions to Number Theory Questions – LCM and HCF

Have given below solutions to questions given here . Apologies for the error in the 4th question that had been posted earlier (the question has now been removed). Had been thinking about this question for a while, and in my haste typed something wrong. Many thanks to the guys on yahoogroups that had pointed this out.

Anyways, the solutions are as follows
1. How many pairs of positive integers x,y exist such that HCF of x,y = 35 and sum of x and y = 1085?
Let HCF of (x,y) be h. Then we can write x = h*a and y = h*b. Furthermore, note that HCF (a,b) = 1. This is a very important property. One that seems obvious when it is mentioned but a property a number of people overlook.
So, we can write x = 35a; y = 35b
x + y = 1085 => 35( a + b) = 1085. => (a+b) = 31. We need to find pairs of coprime integers that add up to 31. (Another way of looking at it is to find out integers less than 31 those are coprime with it or phi(31) as one of the replies had mentioned. More on this wonderful function in another post).

Since 31 is prime. All pairs of integers that add up to 31 will be coprime to each other. Or, there are totally 15 pairs that satisfy this condition.

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

This has become one of my favourite questions. Had not thought much about it when I had written down the question – but came to realise that there are perhaps many more interesting questions that can be created in this genre.
Again let us write x = h * a; y = h * b,
a and b are coprime. So, LCM of (x,y) = h*a*b
So, in essence 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 as 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)
3. Sum of two numbers x,y = 1050. What is the maximum value of the HCF between x and y?
x=525 y =525 works best.
If the question states x,y have to be distinct, then the best solution would be x=350 y =700, HCF = 350

### Related posts

• November 13, 2010 Solutions to Number theory questions – LCM HCF Have given below solutions to the questions on Number Theory LCM, HCF. The questions can be found here. Solutions sent it at the yahoogroups were more or less spot on, so I am just […] Posted in Number Theory
• November 10, 2010 Number Theory questions – LCM HCF Here are a few questions from LCM & HCF? 1. How many pairs of positive integers x,y exist such that HCF of, x,y = 35 and sum of x and y = 1085? 2. How many pairs of positive […] Posted in Number Theory
• November 11, 2010 Number Theory questions – LCM HCF Few more questions on LCM and HCF on Number Theory 1. How many pairs of integers (x,y) exist such that the product of x, y and HCF (x,y) = 1080? 2. Find the smallest number that […] Posted in Number Theory
• November 13, 2010 CAT Number Theory – Final few questions Have given below few more questions on Number Theory A 4-digit number of the form aabb is a perfect square. What is the value of a-b? LCM of three numbers is equal to 1080; HCF of […] Posted in Number Theory