Наибольший общий делитель
Определение. Наибольшим общим делителем чисел a и b называется наибольшее число, на которое a и b делятся без остатка.
Чтобы хорошо понять это определение, подставим вместо переменных a и b любые два числа, например, вместо переменной a подставим 12, а вместо переменной b подставим 9. Теперь попробуем прочитать это определение.
Наибольшим общим делителем чисел 12 и 9 называется наибольшее число, на которое 12 и 9 делятся без остатка.
Из определения ясно, что речь идёт о общем делителе чисел 12 и 9, при этом, этот делитель является наибольшим из всех существующих делителей. Этот наибольший общий делитель (НОД) требуется найти.
Для нахождения наибольшего общего делителя двух чисел, используется два способа. Первый способ достаточно трудоёмкий, но зато позволяет полностью понять суть темы и прочувствовать весь ее смысл. Второй способ очень прост, и даёт возможность быстро найти НОД, но недостаток этого способа в том, что если часто пользоваться им, можно перестать понимать тему. Мы с вами рассмотрим оба способа. А какой применять на практике — выбирать вам.
Первый способ заключается в поиске всех возможных делителей двух чисел и в выборе наибольшего из них. Рассмотрим этот способ на следующем примере: найти наибольший общий делитель чисел 12 и 9.
Сначала ищем все возможные делители числа 12. Для этого, делим 12 на те числа, на которые 12 делится без остатка.
Проверим все числа от 1 до 12. Если число позволит разделить 12 без остатка, то мы будем выделять его красным цветом и в скобках пояснять, что к чему. Итак, начнём:
12: 1 = 12 (12 разделилось на 1 без остатка, значит 1 является делителем числа 12)
12: 2 = 6 (12 разделилось на 2 без остатка, значит 2 является делителем числа 12)
|
|
12: 3 = 4 (12 разделилось на 3 без остатка, значит 3 является делителем числа 12)
12: 4 = 3 (12 разделилось на 4 без остатка, значит 4 является делителем числа 12)
12: 5 = 2 (2 в остатке) (12 не разделилось на 5 без остатка, значит 5 не является делителем числа 12)
12: 6 = 2 (12 разделилось на 6 без остатка, значит 6 является делителем числа 12)
12: 7 = 1 (5 в остатке) (12 не разделилось на 7 без остатка, значит 7 не является делителем числа 12)
12: 8 = 1 (4 в остатке) (12 не разделилось на 8 без остатка, значит 8 не является делителем числа 12)
12: 9 = 1 (3 в остатке) (12 не разделилось на 9 без остатка, значит 9 не является делителем числа 12)
12: 10 = 1 (2 в остатке) (12 не разделилось на 10 без остатка, значит 10 не является делителем числа 12)
12: 11 = 1 (1 в остатке) (12 не разделилось на 11 без остатка, значит 11 не является делителем числа 12)
12: 12 = 1 (12 разделилось на 12 без остатка, значит 12 является делителем числа 12)
Теперь, найдём делители числа 9. Для этого, проверим все числа от 1 до 9
9: 1 = 9 (9 разделилось на 1 без остатка, значит 1 является делителем числа 9)
9: 2 = 4 (1 в остатке) (9 не разделилось на 2 без остатка, значит 2 не является делителем числа 9)
9: 3 = 3 (9 разделилось на 3 без остатка, значит 3 является делителем числа 9)
9: 5 = 1 (4 в остатке) (9 не разделилось на 3 без остатка, значит 3 не является делителем числа 9)
9: 6 = 1 (3 в остатке) (9 не разделилось на 6 без остатка, значит 6 не является делителем числа 9)
9: 7 = 1 (2 в остатке) (9 не разделилось на 7 без остатка, значит 7 не является делителем числа 9)
9: 8 = 1 (1 в остатке) (9 не разделилось на 8 без остатка, значит 8 не является делителем числа 9)
|
|
9: 9 = 1 (9 разделилось на 9 без остатка, значит 9 является делителем числа 9)
Теперь выпишем делители обоих чисел. Числа выделенные красным цветом и являются делителями. Их и выпишем:
Делители числа 12 это { 1 2 3 4 6 12 }
Делители числа 9 это { 1 3 9 }
Выписав делители, можно сразу определить, какой является самым наибольшим и общим. Согласно определению, наибольшим общим делителем чисел 12 и 9, является число, на которое 12 и 9 делятся без остатка. Наибольшим и общим делителем чисел 12 и 9 является число 3. Оно выделено синим цветом и подчёркнуто. И 12 и 9 делятся на 3 без остатка:
12: 3 = 4
9: 3 = 3
НОД (12 и 9) = 3
Второй способ нахождения НОД
Теперь рассмотрим второй способ нахождения наибольшего общего делителя. Суть данного способа в том, что числа, подлежащие поиску наибольшего общего делителя раскладывают на множители. Затем, из разложения множителей первого числа вычеркивают множители, которые не входят в разложение второго числа. Оставшиеся числа в первом разложении перемножают и получают НОД.
Например, найдём НОД для чисел 12 и 9 данным способом. В первую очередь, раскладываем на множители числа 12 и 9.
Разложим на множители число 12
Разложим на множители число 9
Получили два разложения:
2 × 2 × 3
3 × 3
Теперь из разложения первого числа вычеркнем множители, которые не входят в разложение второго числа. В разложение второго числа не входят две двойки. Их и вычеркнем из первого разложения:
2 × 2 × 3
Оставшаяся тройка является наибольшим общим делителем чисел 12 и 9:
12: 3 = 4
9: 3 = 3
НОД (12 и 9) = 3