Наибольший общий делитель (GCF) - это наибольшее число, на которое можно разделить два или более числа. Это, не оставляя следов.
То есть наибольший общий делитель или ОКФ - это наибольшее число, на которое можно разделить набор чисел, в результате чего получится целое число.
Делитель можно формально определить как число, которое содержится в другом ровно n раз.
Следует отметить, что числа, по которым вычисляется GCF, должны быть ненулевыми.
Чтобы лучше это объяснить, давайте рассмотрим пример. Предположим, у нас есть 35 и 15. Таким образом, мы наблюдаем, каковы делители каждого из них:
- Делители 35 → 35,7,5,1
- Делители 15 → 15,5,3,1
Следовательно, наибольший общий делитель 35 и 15 равен 5.
Стоит отметить, что если общие делители двух чисел равны 1 и -1, они называются «простыми по отношению друг к другу».
Методы вычисления наибольшего общего делителя
Мы можем выделить следующие три метода вычисления наибольшего общего делителя:
- Разложение на основной коэффициент: Числа раскладываются на простые числа. Затем, чтобы вычислить GCF, мы возьмем обычные числа в наименьшей степени. Например, предположим, что у нас есть 216 и 156:
216/2=108
108/2=54
54/2=27
27/3=9
9/3=3
3/3=1
216=(3^3)*(2^3)
156/2=78
78/2=39
39/3=13
13/13=1
156=13*3*(2^2)
Следовательно, наибольший общий делитель между обоими числами будет: (2 2) * 3 = 12
Теперь предположим, что у нас есть три элемента: 315, 441 и 819.
315= (3^2)*7*5
441= (3^2)*(7^2)
819= (3^2)*7*13
Затем, после их разделения и взятия каждого делителя с наименьшей степенью, результат будет следующим:
ОКФ = (3 2) * 7 = 63
- Алгоритм Евклида: При делении к Заходи б, получается частное c и р. Итак, наибольший общий делитель к Y б такой же как б Y р. Это, учитывая следующее: а = bc + r. Чтобы лучше понять это, давайте применим этот метод к примеру, показанному ранее с 216 и 156.
216/156 = 1 с остатком 60
теперь делим 156/60 = 2 на остаток 36
Снова делим 60/36 = 1 с остатком 24
Еще раз делим 36/24 = 1 с остатком 12.
И, наконец, делим 24/12 = 2 с остатком 0
Следовательно, наибольший общий делитель равен 12. Как мы видим, мы должны делить до тех пор, пока остаток не будет равен 0, а последним делителем будет GCF.
- На основе наименьшего общего кратного: Числа умножаются, а результат делится на их наименьшее общее кратное (НОК).
Мы должны помнить, что наименьшее общее кратное (НОК) - это наименьшее число, которое удовлетворяет условию кратности всех элементов набора чисел.
То есть, возвращаясь к тому же примеру, мы можем выполнить разложение следующим образом:
216 = (3 3) * (2 3) и 156 = 13 * 3 * (2 2) 204 = 3 * (2 2) * 17 168 = 3 * (2 3) * 7
Наименьшее общее кратное будет: (3 3) * (2 3) * 13 * 17 * 7 = 334,152
Итак: НОД = 216 * 156 / 2,808 = 12
Стоит отметить, что этот метод работает только для двух чисел.