Деление с остатком

[Гость]

Помогите решить задачу: найти остаток от деления 4^13/7 (4 в 13 степени /7) Просьба объяснить решение

[Andy]

Имеем [tex]4^{13}=2^{26},[/tex]
[tex]2^1\equiv{2}~(mod{7}),[/tex]
[tex]2^2\equiv{4}~(mod{7}),[/tex]
[tex]2^3\equiv{1}~(mod{7}),[/tex]
[tex]2^4\equiv{2}~(mod{7}),[/tex]
[tex]2^5\equiv{4}~(mod{7}),[/tex]
[tex]...[/tex]
Остатки повторяются с периодом, равным [tex]3.[/tex]
[tex]26=3\cdot{8}+2,[/tex] поэтому [tex]4^{13}\equiv{4}~(mod{7}).[/tex]
Но [tex]4=7\cdot{0}+4,[/tex] поэтому искомый остаток равен [tex]4.[/tex]
Проверка на калькуляторе даёт [tex]4^{13}=67108864=7\cdot 9586980+4,[/tex] как и должно быть.