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

[sbidujko]

Доказать, что число, состоящее из нулей и единиц (единиц, понятно, больше одной) не может быть точным квадратом

[Sirion]

(Оффтоп)

$11001 = 101^2$

[Did]

Рассмотрите остатки от деления полного квадрата на четыре.

[Sirion]

Did в сообщении #524355 писал(а):

Рассмотрите Остатки от деления полного квадрата на четыре.

Честно говоря, не понимаю, как это поможет.
Остаток от деления на 4 зависит лишь от последних двух цифр. Таким образом, мы исключаем лишь случаи, когда последние две цифры 11 или 10; случаи 01 и 00 (последний можно свести к одному из трёх предыдущих) не исключаются.
Кстати,
$2401 = 49^2$
т.е. случай 01 фактически возможен.

[sbidujko]

Ну будут остатки 0 и 1, дальше что? Кстати, видел обсуждение этой задачи на разных сайтах, но решения не нашел.

[Sirion]

Есть предположение, что $10^n+1$ всегда будет квадратичным невычетом по модулю $10^n$. Проверю чуть позже, если никто до меня этого не сделает.

[maxal]

sbidujko в сообщении #524330 писал(а):

Доказать, что число, состоящее из нулей и единиц (единиц, понятно, больше одной) не может быть точным квадратом

Похоже на открытую проблему.
См. A018884 и F24 in UPINT.

[Sirion]

Sirion в сообщении #524363 писал(а):

Есть предположение, что $10^n+1$ всегда будет квадратичным невычетом по модулю $10^n$. Проверю чуть позже, если никто до меня этого не сделает.

по модулю $10^{n+1}$, разумеется

предположение не оправдалось
$501^2 = 251001$

[Руст]

Если проверять по модулю $10^{n+1}$, то надо проверить число $10^n+10^k+1,n>k>0$. Вроде оно не является квадратичным вычетом.

[maxal]

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

Если проверять по модулю $10^{n+1}$, то надо проверить число $10^n+10^k+1,n>k>0$. Вроде оно не является квадратичным вычетом.

$10^4+10^3+1$ является квадратичным вычетом по модулю $10^5$

[Батороев]

Что-то подсказывает, что выражение $10^{l}+...+10^{m}+10^{n}=a^2-1$ разложить на два множителя, разность между которыми равна $2$, невозможно.

$10^n\cdot (10^{l-n}+...+10^{m-n}+1)=a^2-1$

Получаем два взаимнопростых множителя разной четности.
Поэтому должно выполняться равенство:

$2\cdot \dfrac {(10^{l-n}+...+10^{m-n}+1)}{b}-5\cdot 10^{n-1}\cdot b=\pm 2$,
где $b$ - нечетное число, взаимнопростое с $\dfrac {(10^{l-n}+...+10^{m-n}+1)}{b}$. (1)

$\dfrac {(10^{l-n}+...+10^{m-n}+1)}{b}-25\cdot 10^{n-2}\cdot b=\pm 1$ (2)

$(10^{l-n}+...+10^{m-n}+1)-25\cdot 10^{n-2}\cdot b^2=\pm b$, что при условии (1) невозможно, только если $b$ не равно $1$.

Но при $b=1$, равенство (2) также невыполнимо:

$10^{l-n}+...+10^{m-n}+1-25\cdot 10^{n-2}=\pm 1$.

-- 08 янв 2012 16:05 --

Что-то меня не туда занесло. Вот здесь не верно:

Батороев в сообщении #524494 писал(а):

$(10^{l-n}+...+10^{m-n}+1)-25\cdot 10^{n-2}\cdot b^2=\pm b$, что при условии (1) невозможно, только если $b$ не равно $1$.

т.к. $b$ как раз-то является множителем $(10^{l-n}+...+10^{m-n}+1)$.

[RIP]

Не, так тупо не получится: если число заканчивается на 001, то оно $\equiv1\pmod8$ и $\equiv1\pmod5$, поэтому является квадратичным вычетом по модулю любой степени $10$.

[Руст]

Любое число заканчивающееся на $001$ является квадратичным вычетом по модулю $10^n$. Поэтому $n>3$ значного числа оканчивающего на $001$ однозначно (с точностью до знака) извлечем квадратный корень по модулю $M=10^{[n/2]+1$, пусть он равен х. Если исходное число является квадратом, то он квадрат $x^2$ или $(M-x)^2$. В нашем случае это означат, что первые цифры х должны быть $10...$ при нечетном n или $31....$ при четном. $M-x$ исключается, так как количество знаков для квадрата будет больше n. Вроде можно показать, что при извлечении квадратного корня по модулю не получится число начинающееся на такие числа.

[maxal]

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

Любое число заканчивающееся на $001$ является квадратичным вычетом по модулю $10^n$. Поэтому $n>3$ значного числа оканчивающего на $001$ однозначно (с точностью до знака) извлечем квадратный корень по модулю $M=10^{[n/2]+1$, пусть он равен х. Если исходное число является квадратом, то он квадрат $x^2$ или $(M-x)^2$. В нашем случае это означат, что первые цифры х должны быть $10...$ при нечетном n или $31....$ при четном. $M-x$ исключается, так как количество знаков для квадрата будет больше n. Вроде можно показать, что при извлечении квадратного корня по модулю не получится число начинающееся на такие числа.

Не получится. Для $n=13$ имеем контрпример:

$$1011001\equiv 1025749^2 \pmod{10^7}.$$

P.S. Кроме того, квадратных корней по составному модулю может быть больше двух - "однозначно (с точностью до знака)" здесь не работает.

[Руст]

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

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

Любое число заканчивающееся на $001$ является квадратичным вычетом по модулю $10^n$. Поэтому $n>3$ значного числа оканчивающего на $001$ однозначно (с точностью до знака) извлечем квадратный корень по модулю $M=10^{[n/2]+1$, пусть он равен х. Если исходное число является квадратом, то он квадрат $x^2$ или $(M-x)^2$. В нашем случае это означат, что первые цифры х должны быть $10...$ при нечетном n или $31....$ при четном. $M-x$ исключается, так как количество знаков для квадрата будет больше n. Вроде можно показать, что при извлечении квадратного корня по модулю не получится число начинающееся на такие числа.

Не получится. Для $n=13$ имеем контрпример:

$$1011001\equiv 1025749^2 \pmod{10^7}.$$

P.S. Кроме того, квадратных корней по составному модулю может быть больше двух - "однозначно (с точностью до знака)" здесь не работает.

Точнее квадратных корней по модулю $n$ ровно $2^{\v(n)}$, где $v(n)$ количество простых делителей. В нашем случае 4.
Можно вычислить один корень $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.