2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: решить уравнение в целых числах
Сообщение27.11.2011, 16:59 


16/08/05
1146
И, следовательно,

$x_{1,2}^2\equiv 1\pmod d$

 Профиль  
                  
 
 Re: решить уравнение в целых числах
Сообщение27.11.2011, 22:49 


16/08/05
1146
dmd в сообщении #508837 писал(а):
И, следовательно,

$x_{1,2}^2\equiv 1\pmod d$

:-) , самому смешно, вывел тривиальность.


Еще одно соотношение

$x_1x_2+1=d(x_{1,2}-y_{1,2})$

 Профиль  
                  
 
 Re: решить уравнение в целых числах
Сообщение28.11.2011, 16:13 
Заслуженный участник


08/04/08
8556

(Оффтоп)

у меня такое ощущение, что если Вы клоните к алгоритму факторизации $d$, то не все так просто...

 Профиль  
                  
 
 Re: решить уравнение в целых числах
Сообщение28.11.2011, 18:29 


16/08/05
1146
Sonic86 в сообщении #509206 писал(а):
у меня такое ощущение, что если Вы клоните к алгоритму факторизации $d$, то не все так просто...

Понимаю, что не просто. Главное - интересно.

Например, в этой задаче наблюдаются своеобразные "спуск" и "подъем" по подобным уравнениям и их нетривиальным решениям. При спуске новый нижний $x$ это бывшие верхние $x\% y$, новый $d$ это верхний $y$. При этом не важно от $x_1$ или $x_2$ начинается спуск, заканчивается он внизу одинаково.

 Профиль  
                  
 
 Re: решить уравнение в целых числах
Сообщение29.11.2011, 21:34 


16/08/05
1146
dmd в сообщении #508995 писал(а):
Еще одно соотношение

$x_1x_2+1=d(x_{1,2}-y_{1,2})$

Если обозначить

$x_{1,2}-y_{1,2}=s$

то

$x_1x_2+1=ds$

$y_1y_2+1=s^2$

 Профиль  
                  
 
 Re: решить уравнение в целых числах
Сообщение03.12.2011, 21:37 


16/08/05
1146
Удивительно, но заменой $Y=d(y+2)+1$ исходное уравнение преобразуется в эллиптическое:

$Z^2=Y^3-3d^2Y-2d^3$

Примеры:

$d=527,y_{1,2}=\{45,264\},Y_{1,2}=\{24770,140183\},Z_{1,2}=\{3895738,52484830\}$

$d=893,y_{1,2}=\{40, 555\},Y_{1,2}=\{37507, 497402\},Z_{1,2}=\{7257600, 350799680\}$

 Профиль  
                  
 
 Re: решить уравнение в целых числах
Сообщение04.12.2011, 07:37 


16/08/05
1146
dmd в сообщении #511186 писал(а):
$Z^2=Y^3-3d^2Y-2d^3$

Две целых точки $\{Y,Z\}$ на этой кривой очевидны: $\{-d,0\}$ и $\{2d,0\}$.

Третья точка $\{2d+64,8(3d+64)\}$.

 Профиль  
                  
 
 Re: решить уравнение в целых числах
Сообщение05.12.2011, 15:13 


16/08/05
1146
Понял свою ошибку, правая часть раскладывается

$Y^3-3d^2Y-2d^3=(Y-2d)(Y+d)^2$

 Профиль  
                  
 
 Re: решить уравнение в целых числах
Сообщение10.12.2011, 15:40 


16/08/05
1146
В этой задаче действует Малая теорема Ферма. Только для нетривиальных иксов справедливо соотношение:

$x_{1,2}^{d-1}\equiv 1\pmod d$

Т.е. $d$ псевдопростое по основанию $x_{1,2}$

 Профиль  
                  
 
 Re: решить уравнение в целых числах
Сообщение10.12.2011, 19:53 


16/08/05
1146
Впрочем, это тоже тривиальность. Для любого четного $n$ выполняется $x_{1,2}^n\equiv 1\pmod d$.

 Профиль  
                  
 
 Re: решить уравнение в целых числах
Сообщение01.07.2015, 09:05 


16/08/05
1146
Параметризация делителями.


Пусть $x^2-dy=1$ - уравнение в рациональных числах, где $d$ - заданное натуральное. И пусть даны произвольные целые $a,b$. Выделим из числа $4abd$ делители $p$ и $q$: $4abd=pq$. Причём $p,q$ не обязательно целые. Тогда справедлива параметризация

$x= \frac{ap+bq}{ap-bq},\qquad y=\frac{16a^2b^2}{(ap-bq)^2}$

 Профиль  
                  
 
 Re: решить уравнение в целых числах
Сообщение01.07.2015, 15:39 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
dmd в сообщении #1032660 писал(а):
Пусть $x^2-dy=1$

Перепишем: $d=\frac{x^2-1}{y}$ или $\sqrt{d}\approx \frac{x}{\sqrt{y}}$.
Подходящие дроби разложения $\sqrt{d}$ дают приближения в рациональных числах, и решение ур. Пелля. Если бы существовал алгоритм аппроксимации дробями вида $\frac{p}{\sqrt{q}}$, это был бы ответ на Ваш вопрос, который лучше сформулировать так: найти наименьшее натуральное $x\neq 1$ такое, что $x^2\equiv 1\mod d$. Решение $x=d-1$ верно не только для простого $d$. Так же и для степеней нечетных простых и для удвоенных степеней нечетных простых. Строго говоря, задача не эквивалентна факторизации. Из ее решения получаем только одну пару делителей $d$, среди которых может оказаться и единица. Если же $d$ имеет много пар вз. простых делителей, то нахождение всех квадратов $\equiv1$ с последующей сортировкой может оказаться не самым экономным способом. Даже если делители известны.

 Профиль  
                  
 
 Re: решить уравнение в целых числах
Сообщение08.07.2015, 09:45 
Заслуженный участник
Аватара пользователя


21/12/05
5903
Новосибирск
Переформулировка: Найти все $x$, для которых $x^2-1\equiv 0\pmod {d}$
Эта стандартная задача изложена везде - в Бухштабе, скажем. Начинается она с отыскания решений по модулям простых делителей $d$. Это самая сложная часть - перебор потому что. Поскольку степень сравнения два, то и перебора нет - решений не может быть больше двух, а два есть - это 1 и -1. Далее следует их поднять по показателю степени, с которым простое входит в каноническое разложение $d$ и, наконец, собрать по китайской теореме об остатках.

-- Ср июл 08, 2015 14:02:06 --

PS. Так как $(x^2-1)'=2x\equiv 0\pmod {2}$, то подъём по модулю 2 будет произвольным, а по остальным $p$ однозначным, то количество несравнимых решений (по модулю $d$) будет равно показателю степени, с которым двойка входит в каноническое разложение $d.$

ЗЫ.
bot в сообщении #1034592 писал(а):
будет равно показателю степени, с которым двойка входит в каноническое разложение

Ерунду написал - поторопился потому что. Для $d=2^{k_0}p_1^k^1\ldots p_s^{k_s}$ количество решений будет $m2^s, \ \ 1\leqslant m\leqslant 2^{k_0-1}$ - по нечётному простому решений ведь два и каждое поднимается однозначно, а по модулю 2 некоторые ветки могут раздваиваться, а другие отваливаться.

 Профиль  
                  
 
 Re: решить уравнение в целых числах
Сообщение08.07.2015, 11:35 
Заслуженный участник
Аватара пользователя


21/12/05
5903
Новосибирск
А нет ли в OEIS числа решений сравнения $x^2\equiv 1\pmod{2^k}$?
Это надо взять бинарное представление икса, возвести в квадрат и посмотреть, чтоб ненужных степеней не не было ... хм, не так-то просто, кажется.

 Профиль  
                  
 
 Re: решить уравнение в целых числах
Сообщение08.07.2015, 12:12 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
По поводу количества решений у Бухштаба есть теорема на стр. 169, но нужно ли знать все чтобы найти наименьшее?

(Оффтоп)

— Г-голубчики, — сказал Фёдор Симеонович озадаченно, разобравшись в почерках. — Это же п-проблема Бен Б-бецалеля. К-калиостро же доказал, что она н-не имеет р-решения.
— Мы сами знаем, что она не имеет решения, — сказал Хунта, немедленно ощетиниваясь. — Мы хотим знать, как её решать.
— К-как-то ты странно рассуждаешь, К-кристо… К-как же искать решение, к-когда его нет? Б-бессмыслица какая-то…
— Извини, Теодор, но это ты очень странно рассуждаешь. Бессмыслица — искать решение, если оно и так есть. Речь идёт о том, как поступать с задачей, которая решения не имеет. Это глубоко принципиальный вопрос, который, как я вижу, тебе, прикладнику, к сожалению, не доступен...

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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