НОД и НОК

НОД — наибольшее из чисел, на которые делятся оба числа без остатка. Общие делители 12 и 18 — это 1, 2, 3, 6; наибольший 6, то есть НОД(12, 18) = 6. НОД нужен для сокращения дробей.

НОК — наименьшее из чисел, которые делятся на оба числа. На 4 и 6 делятся 12, 24, 36; наименьшее 12, то есть НОК(4, 6) = 12. НОК нужен для сложения дробей с разными знаменателями.

Formulalar

Связь НОД и НОКEKUB(a, b) · EKUK(a, b) = a · b
НОК через НОДEKUK(a, b) = a · b / EKUB(a, b)
Алгоритм ЕвклидаEKUB(a, b) = EKUB(b, a mod b), EKUB(a, 0) = a

Yechish tartibi

Способ разложения: разложите оба числа на простые множители.
НОД — произведение ОБЩИХ множителей в наименьших степенях. 12 = 2²·3, 18 = 2·3² → НОД = 2·3 = 6.
НОК — произведение ВСЕХ множителей в наибольших степенях. 12 = 2²·3, 18 = 2·3² → НОК = 2²·3² = 36.
Алгоритм Евклида быстрее: делите большее на меньшее, берёте остаток и повторяете, пока остаток не станет 0. Последний ненулевой остаток — НОД.

Namunaviy savollar

Найдите НОД(48, 36) и НОК(48, 36).
Решение
EKUB = 12, EKUK = 144
1. 48 = 2⁴ · 3, 36 = 2² · 3²
2. НОД: общие в наименьшей степени → 2² · 3 = 12
3. НОК: все в наибольшей степени → 2⁴ · 3² = 144
4. Проверка: 12 · 144 = 1728 = 48 · 36
Найдите НОД(1071, 462) алгоритмом Евклида.
Решение
21
1. 1071 = 2 · 462 + 147
2. 462 = 3 · 147 + 21
3. 147 = 7 · 21 + 0
4. Последний ненулевой остаток — 21.

Часто встречающиеся пары

a	b	EKUB	EKUK
4	6	2	12
6	8	2	24
8	12	4	24
9	12	3	36
10	15	5	30
12	18	6	36
14	21	7	42
15	20	5	60
16	24	8	48
18	24	6	72
20	30	10	60
24	36	12	72
25	35	5	175
27	36	9	108
30	45	15	90
36	48	12	144
40	60	20	120
48	72	24	144

Savol va javob

Как найти НОД?

Разложите оба числа на простые множители и перемножьте общие в наименьшей степени; или примените алгоритм Евклида: делите с остатком, пока остаток не станет 0.

Можно ли найти НОК через НОД?

Да: НОК(a, b) = a · b / НОД(a, b). Например, НОК(12, 18) = 12 · 18 / 6 = 36.

Что значит, если НОД равен 1?

Числа называются взаимно простыми — у них нет общих делителей. Тогда НОК равен их произведению: НОК(7, 9) = 63.

a	b	EKUB	EKUK
4	6	2	12
6	8	2	24
8	12	4	24
9	12	3	36
10	15	5	30
12	18	6	36
14	21	7	42
15	20	5	60
16	24	8	48
18	24	6	72
20	30	10	60
24	36	12	72
25	35	5	175
27	36	9	108
30	45	15	90
36	48	12	144
40	60	20	120
48	72	24	144

a	b	EKUB	EKUK
4	6	2	12
6	8	2	24
8	12	4	24
9	12	3	36
10	15	5	30
12	18	6	36
14	21	7	42
15	20	5	60
16	24	8	48
18	24	6	72
20	30	10	60
24	36	12	72
25	35	5	175
27	36	9	108
30	45	15	90
36	48	12	144
40	60	20	120
48	72	24	144

a	b	EKUB	EKUK
4	6	2	12
6	8	2	24
8	12	4	24
9	12	3	36
10	15	5	30
12	18	6	36
14	21	7	42
15	20	5	60
16	24	8	48
18	24	6	72
20	30	10	60
24	36	12	72
25	35	5	175
27	36	9	108
30	45	15	90
36	48	12	144
40	60	20	120
48	72	24	144