Задание 19. Пусть q - наименьшее общее кратное, а d — наибольший общий делитель натуральных чисел х и у, удовлетворяющих равенству 3x=8у-29.
а) Может ли q/d быть равным 170?
б) Может ли q/d быть равным 2?
в) Найдите наименьшее значение q/d.
Решение.
Наибольший общий делитель d можно найти как НОД(x, y)=d. Тогда , а , где - натуральные взаимно простые числа.
а) Подставим в формулу выражения для x и y, получим:
Так как 29 – простое число, то d может принимать значения 1 или 29. Будем полагать, что d=1, тогда
,
и
,
откуда
.
Решаем квадратное уравнение, получаем:
Таким образом, получили первое число u=17, тогда второе значение
,
и
Имеем два числа, у которых НОД(17, 10)=1, а НОК(17, 10)=170, и 170:1=170.
Ответ: 17 и 10.
б) По аналогии с пунктом а) проверим, может ли , имеем:
и видим, что квадратное уравнение не имеет целых решений. Попробуем найти решение при d=29, получим уравнение:
также не имеет целых решений.
Ответ: нет.
в) 1. Будем полагать, что d=1, тогда . Так как u и v – натуральные числа, то минимальное значение u можно найти из выражения
,
и оно равно (путем подбора) u=1, тогда
.
Это и есть минимальные значения u и v, при которых
и НОД(1, 4)=1, НОК(1,4)=4 и q/d=4/1=4 – наименьшее значение при d=1.
2. Будем полагать, что d=29, тогда , и
.
Минимальное значение u=5, тогда , и
НОД(145, 58)=29, НОК(145, 58)=290 и q/d=290/29=10.
Таким образом, имеем минимальное значение .
Ответ: 4.