Модулярное уравнение

[Daniil_Sh]

Пусть имеется число $2^n-1$ для некоторого $n$, в двоичном представлении $n$ единиц. Если умножить $2^n-1$ на произвольное натуральное число, получим новое число $y$: $(2^n-1)x=y$. Хочется найти такое $x$, чтобы минимизировать количество единиц в двоичном представлении $y$. Есть подозрение, что меньше $n$ единиц получить нельзя.
Например, при $n=3$ хотим получить 2 единицы в $y_{[2]}$, то есть должно быть $7x=2^{s_1}+2^{s_2}$. Тогда $2^{s_1}+2^{s_2}\equiv 0 \pmod{7}$. Это значит, что $2^{s_1-s_2}\equiv 6 \pmod{7}$, что невозможно.
В общем случае, $(2^n-1)x=2^{s_1}+2^{s_2}+...+2^{s_k}$, $k<n$, и нужно проверить разрешимость сравнения $2^{s_1}+2^{s_2}+...+2^{s_k}\equiv 0 \pmod{2^n-1}$, $0<s_1,s_2,...,s_k<2^n-1$, $s_i\neq s_j$ при $i\neq j$.

[vpb]

Daniil_Sh в сообщении #1515834 писал(а):

Есть подозрение, что меньше $n$ единиц получить нельзя.

Скорее всего, это подозрение неправильно. Вычетов $2^i$ по модулю $2^n-1$ есть $n$ разных, возможных их сумм по $n-1$ без учета равных $n^{n-1}$, что-то много.

[nnosipov]

vpb в сообщении #1515838 писал(а):

что-то много

Да, много. Но утверждение мне кажется верным. Я бы его доказывал индукцией по $k$. Сначала нужно только редуцировать $s_i$ по модулю $n$. Если после этого появятся одинаковые $s_i$, то соответствующие две степени двойки сложить (это уменьшит $k$ и позволит сделать шаг индукции). Нет?

[vpb]

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

[Daniil_Sh]

Можно ли просто сказать, что $2^{s_1}+2^{s_2}+...+s^{s_k}<\sum\limits_{i=0}^{n-1}2^i=2^n-1$?

[nnosipov]

Если считать, что все $s_i$ меньше $n$ и попарно различны, то да.

[Daniil_Sh]

nnosipov, после редукции всех $s_i$ по модулю $n$ некоторые $s_i$ могут совпасть, и количество слагаемых может уменьшится, но неравенство по-прежнему верно.

[nnosipov]

Daniil_Sh в сообщении #1515851 писал(а):

но неравенство по-прежнему верно.

Нет. Например, после редукции все $s_i$ могут быть равны $n-1$.

[Daniil_Sh]

nnosipov, да, но можно сложить и снова редуцировать.

[nnosipov]

Daniil_Sh в сообщении #1515856 писал(а):

да, но можно сложить и снова редуцировать

И что? Вы напишите рассуждение целиком. Но предварительно четко сформулируйте то утверждение, которое собираетесь доказывать. Пока у Вас какие-то мутные формулировки.

[Daniil_Sh]

Рассматриваем уравнение $2^{s_1}+2^{s_2}+...+2^{s_k}\equiv 0 \pmod{2^n-1}$, где $s_i$ — натуральные числа. Нужно доказать, что решений нет.
Берём показатели $s_i$ по модулю $n$. Если после этого все $s_i$ различны, то $\sum\limits_{i=0}^{k}2^{s_i}<\sum\limits_{i=0}^{n-1}2^i=2^n-1$, и решений нет.
Если есть совпадающие $s_i$, складываем $2^{s_i}+2^{s_i}=2^{s_i+1}$, после чего при необходимости делаем редукцию по модулю $n$. В результате показатели будут различными, а количество слагаемых $l$ станет меньше $k$. Тогда $\sum\limits_{i=0}^{l}2^{s_i}<\sum\limits_{i=0}^{n-1}2^i=2^n-1$. В любом случае у сравнения нет решений.

[nnosipov]

Daniil_Sh в сообщении #1515863 писал(а):

где $s_i$ — натуральные числа

Я бы написал: целые неотрицательные числа.

Daniil_Sh в сообщении #1515863 писал(а):

$\sum\limits_{i=0}^{k}2^{s_i}$

Здесь нужно $\sum\limits_{i=1}^{k}2^{s_i}$.

Daniil_Sh в сообщении #1515863 писал(а):

В результате показатели будут различными

Я бы добавил: вообще говоря, через несколько итераций (сложение+редукция).

[Daniil_Sh]

Да-да, $s_i$ может быть и нулевым.
Спасибо.

[Daniil_Sh]

Хотелось бы ещё обобщить задачу, заменив $2^n-1$ на произвольное положительное нечётное число $m$, в двоичном представлении которого $k\geq 3$ единиц (то есть не рассматриваем нечётные вида $2^n+1$), и цель — уменьшить количество единиц. В тех случаях, когда 2 является первообразным корнем по модулю $m$, задача разрешима.
Для $m=23$ изначально $4$ единицы и $2$ не является образующей $\mathbb{Z}_{23}^{\times}$. Можно уменьшить количество единиц до $3$, поскольку сравнение $2^{s_1}+2^{s_2}+2^{s_3}\equiv 0\pmod{23}$ разрешимо; до двух уменьшить нельзя, так как $22\notin \langle2\rangle$.
Как обрабатывать произвольное нечётное $m$ не вида $2^n\pm 1$, и для которого $2$ не является первообразным корнем по модулю $m$?