 # 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