Як знайти найбільший спільний дільник (нод) двох цілих чисел

Найбільший спільний дільник (НСД) двох цілих чисел - це найбільше ціле число, на яке ділиться кожне з цих чисел. Наприклад, НСД для 20 і 16 дорівнює 4 (як 16, так і 20 мають великі подільники, але вони не є загальними - наприклад, 8 дільник 16, але не дільник 20). Існує простий і системний метод для знаходження НСД, званий "алгоритм Евкліда". Ця стаття розповість вам, як знаходити найбільший спільний дільник двох цілих чисел.

кроки

Метод 1 з 2:

алгоритм подільника

1. Опустіть будь-які знаки мінус.

Зображення з назвою Find the Greatest Common Divisor of Two Integers Step 2

2. Вивчіть термінологію: при розподілі 32 на 5,

32 - ділене

5 - дільник

6 - приватна

2 - залишок

Зображення з назвою Find the Greatest Common Divisor of Two Integers Step 3

3. Визначте більше з чисел. Воно буде діленим, а менша кількість - дільником.

Зображення з назвою Find the Greatest Common Divisor of Two Integers Step 4

4. Запишіть такий алгоритм: (Ділене) = (дільник) * (приватне) + (залишок)

Зображення з назвою Find the Greatest Common Divisor of Two Integers Step 5

5. Поставте більше число на місце ділимо, а менша - на місце подільника.

Зображення з назвою Find the Greatest Common Divisor of Two Integers Step 6

6. Знайдіть, скільки разів більша кількість ділиться на меншу, і запишіть результат замість приватного.

Зображення з назвою Find the Greatest Common Divisor of Two Integers Step 7

7. Знайдіть залишок і впишіть його в відповідну позицію в алгоритмі.

Зображення з назвою Find the Greatest Common Divisor of Two Integers Step 8

8. Запишіть алгоритм знову, але (A) запишіть попередній дільник як нове ділене, а (B) попередній залишок як новий дільник.

Зображення з назвою Find the Greatest Common Divisor of Two Integers Step 9

9. Повторюйте попередній крок до тих пір, поки залишок не дорівнює 0.

Зображення з назвою Find the Greatest Common Divisor of Two Integers Step 10

10. Останній дільник і буде найбільшим загальним дільником (НСД).

Зображення з назвою Find the Greatest Common Divisor of Two Integers Step 11

11. Наприклад, знайдемо НСД для 108 і 30:

Зображення з назвою Find the Greatest Common Divisor of Two Integers Step 12

12. Зверніть увагу, як числа 30 і 18 з першого рядка утворюють другий рядок. Потім 18 і 12 утворюють третій рядок, а 12 і 6 утворюють четвертий рядок.Кратні 3, 1, 1 і 2 цієї статті не використовуються. Вони являють собою число раз, які ділене ділиться на дільник, і тому є унікальними для кожного рядка.

Метод 2 з 2:

прості множники

1. Опустіть будь-які знаки мінус.

Зображення з назвою Find the Greatest Common Divisor of Two Integers Step 14

2. Знайдіть прості множники чисел. Уявіть їх так, як показано на малюнку.

Наприклад, для 24 і 18:

24- 2 x 2 x 2 x 3

18- 2 x 3 x 3

Наприклад, для 50 і 35:

50 2 x 5 x 5

35- 5 x 7

Зображення з назвою Find the Greatest Common Divisor of Two Integers Step 15

3. Знайдіть загальні прості множники.

Наприклад, для 24 і 18:

24- 2 x 2 x 2 x 3

18- 2 x 3 x 3

Наприклад, для 50 і 35:

50 2 x 5 x 5

35- 5 x 7

Зображення з назвою Find the Greatest Common Divisor of Two Integers Step 16

4. Перемножте загальні прості множники.

Для 24 і 18 перемножте 2 і 3 і отримаєте 6. 6 - найбільший спільний дільник 24 і 18.

Для 50 і 35 нічого перемножать. 5 - єдиний загальний простий множник, він і є НОДом.

Зображення з назвою Find the Greatest Common Divisor of Two Integers Step 17

5. зроблено!

Поради

Один із способів записати це: <ділене>mod<дільник> = Остаток- НСД (a, b) = b, якщо mod b = 0, і НСД (a, b) = НСД (b, a mod b) в іншому випадку.
Як приклад знайдемо НСД (-77,91). По-перше, використовуйте 77 замість -77: НОД (-77,91) перетворюється в НОД (77,91). 77 менше 91, тому ми повинні поміняти їх місцями, але розглянемо те, як діє алгоритм, якщо ми не зробимо цього. При обчисленні 77 mod 91 ми отримаємо 77 (77 = 91 х 0 + 77). Так як це не нуль, розглядаємо ситуацію (b, a mod b), тобто НСД (77,91) = НСД (91,77). 91 mod 77 = 14 (14 є залишком). Це не нуль, тому НСД (91,77) стає НСД (77,14). 77 mod 14 = 7. Це не нуль, тому НСД (77,14) стає НОД (14,7). 14 mod 7 = 0 (так як 14/7 = 2 без залишку). Відповідь: НОД (-77,91) = 7.
Описаний метод дуже корисний при спрощення дробів. В описаному вище прикладі: -77/91 = -11/13, так як 7 є найбільшим спільним дільником -77 і 91.
Якщо а і b дорівнюють нулю, то будь-яке відмінне від нуля число є їх дільником, тому в цьому випадку НОД не існує (математики просто вважають, що найбільший спільний дільник 0 і 0 дорівнює 0).