С помощью алгоритма Евклида найдите НОД чисел:

Question

Реши задание на изображении

Расшифровка фото нейросетью:
№3
Найдите неполное частное $q$ и остаток $r$ при делении числа $a$ на число $b$. Запишите результат в виде $a=bq+r$, $0\le r<|b|$.
а) $a=327$, $b=15$
б) $a=-45$, $b=7$

№4
С помощью алгоритма Евклида найдите НОД чисел:
а) 391 и 867;
б) 143 и 247.

№5
Выполните действия по указанному модулю:
а) $17+25\pmod{7}$;
б) $14\cdot23\pmod{5}$.

№6
Докажите, что для любого целого числа $a$:
а) выражение $a^3-a$ делится на 3;
б) выражение $a^3+5a$ делится на 3.

Answer

На фото четыре задания — №3–№6. Ниже решения всех.

Кратко

№3: а) $q=21,\ r=12$; б) $q=-7,\ r=4$.

№4: а) НОД $=17$; б) НОД $=13$.

№5: а) $0$; б) $2$.

№6: оба выражения делятся на $3$ — доказательства ниже.

Подробно

№3

При делении с остатком должно выполняться $0\le r<|b|$.

а) $a=327,\ b=15$:
$$
327=15\cdot21+12,
$$
поэтому
$$
q=21,\quad r=12.
$$

б) $a=-45,\ b=7$:
$$
-45=7\cdot(-7)+4.
$$
Значит,
$$
q=-7,\quad r=4.
$$
Проверка: $7\cdot(-7)+4=-49+4=-45$. Остаток $4$ неотрицателен и меньше $7$. Если взять $q=-6$, остаток был бы $-3$, а это запрещено.

№4

Алгоритм Евклида: делим с остатком, затем заменяем пару $(a,b)$ на $(b,r)$. Когда остаток станет $0$, НОД — последний ненулевой остаток.

а)
$$
867=2\cdot391+85,\quad 391=4\cdot85+51,
$$
$$
85=1\cdot51+34,\quad 51=1\cdot34+17,\quad 34=2\cdot17+0.
$$
Последний ненулевой остаток равен $17$, значит
$$
\text{НОД}(391,867)=17.
$$

б)
$$
247=1\cdot143+104,\quad 143=1\cdot104+39,
$$
$$
104=2\cdot39+26,\quad 39=1\cdot26+13,\quad 26=2\cdot13+0.
$$
Последний ненулевой остаток равен $13$, поэтому
$$
\text{НОД}(143,247)=13.
$$

№5

Работаем по модулю: заменяем число его остатком при делении на модуль.

а)
$$
17\equiv3\pmod{7},\quad 25\equiv4\pmod{7},
$$
$$
17+25\equiv3+4=7\equiv0\pmod{7}.
$$
Ответ: $0$.

б)
$$
14\equiv4\pmod{5},\quad 23\equiv3\pmod{5},
$$
$$
14\cdot23\equiv4\cdot3=12\equiv2\pmod{5}.
$$
Ответ: $2$.

№6

а) Разложим выражение:
$$
a^3-a=a(a^2-1)=a(a-1)(a+1)=(a-1)a(a+1).
$$
Это произведение трёх последовательных целых чисел. Среди любых трёх подряд идущих целых чисел одно обязательно делится на $3$, поэтому всё произведение делится на $3$.

б) Используем пункт а):
$$
a^3+5a=(a^3-a)+6a.
$$
По пункту а) выражение $a^3-a$ делится на $3$. Кроме того, $6a$ тоже делится на $3$. Значит, их сумма
$$
a^3+5a
$$
делится на $3$ для любого целого $a$.

Что запомнить

Остаток при делении должен быть неотрицательным.

В алгоритме Евклида НОД — последний ненулевой остаток.

В сравнениях по модулю можно сначала заменить числа остатками.

Для доказательства делимости часто помогает разложение на последовательные множители.