Question

Записать вместо точек наименьшее возможное положительное число 13^52=... (mod 17)

Answer 1

Числа равны по модулю 17, если их разность кратна 17.

$13^{52}=(13^2)^{26}=169^{26}\equiv(169-17\cdot10)^{26}=(-1)^{26}=1^{26}=1\pmod{17}$

Ответ: 1

Answer 2

Чтобы найти значение \(13^{52} \pmod{17}\), можно воспользоваться малой теоремой Ферма. Согласно этой теореме, если \(p\) — простое число, то для любого целого числа \(a\), не делящегося на \(p\), справедливо:

\[a^{p-1} \equiv 1 \pmod{p}\]

В данном случае \(p = 17\), поэтому \(13^{16} \equiv 1 \pmod{17}\). Теперь мы можем использовать это свойство, чтобы упростить выражение:

\[13^{52} = (13^{16})^3 \cdot 13^4 \equiv 1^3 \cdot 13^4 \pmod{17}\]

Теперь найдем \(13^4\) по модулю 17:

\[13^4 = (13^2)^2 = 169^2 \equiv 4^2 \equiv 16 \pmod{17}\]

Теперь мы можем подставить это обратно в исходное выражение:

\[13^{52} \equiv 1 \cdot 16 \equiv 16 \pmod{17}\]

Таким образом, наименьшее положительное число, которое равно \(13^{52}\) по модулю 17, это 16.