Докажите что числа 644 и 495 взаимно простые

Чтобы доказать, что числа $644$ и $495$ являются взаимно простыми, необходимо подтвердить, что их наибольший общий делитель (НОД) равен $1$. Это можно сделать двумя способами: через разложение на простые множители или с помощью алгоритма Евклида. Способ 1: Разложение на простые множители Разложим каждое число на простые множители и проверим наличие общих делителей. Разложение числа 644:

1. Число четное: $644=2\cdot 322$ Еще раз делим на 2: $322=2\cdot 161$ Проверяем 161: на 3 не делится (сумма цифр $1+6+1=8$), на 5 не делится. Проверяем 7: $161=7\cdot 23$ Число 23 является простым.
   Итого: $644=2^2\cdot 7\cdot 23$

Разложение числа 495:

1. Оканчивается на 5: $495=5\cdot 99$ Число 99 делится на 9: $99=9\cdot 11=3^2\cdot 11$
   Итого: $495=3^2\cdot 5\cdot 11$

Сравнение множителей:

• Множители 644: $\{2,7,23\}$ Множители 495: $\{3,5,11\}$

Общих простых множителей нет, следовательно, $НОД(644,495)=1$. Способ 2: Алгоритм Евклида Этот метод основан на последовательном делении с остатком.

1. $644=495\cdot 1+149$ $495=149\cdot 3+48$ (так как $149\cdot 3=447$, остаток $495-447=48$) $149=48\cdot 3+5$ (так как $48\cdot 3=144$, остаток $149-144=5$) $48=5\cdot 9+3$ $5=3\cdot 1+2$ $3=2\cdot 1+1$ $2=1\cdot 2+0$

Последний ненулевой остаток равен 1. Вывод Поскольку наибольший общий делитель чисел $644$ и $495$ равен $1$, данные числа являются взаимно простыми по определению. Я могу также составить для вас таблицу простых чисел или продемонстрировать решение аналогичной задачи для других пар чисел. Хотите продолжить?