Зміст

• кроки
• Метод 1 з 2: Алгоритм подільника
• Метод 2 з 2: Прості множники
• Поради

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

кроки

Метод 1 з 2: Алгоритм подільника

1. 1 Опустіть будь-які знаки мінус.
2. 2 Вивчіть термінологію: при розподілі 32 на 5,
   • 32 - ділене
   • 5 - дільник
   • 6 - приватна
   • 2 - залишок
3. 3 Визначте більше з чисел. Воно буде діленим, а менша кількість - дільником.
4. 4 Запишіть такий алгоритм: (Ділене) = (дільник) * (приватне) + (залишок)
5. 5 Поставте більше число на місце ділимо, а менша - на місце подільника.
6. 6 Знайдіть, скільки разів більша кількість ділиться на меншу, і запишіть результат замість приватного.
7. 7 Знайдіть залишок і впишіть його в відповідну позицію в алгоритмі.
8. 8 Запишіть алгоритм знову, але (A) запишіть попередній дільник як нове ділене, а (B) попередній залишок як новий дільник.
9. 9 Повторюйте попередній крок до тих пір, поки залишок не дорівнює 0.
10. 10 Останній дільник і буде найбільшим загальним дільником (НСД).
11. 11 Наприклад, знайдемо НСД для 108 і 30:
12. 12 Зверніть увагу, як числа 30 і 18 з першого рядка утворюють другий рядок. Потім 18 і 12 утворюють третій рядок, а 12 і 6 утворюють четвертий рядок. Кратні 3, 1, 1 і 2 цієї статті не використовуються. Вони являють собою число раз, які ділене ділиться на дільник, і тому є унікальними для кожного рядка.

Метод 2 з 2: Прості множники

1. 1 Опустіть будь-які знаки мінус.
2. 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
3. 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
4. 4 Перемножте загальні прості множники.
   • Для 24 і 18 перемножте 2 і 3 і отримаєте 6. 6 - найбільший спільний дільник 24 і 18.
   • Для 50 і 35 нічого перемножать. 5 - єдиний загальний простий множник, він і є НОДом.
5. 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).