Browse · MathNet
Print75th Romanian Mathematical Olympiad
Romania number theory
Problem
The positive integers are such that is a common multiple of and ().
a) Prove that the greatest common divisor of and is .
b) Find the positive integers , so that and fulfill ().
a) Prove that the greatest common divisor of and is .
b) Find the positive integers , so that and fulfill ().
Solution
a) Since and , . Now implies , hence . Then .
b) From and (a), . Since , . From follows .
Case I: . Then , , , whence . The values of so that , are: , implying ; , implying ; , implying .
Case II: . Then , , . So , yielding and .
In conclusion, .
b) From and (a), . Since , . From follows .
Case I: . Then , , , whence . The values of so that , are: , implying ; , implying ; , implying .
Case II: . Then , , . So , yielding and .
In conclusion, .
Final answer
{18, 144, 486, 900}
Techniques
Greatest common divisors (gcd)Least common multiples (lcm)Techniques: modulo, size analysis, order analysis, inequalities