Question

Найдите остаток от деления 3^2020 на 5. Пожалуйста!

Answer 1

Ответ:

1

Объяснение:

Найдём функцию Эйлера от числа 5. Это количество чисел, меньших 5 и взаимно простых с ним, то есть не имеющих с 5 общих делителей. Такими числами являются 1, 2, 3, 4, поскольку они не делятся на 5. Тогда функция Эйлера φ(5) = 4 (к тому же функция Эйлера простого числа, каким является 5, представляет собой результат вычитания единицы из этого числа, то есть 5 - 1 = 4, как у нас и получилось).

Так как 3 и 5 — взаимно простые числа, то $3^{4}$ сравнимо с 1 по модулю 5.

2020 = 5 * 404

Тогда $3^{2020}$ можно записать в виде $(3^{5}) ^{404}$

Поскольку мы выяснили, что $3^{4}$ сравнимо с 1 по модулю 5, то $(3^{5}) ^{404}$ также сравнимо с 1 по модулю 5. То есть остаток равен 1.

Answer 2

Для того чтобы найти остаток от деления $3^{2020}$ на 5, давайте воспользуемся малой теоремой Ферма.

Малая теорема Ферма говорит, что если $p$ - простое число, то для любого целого числа $a$, не делящегося на $p$, справедливо:

$a^{p-1} \equiv 1 \mod p$

В данном случае, $p = 5$, поэтому:

$3^4 \equiv 1 \mod 5$

Теперь, чтобы найти остаток от деления $3^{2020}$ на 5, давайте разобьем показатель степени:

$2020 = 4 \cdot 505$

Используя свойство остатков от деления, мы можем записать:

$3^{2020} = (3^4)^{505}$

Из малой теоремы Ферма мы знаем, что $3^4 \equiv 1 \mod 5$, поэтому:

$(3^4)^{505} \equiv 1^{505} \equiv 1 \mod 5$

Итак, остаток от деления $3^{2020}$ на 5 равен 1.