НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ
Рассмотрим числа 12 и 54:
Делители числа 12: 1, 2, 3, 4, 6, 12.
Делители числа 54: 1, 2, 3, 6, 9, 18, 27, 54.
Заметим, что у 12 и 54 есть одинаковые делители: 1, 2, 3, 6.
Их называют общими делителями для чисел 12 и 54, то есть оба числа: и 12 и 54 делятся на 1, 2, 3, 6.
Наибольшим общим делителем натуральных чисел а и b называют наибольшее натуральное число, на которое делится нацело и a, и b.
Обозначается НОД(a,b)=c, то есть a ⋮ c и b ⋮ c.
Например: найдем НОД(45, 60)
делители числа 45: 1, 3, 5, 9, 15, 45.
делители числа 60: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60.
общие делители для 45 и 60: 1, 3, 5, 15.
Наибольшим среди них будет 15, то есть: НОД(45, 60)=15
Замечание: Наибольший общий делитель чисел не может быть больше любого из них, то есть НОД(a,b)=c, значит a ≥ c и b ≥ c.
Например:
НОД(58,32) не может равняться 34, потому что 32 < 34 и значит 32 не может делиться на 34.
Алгоритм нахождения наибольшего общего делителя:
1. Разложить числа на простые множители.
2. Обвести одинаковые простые множители.
3. Умножить обведенные простые множители из разложения одного из чисел.
Например: НОД(18, 24)
18
9
3
1
|
2
3
3
|
24
12
6
3
1
|
2
2
2
3
|
получаем НОД(18, 24)=2∙3=6
Замечание: Если одно из двух чисел нацело делится на другое, то их наибольший общий делитель равен меньшему из них.
Например: НОД(8, 72)=8, потому что 72 ⋮ 8
НОД(444, 111)=111, потому что 444 ⋮ 111
Взаимно простые числа – это числа, не имеющие общих простых делителей.
Например: 56 и 45 – взаимно простые числа, потому что
делители числа 56: 1, 2, 4, 7, 8, 14, 28, 56
делители числа 45: 1, 3, 5, 9, 15, 45
общий делитель – 1, то есть: общих простых делителей нет.
Утверждение: Наибольший общий делитель взаимно простых чисел равен 1. Если a и b – взаимно простые числа, то НОД(a, b)= 1
Например: НОД(7, 50)=1, НОД(11, 19)=1, НОД(40, 33)=1
Замечание 1: Любые два простых числа являются взаимно простыми и их НОД равно 1.
Например: НОД(13, 17)=1, НОД(37, 59)=1, НОД(5, 29)=1
Замечание 2: Любые два последовательных числа в ряду натуральных чисел всегда являются взаимно простыми и их НОД равно 1.
Например: НОД(10, 11)=1, НОД(40, 41)=1, НОД(204, 205)=1
Достарыңызбен бөлісу: |
