ГДЗ по Математике 6 Класс Вариант 3 Номер 23 Мерзляк, Полонский — Подробные Ответы

Докажите, что числа 715 и 567 — взаимно простые.

Кратко—через алгоритм Евклида.

$715=567\cdot1+148$ (потому что $715-567=148$).

$567=148\cdot3+123$ (потому что $148\cdot3=444,\;567-444=123$).

$148=123\cdot1+25$ (148−123=25).

$123=25\cdot4+23$ (25·4=100, 123−100=23).

$25=23\cdot1+2$ (25−23=2).

$23=2\cdot11+1$ (2·11=22, 23−22=1).

$2=1\cdot2+0$.

Последний ненулевой остаток — $1$. Значит $\gcd(715,567)=1$, то есть числа взаимно просты.

Нужно доказать:
$715$ и $567$ — взаимно простые, то есть их наибольший общий делитель (НОД) равен $1$.

Метод: алгоритм Евклида

Алгоритм Евклида основан на том, что

$$\gcd(a,b) = \gcd(b, a \bmod b)$$

и повторении этой операции, пока остаток не станет равен нулю. Последний ненулевой остаток и есть НОД.

Шаг 1:

$$715 = 567 \cdot 1 + 148$$

Тут мы делим 715 на 567, берём целую часть $1$, остаток — $148$.
Значит

$$\gcd(715, 567) = \gcd(567, 148)$$

Шаг 2:

$$567 = 148 \cdot 3 + 123$$

$148 \cdot 3 = 444$, остаток $567 — 444 = 123$.
Теперь

$$\gcd(567, 148) = \gcd(148, 123)$$

Шаг 3:

$$148 = 123 \cdot 1 + 25$$

$123 \cdot 1 = 123$, остаток $148 — 123 = 25$.

$$\gcd(148, 123) = \gcd(123, 25)$$

Шаг 4:

$$123 = 25 \cdot 4 + 23$$

$25 \cdot 4 = 100$, остаток $123 — 100 = 23$.

$$\gcd(123, 25) = \gcd(25, 23)$$

Шаг 5:

$$25 = 23 \cdot 1 + 2$$

$23 \cdot 1 = 23$, остаток $25 — 23 = 2$.

$$\gcd(25, 23) = \gcd(23, 2)$$

Шаг 6:

$$23 = 2 \cdot 11 + 1$$

$2 \cdot 11 = 22$, остаток $23 — 22 = 1$.

$$\gcd(23, 2) = \gcd(2, 1)$$

Шаг 7:

$$2 = 1 \cdot 2 + 0$$

Остаток 0, значит последний ненулевой остаток — 1.

Вывод:

$$\gcd(715, 567) = 1$$

Следовательно, числа взаимно простые.