Квадрата из единиц и нулей не существует

[maxal]

Руст в сообщении #524622 писал(а):

Можно вычислить один корень $x<5*10^n$ по модулю $10^{n+1},n>1$, остальные находятся по формулам $5*10^n-x, 5*10^n+x,10^{n+1}-x$. Приведенный пример не является контпримером, так как $x=25749$ и не начинается на 10 или 31.

Тогда вот аж два контрпримера:

$$1011001 \equiv 10380501^2 \pmod{10^8}$$

$$110001 \equiv 31976249^2 \pmod{10^8}$$

[Руст]

maxal в сообщении #524634 писал(а):

Руст в сообщении #524622 писал(а):

Можно вычислить один корень $x<5*10^n$ по модулю $10^{n+1},n>1$, остальные находятся по формулам $5*10^n-x, 5*10^n+x,10^{n+1}-x$. Приведенный пример не является контпримером, так как $x=25749$ и не начинается на 10 или 31.

Тогда вот аж два контрпримера:

$$1011001 \equiv 10380501^2 \pmod{10^8}$$

$$110001 \equiv 31976249^2 \pmod{10^8}$$

Вообще и они не контпримеры. Так как я предлагал брать квадратный корень x от $n$ значного числа по модулю $10^k, k>n/2+1$. В первом случае правда $n=15$ во втором $n=16$ и в этом смысле они не проходят.
По видимому можно использовать индукцию по количеству цифр для доказательства отсутствия такого квадратного корня.

[maxal]

Вообще-то ранее было $k=[n/2]+1$ - и в первом контрпримере $n=15$, $k=8 =[n/2]+1$, а корень начинается c "10".

Вот еще контрпримерчик с $n=21$ и $k=12 > n/2+1$:

$$10245124499^2 = 104962576000010001001 \equiv 10001001 \pmod{10^{12}}.$$

[Руст]

На самом деле я хотел брать $k$ на 1 больше, чем разряд 1, встречающийся у исходного числа $y$ в первой половине.
В этом смысле собирался доказывать по индукции. Здесь в первой половине $104962576000010001001$
1) первой с конца не нулевой разряд 6 а не 1, к тому же
2) он соответствует $k=13$.
Однако примеры интересны.

[maxal]

Руст в сообщении #524736 писал(а):

Здесь в первой половине $104962576000010001001$
1) первой с конца не нулевой разряд 6 а не 1

Тогда такой пример:

$$10164569499^2 = 1033184731|00001111001$$

[Руст]

Убедил. Совмещение неархимедового квадратного корня (по модулю и с конца) с архимедовым (с начала) только на 1-2 знаках ничего не дает.