Докажи, что числа 945 и 544 взаимно простые

Чтобы доказать, что числа 945 и 544 взаимно простые, необходимо показать, что их наибольший общий делитель (НОД) равен 1.

Можно использовать метод деления с остатком, который основан на алгоритме Евклида. Этот метод позволяет найти НОД двух чисел.

1. Начнем с деления большего числа на меньшее: 945 делим на 544: \[ 945 \div 544 = 1 \quad (целая часть) \] Остаток: \[ 945 - 544 \cdot 1 = 401 \]

2. Теперь берем 544 и делим его на остаток 401: \[ 544 \div 401 = 1 \] Остаток: \[ 544 - 401 \cdot 1 = 143 \]

3. Далее, делим 401 на 143: \[ 401 \div 143 = 2 \] Остаток: \[ 401 - 143 \cdot 2 = 115 \]

4. Теперь делим 143 на 115: \[ 143 \div 115 = 1 \] Остаток: \[ 143 - 115 \cdot 1 = 28 \]

5. Далее, делим 115 на 28: \[ 115 \div 28 = 4 \] Остаток: \[ 115 - 28 \cdot 4 = 3 \]

6. Продолжаем деление: 28 на 3: \[ 28 \div 3 = 9 \] Остаток: \[ 28 - 3 \cdot 9 = 1 \]

7. Наконец, 3 на 1: \[ 3 \div 1 = 3 \] Остаток: \[ 3 - 1 \cdot 3 = 0 \]

Когда мы дошли до остатка 0, значит, последний ненулевой остаток — это 1.

Поскольку НОД(945, 544) = 1, утверждаем, что числа 945 и 544 взаимно простые.