2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Квадрата из единиц и нулей не существует
Сообщение08.01.2012, 19:58 
Модератор
Аватара пользователя


11/01/06
5710
Руст в сообщении #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}$$

 Профиль  
                  
 
 Re: Квадрата из единиц и нулей не существует
Сообщение08.01.2012, 20:38 
Заслуженный участник


09/02/06
4401
Москва
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$ и в этом смысле они не проходят.
По видимому можно использовать индукцию по количеству цифр для доказательства отсутствия такого квадратного корня.

 Профиль  
                  
 
 Re: Квадрата из единиц и нулей не существует
Сообщение08.01.2012, 23:23 
Модератор
Аватара пользователя


11/01/06
5710
Вообще-то ранее было $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}}.$$

 Профиль  
                  
 
 Re: Квадрата из единиц и нулей не существует
Сообщение08.01.2012, 23:42 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Квадрата из единиц и нулей не существует
Сообщение09.01.2012, 01:13 
Модератор
Аватара пользователя


11/01/06
5710
Руст в сообщении #524736 писал(а):
Здесь в первой половине $104962576000010001001$
1) первой с конца не нулевой разряд 6 а не 1

Тогда такой пример:
$$10164569499^2 = 1033184731|00001111001$$

 Профиль  
                  
 
 Re: Квадрата из единиц и нулей не существует
Сообщение09.01.2012, 08:22 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 21 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group