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$

Answer 2

Чтобы найти остаток от деления значения выражения $6^{2020}+4^{2020}$ на 25, мы можем воспользоваться малой теоремой Ферма. Эта теорема утверждает, что если $p$ - простое число, а $a$ не делится на $p$, то $a^{p-1}$ делится на $p$, то есть $a^{p-1} \equiv 1 \pmod{p}$.

В данном случае $p = 25$, и $6$ и $4$ не делятся на $25$, поэтому мы можем воспользоваться теоремой Ферма.

Сначала найдем остаток от деления $6^{2020}$ на $25$:

$6^{2020} \equiv 6^{20 \cdot 101} \equiv (6^{20})^{101} \pmod{25}$.

Теперь найдем остаток от деления $4^{2020}$ на $25$:

$4^{2020} \equiv 4^{20 \cdot 101} \equiv (4^{20})^{101} \pmod{25}$.

Теперь вычислим остатки от деления $6^{20}$ и $4^{20}$ на $25$:

$6^{20} \equiv (6^{4})^5 \equiv (1296)^5 \equiv 21^5 \pmod{25}$.

$4^{20} \equiv (4^{4})^5 \equiv (256)^5 \equiv 6^5 \pmod{25}$.

Теперь вычислим остатки от деления $21^5$ и $6^5$ на $25$:

$21^5 = 47521821$, и $47521821 \equiv 21 \pmod{25}$.

$6^5 = 7776$, и $7776 \equiv 1 \pmod{25}$.

Итак, мы нашли остатки от деления $6^{20}$ и $4^{20}$ на $25$, которые равны $21$ и $1$ соответственно. Теперь мы можем вычислить остаток от деления исходного выражения:

$$6^{2020} + 4^{2020} \equiv 21^{101} + 1^{101} \pmod{25}$$

Теперь сложим остатки:

$$21^{101} + 1^{101} \equiv 21 + 1 \equiv 22 \pmod{25}$$

Итак, остаток при делении $6^{2020}+4^{2020}$ на 25 равен 22.