Question

Найти остаток от деления $204^{102}$ на 10403

Answer 1

Ответ:

5357

Объяснение:

Изящного решения не получилось, но кое-какие соображения есть. Заметим, что

          10403=10300+103=103(100+1)=103·101=(102+1)·(102-1)=102²-1.

Поскольку

$204^{102}=102^{102}\cdot 2^{102}=(102^{102}-1)\cdot 2^{102}+2^{102}=\left((102^{2})^{51}-1\right)\cdot 2^{102}+2^{102}=$

          $=(102^{2}-1)\left((102^2)^{50}+(102^2)^{49}+\ldots +102^2+1\right)\cdot 2^{102}+2^{102},$

остаток от деления $204^{102}$ на 10403 совпадает с остатком от деления

$2^{102}$ на 10403.

                                  $2^{102}=2^{17\cdot 6}=(2^{17})^6=131072^6;$

                                     $131072=10403\cdot 12+6236,$

поэтому остается найти остаток от деления $6236^6$ на 10403.

                           $6236^2=38887696=10403\cdot 3738+1282,$

поэтому остается найти остаток от деления 1282³ на 10403.

                        $1282^3=2106997768=10403\cdot 202537+5357,$

поэтому ответом в задаче (если я не ошибся) служит число 5357.