Наибольший общий фактор (GCF)

Наибольший общий делитель (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

Стоит отметить, что этот метод работает только для двух чисел.