Как да намерите най-голям общ делител (ГРУ)

Да вземем два метода за намиране на най-голям общ делител.

Намирането на начин за факторинг

Първият начин се състои в намирането на най-големия общ делител на номерата на данни чрез разлагане на основните фактори.

За да намерите НОД на няколко номера, достатъчно, за да ги пуснат в прости числа и да се размножават помежду си тези, които са общи за всички тези номера.

Пример 1. Намираме GCD (84, 90).

Ние се разлага на броя 84 и 90 в основните фактори:

Така че, ние сме подчертавали всички общи простите делители, остава да ги умножи заедно: 1 · 2 · 3 = 6.

По този начин, GCD (84, 90) = 6.

Пример 2. Да се ​​определи ГРУ (15, 28).

Спред 15 и 28 в основните фактори:

Числата 15 и 28 са сравнително премиер, тъй като най-голямото им общ делител - единица.

алгоритъм на Евклид

Вторият метод (в противен случай той се нарича метод Евклид) се състои в намирането на GCD чрез последователно разделяне.

На първо място, ние считаме този метод, които се прилагат само два до цифрите, а след това ще разберем как да го прилага по отношение на три или повече числа.

Ако по-голямата от двете числа е разделена на данни минимални, броят на които е по-малък и най-голямото им общ делител.

Пример 1: Вземете две числа 27 и 9. От 27, разделени на 9 и 9 се дели на 9, а след 9 е общ делител на числата 27 и 9. Тази разделител е в същото време и най-великият, защото 9 не могат да споделят всякакви число по-голямо от 9. Следователно, GCD (27, 9) = 9.

В други случаи, за да се намери най-голям общ делител на две числа, като се използва следната процедура:

1. От две числа по-голям брой данни е разделен на минимален.
2. След това, по-малък брой се разделя на остатъка в резултат от разделяне на по-голям брой по-малко.
3. Освен това, първият Остатъкът е разделен на втория остатък, който беше от по-малък брой от участък за първи остатък.
4. Вторият Остатъкът се разделя на три, които са получени от първата разделянето на втория остатък и така нататък. D.
5. Така участък продължава толкова дълго, колкото баланс не се получава нула. Последно разделител да бъде само най-голям общ делител.

Пример 2. Да се ​​намери най-голям общ делител на 140 и 96:

1) 140. 96 = 1 (44 остатък)

2) 96. 44 = 2 (остатък 8)

3) 44. 8 = 5 (остатък 4)

Последно делител е 4 - което означава, че GCD (140, 96) = 4.

Последователно дивизия също може да записва колона:

За да намерите най-голям общ делител на три или повече от тези номера, ние използваме следната процедура:

1. На първо място, ние откриваме най-голям общ делител на всеки две числа от няколко данни.
2. След това, ние намерите НОД намери разделител и на една трета от броя.
3. След това ние откриваме последната поява на NOD четвърти разделител и определен брой и така нататък.

Пример 3. Ние откриваме най-голям общ делител на 140, 96 и 48. номера GCD 140 и 96, ние вече открити в предишния пример (броят 4). Остава да се намери най-голям общ делител на 4 и една трета от този брой - 48:

48, разделена на четири без остатък. По този начин, GCD (140, 96, 48) = 4.