Сравнения. Остаток от деления и последняя цифра

[Ubermensch]

Найти остаток от деления $a$ на $b$ и последнюю цифру числа $a$
1)$a=178^{274}$, $b=22$
$178 \equiv 2(\mod 22)$
$178^{274} \equiv 2^{274} (\mod 22)$
$2^5=32\equiv 10 (\mod 22)$
$(2^5)^{54} \cdot 16 \equiv 10^{54} \cdot 16 (\mod 22)$
А дальше?

Какая основная мысль при решении таких задач? Делать эквивалентные замены, пока что?
Не понимаю, как применять теорию на практике.

[provincialka]

Может, малую теорему Ферма применить? Например, отдельно для деления на 11 (на 2 это число и так делится).

[Sonic86]

Разложите модуль $b$ на множители, ищите остатки от деления на каждый множитель с помощью МТФ, а потом двоичным возведением в квадрат, потом вернитесь к общему модулю с помощью китайской теоремы об остатках.

[Ubermensch]

А примитивные способы есть?
Дело в том, что КТ, МТФ мы проходили только на лекции, на практике еще нет. И по идее это мы должны сделать без теорем Эйлера, Ферма, китайской теоремы.

[provincialka]

Тогда просто найдите последовательность остатков. Если при делении на 22 остатки не будут повторятьсяслишком долго, рассмотрите деление на 11 и 2.

[vorvalm]

Ничего не надо.

$!78^{274}=2^{274}\cdot 89^{274}$

$89^{274-27\cdot {10}}=89^4\equiv 1\pmod {22}$

$10=\varphi(22)$

[Ubermensch]

Все еще буду благодарен, если кто-нибудь покажет и объяснит, как такое решать без всяких именных теорем.

[AV_77]

Ubermensch в сообщении #777588 писал(а):

Найти остаток от деления $a$ на $b$ и последнюю цифру числа $a$
1)$a=178^{274}$, $b=22$
$178 \equiv 2(\mod 22)$
$178^{274} \equiv 2^{274} (\mod 22)$
$2^5=32\equiv 10 (\mod 22)$

$2^6 \equiv 20 \equiv -2 \pmod{22}$
$2^{274} = 2^4 \cdot (2^6)^{45} \equiv 2^4 \cdot (-2)^{45} \equiv - 2^4 \cdot 2^3 \cdot (2^6)^7 \equiv -2^7 \cdot (-2)^7 = 2^{14} \pmod{22}$
Дальше справитесь?

[Ubermensch]

Нет.
Я хочу понять логику этих преобразований. То есть понять, к чему мы должны придти. Какая конечная цель наших преобразований.

[AV_77]

Ubermensch в сообщении #777627 писал(а):

То есть понять, к чему мы должны придти.

Прийти надо к тому, что требуется найти в задаче.

[nnosipov]

Ubermensch в сообщении #777593 писал(а):

А примитивные способы есть?

Есть: бинарный алгоритм возведения в степень по модулю.

[vorvalm]

Не понимаю, что тут непонятно.

$89^{274}\equiv 1\pmod {22}$

Остаток 1, последняя цифра 1.

[provincialka]

Самый тупой способ - возводить последовательно в степень. Получаем $-2,4,-8,16 \equiv -6, 12, -24\equiv -2$, дальше все повторяется.

[yk2ru]

Можно использовать $2^{11}\equiv 2\pmod {22}$.
Остаток 16 и последня цифра 4, так как $8^5$ оканчивается на 8 .

[Ubermensch]

vorvalm в сообщении #777604 писал(а):

Ничего не надо.

$!78^{274}=2^{274}\cdot 89^{274}$

$89^{274-27\cdot {10}}=89^4\equiv 1\pmod {22}$

$10=\varphi(22)$

что произошло во второй строчке? Не могу понять применения теоремы.