Как доказать, что числа 945 и 572 взаимно простые?
Ответы
Сергей Громов
Для определения взаимной простоты чисел 945 и 572 необходимо найти их наибольший общий делитель (НОД). Если НОД равен 1, то числа являются взаимно простыми.
Существует несколько способов нахождения НОД. Один из них – разложение чисел на простые множители:
Разложим 945: 945 = 33 * 5 * 7
Разложим 572: 572 = 22 * 11 * 13
Теперь сравним полученные разложения. Видим, что у чисел нет общих простых множителей.
Другой способ – алгоритм Евклида:
945 = 1 * 572 + 373
572 = 1 * 373 + 199
373 = 1 * 199 + 174
199 = 1 * 174 + 25
174 = 6 * 25 + 24
25 = 1 * 24 + 1
24 = 24 * 1 + 0
Последний ненулевой остаток равен 1, следовательно, НОД(945; 572) = 1.
Поскольку наибольший общий делитель чисел 945 и 572 равен 1, то эти числа являются взаимно простыми.
Для определения взаимной простоты чисел 945 и 572 необходимо найти их наибольший общий делитель (НОД). Если НОД равен 1, то числа являются взаимно простыми.
Существует несколько способов нахождения НОД. Один из них – разложение чисел на простые множители:
Теперь сравним полученные разложения. Видим, что у чисел нет общих простых множителей.
Другой способ – алгоритм Евклида:
Последний ненулевой остаток равен 1, следовательно, НОД(945; 572) = 1.
Поскольку наибольший общий делитель чисел 945 и 572 равен 1, то эти числа являются взаимно простыми.