Question

Докажите, что если: 2^n=1(mod13), то 2^(n+12)=1(mod13)

Answer 1

4096=2^12 при делении на 13 дает такой же остаток, как и 1: 1/13, т.е. 2^12==1(mod13). Согласно свойству сравнения по модулю левые и правые части можно перемножать: 2^n*2^12== 1*1(mod13), тогда 2^(n+12)== 1(mod13), чтд

Answer 2

Для доказательства данного утверждения, воспользуемся свойством модульной арифметики и алгеброй вычетов.

Из условия дано, что $2^n \equiv 1 \pmod{13}$, что означает, что $2^n$ и $1$ имеют одинаковый остаток при делении на $13$.

Мы хотим доказать, что $2^{n+12} \equiv 1 \pmod{13}$. Разложим $2^{n+12}$ по модулю $13$:

$2^{n+12} = 2^n \cdot 2^{12}$

Теперь рассмотрим $2^{12}$. Мы можем вычислить его значение по модулю $13$:

$2^{12} \equiv 4096 \equiv 1 \pmod{13}$

Так как $2^{12}$ имеет остаток $1$ при делении на $13$, то это значит, что $2^{n+12}$ также будет иметь остаток $1$ при делении на $13$, если $2^n$ имеет остаток $1$ при делении на $13$.

Таким образом, если $2^n \equiv 1 \pmod{13}$, то $2^{n+12} \equiv 1 \pmod{13}$, что и требовалось доказать.