Как найти наибольший общий делитель (НОД) двух целых чисел

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).