Тема 01 · Математика, углублённый уровень · подтема 3 из 5

НОД и НОК в текстовых задачах

Делимость, НОД и НОК, остатки. 100 заданий.

Решено

Правильно

Точность

Простыми словами

Каждое натуральное число больше 1 «собрано» из простых чисел, как слово из букв: $360 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 3 \cdot 5$ . Зная этот «состав», легко ответить на любой вопрос: делится ли число на 45, сколько у него делителей, каков НОД и НОК. А остатки помогают с циклами — днями недели, последними цифрами степеней.

Признаки делимости на составные числа

Составной делитель раскладывают на взаимно простые множители и проверяют каждый признак отдельно:

На	12	15	18	36	45	72
Проверяем	3 и 4	3 и 5	2 и 9	4 и 9	5 и 9	8 и 9

«На 4 и на 6 — значит на 24» — неверно: 4 и 6 не взаимно просты. Число 12 делится на 4 и на 6, но не на 24.

Наименьшее число вида $* 948 *$ , делящееся на $45$ .

$45 = 5 \cdot 9$ . На 5: последняя цифра $0$ или $5$ .
На 9: сумма цифр $a + 9 + 4 + 8 + b = 21 + a + b$ делится на 9.
Хотим маленькую первую цифру. При $b = 5$ : $26 + a$ кратно 9 → $a = 1$ : $19485$ . При $b = 0$ : $a = 6$ — больше.
Ответ: $19485$ .

Разложение и число делителей

n = p^{a} \cdot q^{b} \cdot r^{c} \Rightarrow делителей (a + 1) (b + 1) (c + 1)

p, q, r

— разные простые множители числа

n

a, b, c

— показатели их степеней

$360 = 2^{3} \cdot 3^{2} \cdot 5$ → $(3 + 1) (2 + 1) (1 + 1) = 24$ делителя.

Ровно 2 делителя — простое число; ровно 3 — квадрат простого ( $p^{2}$ ); ровно 5 — $p^{4}$ (например, $81 = 3^{4}$ ).
Точный квадрат — все показатели чётные, точный куб — все кратны 3.

Сколько делителей числа $4212$ делятся на $54$ ?

$4212 = 2^{2} \cdot 3^{4} \cdot 13$ , $54 = 2 \cdot 3^{3}$ .
Такой делитель равен $54 \cdot m$ , где $m$ — делитель числа $4212 : 54 = 78 = 2 \cdot 3 \cdot 13$ .
У $78$ делителей $2 \cdot 2 \cdot 2 = 8$ . Ответ: $8$ .

НОД и НОК в задачах

НОДОбщие простые множители в наименьших степенях. «Наибольшее число одинаковых подарков», «разрезать на наибольшие равные куски».

НОКВсе простые множители в наибольших степенях. «Снова одновременно», «впервые вместе», «наименьшее число, кратное…».

НОД (a, b) \cdot НОК (a, b) = a \cdot b

для двух чисел

208 конфет и 224 груши — в наибольшее число одинаковых подарков. Сколько груш в подарке?

$208 = 2^{4} \cdot 13$ , $224 = 2^{5} \cdot 7$ ; $НОД = 2^{4} = 16$ подарков.
Груш в подарке: $224 : 16 = 14$ .

Автобусы уходят в 7:15 вместе, интервалы 21 и 25 мин. Когда снова вместе?

$НОК (21, 25) = 525$ мин $= 8$ ч $45$ мин.
$7 : 15 + 8 : 45 = 16 : 00$ — ровно 0 минут после начала часа.

Остатки и циклы

Остаток суммы (произведения) равен остатку суммы (произведения) остатков.
Один и тот же остаток $r$ при делении на $a$ и $b$ : $n = НОК (a, b) \cdot k + r$ .
Не хватает 1 до делимости на $a$ и $b$ : $n = НОК (a, b) \cdot k - 1$ .
Последние цифры степеней повторяются: у $7^{n}$ — $7, 9, 3, 1, 7, 9, \dots$ (цикл длины 4).

Через 489 дней:

489 = 7 \cdot 69 + 6

— полные недели не меняют день, остаётся сдвиг на 6

Сегодня воскресенье. Через 489 дней: остаток $489 : 7$ равен $6$ ; от воскресенья на 6 дней вперёд — суббота. Из среды через 316 дней: $316 = 7 \cdot 45 + 1$ → четверг.

Если что-то повторяется с периодом $k$ , важен только остаток от деления номера (или числа шагов) на $k$ .

Подсчёты и перебор

Сколько чисел на отрезке делится на $k$ . От $1$ до $N$ их $[N : k]$ ; от $a$ до $b$ — $[b : k] - [(a - 1) : k]$ . «На 8 или на 9» — по формуле включений: $[\dots : 8] + [\dots : 9] - [\dots : 72]$ .

Сколько чисел от 21 до 147 делятся на 8 или на 9?

На 8: $[147 : 8] - [20 : 8] = 18 - 2 = 16$ . На 9: $[147 : 9] - [20 : 9] = 16 - 2 = 14$ .
На 72 (и на 8, и на 9): $[147 : 72] - [20 : 72] = 2 - 0 = 2$ .
$16 + 14 - 2 = 28$ .

Нечётные делители — делители числа без двоек. $4536 = 2^{3} \cdot 3^{4} \cdot 7$ : нечётные делители — делители $3^{4} \cdot 7$ , их $(4 + 1) (1 + 1) = 10$ .

Кратное с различными цифрами ищут перебором кратных от края: наименьшее четырёхзначное, кратное 52, — $1040$ (цифры повторяются), $1092$ — все цифры разные. Ответ $1092$ .

Шестерёнки. Отмеченные зубцы снова встретятся, когда каждая шестерёнка провернётся на $НОК$ зубцов. У шестерёнок с 38 и 21 зубцом $НОК = 798$ : первая сделает $798 : 38 = 21$ оборот.

Простые числа

Единственное чётное простое — $2$ . Если сумма двух простых нечётна, одно из них $2$ : сумма 9 → $2 + 7$ , произведение $14$ .
Проверка на простоту: достаточно делить $n$ на простые $p$ с $p \cdot p \leq n$ . Для $n < 400$ хватит простых до 19.
Числа-близнецы — простые $p$ и $p + 2$ . Между 250 и 314: $269$ и $271$ , $281$ и $283$ , $311$ и $313$ .

Число $1$ не простое. Нечётное число не обязательно простое: $91 = 7 \cdot 13$ , $221 = 13 \cdot 17$ .

Посмотреть и посчитать

Калькуляторы

НОД и НОК Разложение на простые множители

Серия: 0