Таблицы Брадиса

Обозначим НОКа, Ъй через В.

Обозначим НОКа, Ъй через В.

Элементы математики в задачах - Г. А. Мерзон

Определение 3. Наименьшим общим кратным чисел а и Ъ называ­ется наименьшее из таких положительных чисел й, что й . а, й . Ъ. Обозначение: НОК(а, Ъ).

Задача 17. Докажите, что для любых а и Ъ (аЪ = 0):

а) НОК(а, Ъ) существует и единственен;

б) НОК(а, Ъ) ■ НОД (а, Ъ) = аЪ.

Решение. а) Множество положительных чисел, которые делятся на а и на Ъ, непусто, так как по крайней мере число \аЪ\ там содержится. Кроме того, оно ограничено снизу, так как наименьшее общее крат­ное не может быть меньше модулей каждого из чисел а и Ъ. Значит, в этом множестве найдется наименьший элемент.

б)  Обозначим НОД(а, Ъ) через й. Пусть а1 и Ъ1 —такие числа, что а = й ■ а1, Ъ = й ■ Ъ1. Обозначим НОК(а, Ъ)/й через В. Тогда В делится и на а1, и на Ъ1. Поскольку а1 и Ъ1 взаимно просты, В делится на их произведение а1 Ъ1, а значит, НОК(а, Ъ) делится на а1 Ъ1й, откуда НОК(а, Ъ) ^ а1 Ъ1 й. Но число а1Ъ1 й делится на а и Ъ. Следовательно, НОК(а, Ъ) = а1 Ъ1 й и НОД(а, Ъ) ■ НОК(а, Ъ) = й ■ а1Ъ1 й = аЪ.

Задача 18. Найдите НОК(12,15), НОК(120,45).

Ответ. НОК(12,15) = 3 ■ 4 ■ 5 = 60, НОК(120, 45) = 3 ■ 5 ■ 23 ■ 3 = 360.

Задача 19. Пусть (х0, у0) —решение уравнения

ах + Ъу = й.

Пусть а0 и Ъ0 — такие числа, что НОД (а, Ъ)а0 = а, НОД(а, Ъ)Ъ0 = Ъ. Покажите, что каждое решение уравнения ах + Ъу = й имеет вид

х = х0 + Ъ0£, у = У0 — а0^>

где г є z.

Решение. Очевидно, что х и у такого вида являются решением. Дока­жем, что все решения имеют такой вид. Пусть (х, у) —какое-либо

решение уравнения. Тогда, вычитая равенство ах0 + Ъу0 = d из ра­венства ах + Ъу = d, получаем а(х — х0) + Ъ(у — у0) = 0. Сокращая на НОД(а, Ъ), приходим к а0(х — х0) + Ъ0(у — у0) = 0.

Выберем теперь к и I так, что а0к + Ъ01 = 1. Тогда а0(х — х0) +