МАЛЫЙ МЕХМАТ МГУ

Кружок 8 класса

Версия для печати

Занятие 3. НОД и НОК

Определение. Наибольший общий делитель целых чисел a и b — это наибольшее натуральное число c такое, что a делится на c и b делится на c. Обозначается НОД(a, b) или просто (a, b). Аналогично определяется НОД нескольких целых чисел.

Определение. Наименьшее общее кратное целых чисел a и b — это наименьшее натуральное число c такое, что c делится на a и c делится на b. Обозначается НОК(a, b) или [a, b]. Аналогично определяется НОК нескольких целых чисел.

Теорема 1. Пусть числа a и b разложены на простые множители: a = p₁^m₁ … p_k^m_k , b = p₁^n₁ … p_k^n_k , где m_i ≥ 0, n_i ≥ 0. Тогда их НОД и НОК можно найти по формулам:

Теорема 2. Для любых двух целых чисел a и b имеет место равенство НОД(a, b) · НОД(a, b) = a·b

1.

Вычислите (без калькулятора!):

a)

(8, 64) и [8, 64];

б)

(36, 60) и [36, 60];

в)

(125, 1534569) и [54, 163];

г)

(2³· 3¹⁵· 7¹⁹, 2³¹· 3²· 11³) и [2³·3²·5², 2²·3³·5³]

2.

Бак был полон воды. Эту воду поровну перелили в три бидона. Оказалось, что в первом бидоне вода заняла половину его объема, во втором — ⅔ объема, а в третьем — ¾ его объема. Бак и все три бидона вмещают по целому числу литров. При каком наименьшем объеме бака это возможно?

3.

Ровно в полдень Клайв закрасил число 12 на циферблате часов красным цветом и решил через каждые 57 часов закрашивать текущий час в красный цвет.

a)

Сколько чисел окажутся покрашенными через месяц?

б)

А если Клайв будет красить их каждый 1913-й час в течение всей жизни?

4.

a)

Про натуральные числа a и b известно, что 15a = 14b и (a, b) = 13. Найдите a и b.

б)

a и b — целые числа, удовлетворяющие равенству 56a = 65b. Докажите, что a + b — составное число.

5.

a)

Объясните, почему в теореме 1 можно считать, что числа a и b имеют один и тот же набор простых множителей p₁, … ,p_k. (Обратите внимание, что некоторые m_i и n_i могут быть равны нулю!)

б)

Докажите теорему 1.

в)

С помощью теоремы 1 докажите теорему 2.

г)

Когда НОК(a, b) = ab?

6

Докажите, что среди любых десяти последовательных натуральных чисел найдется число, взаимно простое с остальными.