Question

Помогите найти остаток от деления числа: 5^2013 на 13

Answer 1

Заметим, что 5^2 = 25 = 26 - 1 = 13*2 - 1

Тогда число 5^(2n) сравнимо по модулю 13 с числом (-1)^n (для доказательства достаточно раскрыть по биному (26 - 1)^n и заметить, что все слагаемые кроме (-1)^n делятся на 26)

Отсюда число 5^2012 = 26^1006 сравнимо по модулю 13 с числом (-1)^1006 = 1. А тогда число 5^2013 = 5 * 5^2012 при делении на 13 даёт остаток 5.

Answer 2

Для нахождения остатка от деления \(5^{2013}\) на 13, мы можем воспользоваться малой теоремой Ферма. Согласно этой теореме, если \(p\) — простое число, а \(a\) не делится на \(p\), то \(a^{p-1} \equiv 1 \pmod{p}\). Это можно записать как \(a^{p-1} \equiv 1 \mod p\).

В данном случае \(p = 13\), поэтому малая теорема Ферма говорит нам, что \(5^{12} \equiv 1 \mod 13\). Теперь мы можем использовать это для упрощения выражения \(5^{2013}\):

\[5^{2013} = (5^{12})^{167} \times 5^9.\]

Так как \(5^{12} \equiv 1 \mod 13\), мы можем заменить \(5^{12}\) на 1:

\[5^{2013} \equiv 1^{167} \times 5^9 \mod 13.\]

Теперь остается вычислить \(5^9\) и найти остаток от деления этого значения на 13. Можно пошагово вычислить степени:

\[5^2 \equiv 25 \equiv -1 \mod 13.\]

Теперь возводим в квадрат:

\[5^4 \equiv (-1)^2 \equiv 1 \mod 13.\]

Аналогично:

\[5^8 \equiv 1^2 \equiv 1 \mod 13.\]

Теперь умножаем на \(5\) и получаем:

\[5^9 \equiv 5 \mod 13.\]

Таким образом, остаток от деления \(5^{2013}\) на \(13\) равен \(5\).