Skip to main content
OlympiadHQ

Browse · MathNet

Print

Ukrainian Mathematical Olympiad

Ukraine number theory

Problem

Let and be positive integers such that is integer. Prove that is divisible by .
Solution
Якщо виконується умова задачі, і принаймні одне з чисел дорівнює 1, то твердження є очевидним. Нехай і . Позначимо , , де — натуральні числа, причому . За умовою задачі, сума є цілим числом, тобто . З цієї рівності випливає, що і . Отже, . Оскільки добуток також є цілим числом, то , бо . Звідси випливає, що ділиться без остачі на . Звідси одержуємо, що , а числа , і діляться без остачі на (ми враховуємо, що ділиться без остачі на ), то , що й треба було довести (можна також було скористатися й властивостями конгруенцій).

Techniques

Greatest common divisors (gcd)Factorization techniques