Руст писал(а):
... T(n) линейный оператор, соответственно на множестве остатков по модулю 2^k ...
Какая линейность?

Цитата:
В принципе можно представить и решение в явном виде начиная разрешать с конца
Так и есть. Удлинять двоичную последовательность надо с конца. Пристроить нули спереди нет проблем. Чуть сложнее пристроить единицу с некоторым количеством нулей.
Чуть подробнее скажу, чем в цитате выше.
1) Сначала подъём: вместо

берём

, тогда очевидно

для

, то есть возникающая из

двоичная последовательность не будет отличаться от прежней столь долго, сколько пожелаем.
2) Умножив на

, получим

, для которого эта последовательность надстроится

нулями спереди.
3) Достаточно большое

выбираем теперь так, чтобы

делилось на

.
Согласен, что задача несложная. Цитата перед вами - сам оценивал это как тривиальный факт и когда предлагал её для матбоя, в котором участвовали студенты 1-3 курсов тоже имел сомнения, а не слишком ли она проста. Как оказалось - не слишком.