Упр.29.6 ГДЗ Мерзляк Поляков 8 класс (Алгебра)

Задача

Рассмотрим вариант решения задания из учебника Мерзляк, Поляков 8 класс, Вентана-Граф: 29.6. Докажите, что ?(a_n a_(n-1)…a_k a_(k-1)…a_0 )??(a_(k-1) a_(k-2)…a_0 ) (mod 2^k ).

Подробный ответ

Рассмотрим число

$$\overline{a_n a_{n-1}\dots a_k a_{k-1}\dots a_0}.$$

Его можно записать так:

$$\overline{a_n a_{n-1}\dots a_k a_{k-1}\dots a_0}=a_0+10a_1+10^2a_2+\dots+10^k a_k+\dots+10^n a_n.$$

Нужно доказать, что

$$\overline{a_n a_{n-1}\dots a_k a_{k-1}\dots a_0}\equiv \overline{a_{k-1}a_{k-2}\dots a_0}\pmod{2^k}.$$

Для этого заметим, что при делении на $$2^k$$ все слагаемые с множителями $$10^k,10^{k+1},\dots,10^n$$ дают остаток $$0$$, так как

$$10^k=2^k\cdot 5^k,$$

а значит, $$10^k,10^{k+1},\dots,10^n$$ делятся на $$2^k$$.

Следовательно, по модулю $$2^k$$ остаётся только часть числа, составленная из последних $$k$$ цифр:

$$\overline{a_n a_{n-1}\dots a_k a_{k-1}\dots a_0}\equiv a_{k-1}10^{k-1}+a_{k-2}10^{k-2}+\dots+a_1\cdot 10+a_0 \pmod{2^k}.$$