Question

Найдите остаток при делении на 25 значения выражения: 6^2020+4^2020​

Answer 1

Ответ:

2

Пошаговое объяснение:

$\displaystyle 6^{2020} + 4^{2020} \ mod \ 25 \equiv 6^{2020} \ mod \ 25 + 4^{2020} \ mod \ 25$

1) $6^{2020} \ mod \ 25$

Так как НОД(6, 25) = 1, то выполняется теорема Эйлера:

$\displaystyle 6^{\phi(25)} \equiv 1 \ mod\ 25, \ \phi(25) = \phi(5^2) = [\phi(p^n) = p^n - p^{n-1}] = 25 - 5 = 20\\6^{20} \equiv 1 \ mod \ 25$

Тогда:

$6^{2020} \ mod \ 25 \equiv 6^{20*(101)} \ mod \ 25 \equiv 1^{101} \ mod \ 25 \equiv 1 \ mod \ 25$

2) $4^{2020} \ mod \ 25$

Так как НОД(4, 25) = 1, то выполняется теорема Эйлера:

$\displaystyle 4^{\phi(25)} \equiv 1 \ mod\ 25 \\4^{20} \equiv 1 \ mod \ 25$

Тогда:

$4^{2020} \ mod \ 25 \equiv 4^{20*(101)} \ mod \ 25 \equiv 1^{101} \ mod \ 25 \equiv 1 \ mod \ 25$

3)

В итоге:

$\displaystyle 6^{2020} + 4^{2020} \ mod \ 25 \equiv 6^{2020} \ mod \ 25 + 4^{2020} \ mod \ 25 \equiv 1 \ mod \ 25 + 1 \ mod \ 25 \equiv 2 \ mod \ 25$