Найбільший загальний дільник (GCF) - це найбільше число, на яке можна розділити два чи більше числа. Це, не залишаючи залишку.
Тобто, найбільший загальний дільник або GCF - це найвища цифра, на яку можна розділити набір чисел, що призводить до цілого числа.
Дільник можна формально визначити як число, яке міститься в іншому рівно кількості n разів.
Слід зазначити, що цифри, за якими обчислюється коефіцієнт корисної дії, повинні бути ненульовими.
Щоб пояснити це краще, давайте розглянемо приклад. Припустимо, у нас є 35 і 15. Таким чином, ми спостерігаємо, що дільники кожного з них:
- Дільники 35 → 35,7,5,1
- Дільники 15 → 15,5,3,1
Тому найбільшим загальним коефіцієнтом 35 і 15 є 5.
Варто згадати, що якщо загальними дільниками двох чисел є лише 1 і -1, вони називаються "простими один до одного".
Методи обчислення найбільшого спільного дільника
Ми можемо розрізнити наступні три методи для обчислення найбільшого спільного дільника:
- Розкладання простого коефіцієнта: Числа розкладаються на прості числа. Потім для обчислення коефіцієнта корисного коефіцієнта беремо загальні числа, підняті до найменшої потужності. Наприклад, припустимо, що ми маємо 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
Тоді, після їх розподілу, взявши кожен дільник з найменшою потужністю, результат буде:
GCF = (3 2) * 7 = 63
- Алгоритм Евкліда: При поділі до Увійдіть b, отримується коефіцієнт c і a р. Отже, найбільший спільний дільник до Y b це те саме, що b Y р. Це, враховуючи наступне: a = 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.
- На основі найменш загального кратного: Числа множаться, а результат ділиться на найменше загальне кратне (LCM).
Потрібно пам’ятати, що найменше загальне кратне (LCM) - це найменша цифра, яка задовольняє умові кратності всіх елементів набору чисел.
Тобто, повертаючись до того самого прикладу, ми можемо розкласти наступним чином:
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
Отже: GCD = 216 * 156 / 2,808 = 12
Варто згадати, що цей метод працює лише для двох чисел.