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

Найбільший спільний дільник (НСД) двох цілих чисел - це найбільше ціле число, на яке ділиться кожне з цих чисел. Наприклад, НОД для 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).