Problem:
Let , be natural numbers with . Suppose that the sum of their greatest common divisor and least common multiple is divisible by . Prove that the quotient is at most . When is this quotient exactly equal to ?
Problem:
Let , be natural numbers with . Suppose that the sum of their greatest common divisor and least common multiple is divisible by . Prove that the quotient is at most . When is this quotient exactly equal to ?
Solution:
Let and denote the greatest common divisor and the least common multiple, respectively, of and . Then . Therefore .
Suppose that . Then we have , so we get .
Assuming we either have or .
In the former case, and the quotient is .
In the latter case, and so we get that divides . Therefore divides which implies that and , a contradiction to the given assumption that .
This shows that .
Note that for the equality to hold, we need that either or, and , . The latter case happens if and only if and are two consecutive odd numbers. (If and then divides and the quotient is precisely .)