В математике пятого-шестого класса есть тема, которая вызывает затруднения даже у отличников. Это нахождение НОД нескольких чисел.
Сегодня я расскажу вам, что такое наибольший общий делитель, покажу три способа как быстро и эффективно его находить, даже для очень больших чисел, а также научу пользоваться «Алгоритмом Евклида«, способом находить наибольший общий делитель, изобретённый в третьем веке до нашей эры, но актуальный и по сей день.
Для начала давайте вспомним (или узнаем если вы не знали), что такое НОД.
НОД — это наибольший общий делитель. Это целое число, на которое делятся заданные числа без остатка и такое число, самое большое из всех делителей.
Давайте я поясню вам на примере. Допустим даны числа 24 и 36. Оба они делятся без остатка на два (будет 12 и 18, соответственно), так же 24 и 36 делятся и на три и на четыре. Но самым большим числом на которое делятся эти числа, будет 12. 36 еще можно разделить на восемнадцать, а вот 24 уже нельзя. Следовательно, наибольшим общим будет именно 12.
Так, с формулировками разобрались. Но как же находить этот НОД?
Существует несколько способов. Давайте начнем с самого простого для понимания и самого сложного по реализации. Этот способ предполагает выписывание общих делителей для обеих чисел, а затем визуального определения, какое из них общее будет больше. Давайте проделаем это для тех же чисел, которые мы привели в примере.
- Делители числа 24: 1, 2, 3, 4, 6, 8, 12, 24.
- Делители числа 36: 1, 2, 3, 4, 6, 9, 12, 18, 36.
В примере выше мы выписали все делители чисел 24 им 36, остается найти наибольший общий. Как видим это число 12. Следовательно наибольшим общим делителем для чисел 24 и 36, будет число 12.
Теперь способ попроще. Разложим число 24 на простые множители. Напомню, простыми называются такие множители, которые уже не на что не делятся.
24/2=12 12/2 = 6 6/2= 3 3/3 = 1
Следовательно 24 это 2*2*2*3
Теперь тоже проделаем для 36.
36/2=18 18/2=9 9/3=3 3/3=1
Получается, что 36 это 2*2*3*3
Теперь подчеркнем одинаковые множители для 24 и для 36
24 это 2*2*2*3 для 36 это 2*2*3*3 как видим общие тут две двойки и одна тройка. 2*2*3
Теперь перемножим их 2*2*3=12. Ответ 12 и будет НОД для чисел 24 и 36.
Но есть и третий способ! Он максимально простой в выполнении. Следите за руками😂
Алгоритмом Евклида
- 24 и 36 — пишем числа рядом, для которых ищем НОД
- 24 — переписываем меньшее, а рядом пишем большее минус меньшее 36-24=12, получаем
- 24 и 12 — повторяем все еще раз
- 12 — переписываем меньшее, а рядом пишем большее минус меньшее 24-12=12
12 и 12 — как только числа станут равны это и есть НОД!
Давайте проделаем еще раз, но для чисел 96 и 64
- 96 и 64
- 64 и 96-64=32
- 64 и 32
- 32 и 64-32=32
- 32=32 = НОД
Как видите, существует несколько простых способов нахождения Наибольшего Общего Делителя для чисел. Как по мне, так проще второй способ. Он одинаково удобен и для коротких и для длинных чисел. А вот способ, называемый Евклидовым алгоритмом, как мне кажется, лучше применять для небольших двух-трехзначных чисел.