Как вычислить наибольший общий делитель?

Подробнее о наибольшем общем делителе (иногда также называемом наибольшим общим делителем) : Наибольший общий делитель (НОД) между двумя положительными целыми числами \(n_1\) и \(n_2\) - это наибольшее целое число, которое делит как \(n_1\), так и \(n_2\). Обычно его легко найти путем проверки (это систематический перебор большого количества чисел, пока мы не найдем его), но это верно только для небольших чисел. Вычисление GCD для больших чисел путем проверки может быть утомительным или сложным.

К счастью, существует систематический и простой (кашель, кашель) способ вычислить НОД для двух чисел. Метод выглядит так

• Вычислить разложение на простые числа из \(n_1\) и \(n_2\). Символически у нас будет что-то вроде этого: \[n_1 = p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_n^{\alpha_n}\] \[n_2 = q_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_m^{\alpha_m}\]
• Найдите список общих простых чисел в соответствующем разложении на простые числа. Если общих простых чисел нет, то СТОП, вы обнаружили, что GCD = 1. В противном случае пусть \(\{r_1, ..., r_k \}\) будет списком общих простых чисел \(k\) и пусть \(\alpha_{i_l}, \beta_{i_l}\) для \(l=1,2,..,k\) соответствующие показатели степени, найденные в простом разложении \(n_1\) и \(n_2\) для соответствующих общих чисел простые числа.
  
  
• НОД вычисляется как: \[GCD = r_1^{\min\{\alpha_{i_1}, \beta_{i_1}\}} \cdot r_2^{ \min\{\alpha_{i_2}, \beta_{i_2}\}} \cdots r_k^{\min\{\alpha_{i_k}, \beta_{i_k}\}} \]

Вышеупомянутый метод выглядит слишком сложным ?? Не совсем. Давайте посмотрим на пример: давайте вычислим НОД для \(n_1 = 165\) и \(n_2 = 1575\). Давайте найдем разложение на простые числа каждого из этих чисел (вы можете использовать наш калькулятор разложения на простые числа)

\[165 = 3 \cdot 5 \cdot 11\] \[1575 = 3^2 \cdot 5^2 \cdot 7\]

Из вышесказанного: какие простые числа имеют эти два числа общего? Как мы видим, общие простые числа - это 3 и 5. Глядя на показатели этих общих простых чисел в каждом из чисел, мы ищем минимум между ними. В этом случае минимальный показатель для 3 равен 1, а минимальный показатель для 5 также равен 1. Следовательно

\[GCD = 3^1 \cdot 5^1 = 3 \cdot 5 = 15 \]

Помимо калькулятора GDC, вы можете выбрать один из наших калькуляторы и решатели алгебры .