Уравнение Пелля с параметром

[wrest]

nnosipov в сообщении #1411161 писал(а):

Давайте такие значения $l$ называть тривиальными. Таким образом, тривиальные значения $l$ --- это $3,8,15,24,35$ и т.д.

Еще из численных результатов видно что много вот таких решений $ly=x+1$

[nnosipov]

wrest в сообщении #1411191 писал(а):

много вот таких решений $ly=x+1$

Тут такая штука: если бы удалось доказать, что для любого решения $(x,y)$ уравнения $x^2-(l^2+l)y^2=-l^2+1$ имеет место сравнение

$$x \equiv \pm 1 \pmod{l},\eqno(*)$$

то тогда гипотезу можно было бы легко доказать. Таким образом, в гипотетическом контрпримере сравнение $(*)$ должно нарушаться.

[wrest]

nnosipov в сообщении #1411192 писал(а):

Таким образом, в гипотетическом контрпримере сравнение $(*)$ должно нарушаться.

Так ведь таких решений полно...
Например $l=120, y=3, x=341$

[nnosipov]

wrest в сообщении #1411194 писал(а):

Например $l=120, y=3, x=341$

Действительно. Не знаю, что с этим делать. Я надеялся, что таких "малых" контрпримеров будет немного.

-- Вт авг 20, 2019 02:41:38 --

nnosipov в сообщении #1411192 писал(а):

если бы удалось доказать, что для любого решения $(x,y)$ уравнения $x^2-(l^2+l)y^2=-l^2+1$ имеет место сравнение

$$x \equiv \pm 1 \pmod{l},\eqno(*)$$

Теперь мы знаем, что это доказать нельзя.

[wrest]

nnosipov в сообщении #1411195 писал(а):

Я надеялся, что таких "малых" контрпримеров будет немного.

Они всегда (в наблюденных рамках $l<10^6$) идут по трое. Одно решение типа $ly=x+1$ и ещё два (для того же $l$) где $ly \ne x+1$
Например:
$l=94248, y=4, x=365023$
$l=94248, y=39, x=3674483$
$l=94248, y=306, x=28839887,ly=x+1$
Кстати, вот решений где $ly=x-1$ не попадалось вовсе.

[wrest]

wrest в сообщении #1411179 писал(а):

Так что перезапустил, до $10^7$

Решений где $l\ne t^2-1$ не нашлось до $l=10^7$
Время счета составило 3 часа.

[nnosipov]

wrest в сообщении #1411242 писал(а):

Решений где $l\ne t^2-1$ не нашлось до $l=10^7$
Время счета составило 3 часа.

Удовольствуемся пока этим. Еще раз спасибо.

[dmd]

Andrey A в сообщении #1410698 писал(а):

$\left\{\begin{matrix} l(y^2-1)+1 & =dp^2\\ l+1 & =dq^2 \end{matrix}\right.$ Отсюда $d=\dfrac{2-y^2}{p^2-(y^2-1)q^2},\ l=\dfrac{q^2-p^2}{p^2-(y^2-1)q^2}.$

Примем $y$ за аргумент: $p^2-(y^2-1)q^2=\dfrac{2-y^2}{d}\ \ \ (2)$

Интересные соотношения получаются.

$y^2 - 2 = d (q^2 (y^2 - 2)-(p^2 - q^2))$

и

$(y^2 - 2) (d q^2 - 1) = d (p^2 - q^2)$

Видим, что $d\mid y^2 - 2$, т.е. двойка есть квадратичный вычет по модулю $d$.

Тогда любой простой делитель $d$, назовём его $p_d$, должен иметь символ Лежандра равный единице $\left(\frac{2}{p_d}\right)=1$, и соответственно символ Кронекера $\left(\frac{2}{d}\right)\neq-1$.

Следующий небольшой тест это подтверждает.

testd()=
{
 for(l=2, 100,
  if(!issquare(l+1),
   for(y=2, sqrtint(l),
    d= gcd(l+1, y^2-2);
    if(d>1, if(issquarefree(d),
     print("l = "l"    d = "d"    "factorint(d))
    ))
   )
  )
 )
};

(вывод теста)

? \r testd.gp
? testd()
l = 5 d = 2 Mat([2, 1])
l = 7 d = 2 Mat([2, 1])
l = 9 d = 2 Mat([2, 1])
l = 11 d = 2 Mat([2, 1])
l = 13 d = 2 Mat([2, 1])
l = 13 d = 7 Mat([7, 1])
l = 17 d = 2 Mat([2, 1])
l = 17 d = 2 Mat([2, 1])
l = 19 d = 2 Mat([2, 1])
l = 19 d = 2 Mat([2, 1])
l = 20 d = 7 Mat([7, 1])
l = 20 d = 7 Mat([7, 1])
l = 21 d = 2 Mat([2, 1])
l = 21 d = 2 Mat([2, 1])
l = 23 d = 2 Mat([2, 1])
l = 23 d = 2 Mat([2, 1])
l = 25 d = 2 Mat([2, 1])
l = 25 d = 2 Mat([2, 1])
l = 27 d = 2 Mat([2, 1])
l = 27 d = 7 Mat([7, 1])
l = 27 d = 14 [2, 1; 7, 1]
l = 29 d = 2 Mat([2, 1])
l = 29 d = 2 Mat([2, 1])
l = 31 d = 2 Mat([2, 1])
l = 31 d = 2 Mat([2, 1])
l = 33 d = 2 Mat([2, 1])
l = 33 d = 2 Mat([2, 1])
l = 34 d = 7 Mat([7, 1])
l = 34 d = 7 Mat([7, 1])
l = 37 d = 2 Mat([2, 1])
l = 37 d = 2 Mat([2, 1])
l = 37 d = 2 Mat([2, 1])
l = 39 d = 2 Mat([2, 1])
l = 39 d = 2 Mat([2, 1])
l = 39 d = 2 Mat([2, 1])
l = 41 d = 2 Mat([2, 1])
l = 41 d = 7 Mat([7, 1])
l = 41 d = 14 [2, 1; 7, 1]
l = 41 d = 2 Mat([2, 1])
l = 43 d = 2 Mat([2, 1])
l = 43 d = 2 Mat([2, 1])
l = 43 d = 2 Mat([2, 1])
l = 45 d = 2 Mat([2, 1])
l = 45 d = 2 Mat([2, 1])
l = 45 d = 23 Mat([23, 1])
l = 45 d = 2 Mat([2, 1])
l = 47 d = 2 Mat([2, 1])
l = 47 d = 2 Mat([2, 1])
l = 47 d = 2 Mat([2, 1])
l = 49 d = 2 Mat([2, 1])
l = 49 d = 2 Mat([2, 1])
l = 49 d = 2 Mat([2, 1])
l = 50 d = 17 Mat([17, 1])
l = 51 d = 2 Mat([2, 1])
l = 51 d = 2 Mat([2, 1])
l = 51 d = 2 Mat([2, 1])
l = 53 d = 2 Mat([2, 1])
l = 53 d = 2 Mat([2, 1])
l = 53 d = 2 Mat([2, 1])
l = 55 d = 2 Mat([2, 1])
l = 55 d = 7 Mat([7, 1])
l = 55 d = 14 [2, 1; 7, 1]
l = 55 d = 2 Mat([2, 1])
l = 57 d = 2 Mat([2, 1])
l = 57 d = 2 Mat([2, 1])
l = 57 d = 2 Mat([2, 1])
l = 59 d = 2 Mat([2, 1])
l = 59 d = 2 Mat([2, 1])
l = 59 d = 2 Mat([2, 1])
l = 61 d = 2 Mat([2, 1])
l = 61 d = 2 Mat([2, 1])
l = 61 d = 2 Mat([2, 1])
l = 62 d = 7 Mat([7, 1])
l = 62 d = 7 Mat([7, 1])
l = 65 d = 2 Mat([2, 1])
l = 65 d = 2 Mat([2, 1])
l = 65 d = 2 Mat([2, 1])
l = 65 d = 2 Mat([2, 1])
l = 67 d = 2 Mat([2, 1])
l = 67 d = 2 Mat([2, 1])
l = 67 d = 34 [2, 1; 17, 1]
l = 67 d = 2 Mat([2, 1])
l = 68 d = 23 Mat([23, 1])
l = 69 d = 2 Mat([2, 1])
l = 69 d = 7 Mat([7, 1])
l = 69 d = 14 [2, 1; 7, 1]
l = 69 d = 2 Mat([2, 1])
l = 69 d = 2 Mat([2, 1])
l = 71 d = 2 Mat([2, 1])
l = 71 d = 2 Mat([2, 1])
l = 71 d = 2 Mat([2, 1])
l = 71 d = 2 Mat([2, 1])
l = 73 d = 2 Mat([2, 1])
l = 73 d = 2 Mat([2, 1])
l = 73 d = 2 Mat([2, 1])
l = 73 d = 2 Mat([2, 1])
l = 75 d = 2 Mat([2, 1])
l = 75 d = 2 Mat([2, 1])
l = 75 d = 2 Mat([2, 1])
l = 75 d = 2 Mat([2, 1])
l = 76 d = 7 Mat([7, 1])
l = 76 d = 7 Mat([7, 1])
l = 77 d = 2 Mat([2, 1])
l = 77 d = 2 Mat([2, 1])
l = 77 d = 2 Mat([2, 1])
l = 77 d = 2 Mat([2, 1])
l = 79 d = 2 Mat([2, 1])
l = 79 d = 2 Mat([2, 1])
l = 79 d = 2 Mat([2, 1])
l = 79 d = 2 Mat([2, 1])
l = 81 d = 2 Mat([2, 1])
l = 81 d = 2 Mat([2, 1])
l = 81 d = 2 Mat([2, 1])
l = 81 d = 2 Mat([2, 1])
l = 83 d = 2 Mat([2, 1])
l = 83 d = 7 Mat([7, 1])
l = 83 d = 14 [2, 1; 7, 1]
l = 83 d = 2 Mat([2, 1])
l = 83 d = 2 Mat([2, 1])
l = 84 d = 17 Mat([17, 1])
l = 85 d = 2 Mat([2, 1])
l = 85 d = 2 Mat([2, 1])
l = 85 d = 2 Mat([2, 1])
l = 85 d = 2 Mat([2, 1])
l = 87 d = 2 Mat([2, 1])
l = 87 d = 2 Mat([2, 1])
l = 87 d = 2 Mat([2, 1])
l = 87 d = 2 Mat([2, 1])
l = 89 d = 2 Mat([2, 1])
l = 89 d = 2 Mat([2, 1])
l = 89 d = 2 Mat([2, 1])
l = 89 d = 2 Mat([2, 1])
l = 90 d = 7 Mat([7, 1])
l = 90 d = 7 Mat([7, 1])
l = 91 d = 2 Mat([2, 1])
l = 91 d = 2 Mat([2, 1])
l = 91 d = 23 Mat([23, 1])
l = 91 d = 2 Mat([2, 1])
l = 91 d = 2 Mat([2, 1])
l = 92 d = 31 Mat([31, 1])
l = 93 d = 2 Mat([2, 1])
l = 93 d = 2 Mat([2, 1])
l = 93 d = 2 Mat([2, 1])
l = 93 d = 47 Mat([47, 1])
l = 93 d = 2 Mat([2, 1])
l = 95 d = 2 Mat([2, 1])
l = 95 d = 2 Mat([2, 1])
l = 95 d = 2 Mat([2, 1])
l = 95 d = 2 Mat([2, 1])
l = 97 d = 2 Mat([2, 1])
l = 97 d = 7 Mat([7, 1])
l = 97 d = 14 [2, 1; 7, 1]
l = 97 d = 2 Mat([2, 1])
l = 97 d = 2 Mat([2, 1])

Видно, что, кроме двойки, в кандидатах $d$ простыми делителями являются только 7,17,23,31,47, у которых символ Лежандра равен единице.

Возможно ли это как-то использовать в поиске контрпримера? И что можно сказать о чётности $d$?

[nnosipov]

Вот что придумалось.

Рассмотрим уравнение (2), которое написал Andrey A. Похоже, с ним и надо работать, оно наиболее удобно. Можно считать, что $d$ свободно от квадратов и что простые делители $d$ --- это $2$ и простые числа вида $8k \pm 1$. Так вот, интерес могут представлять только "маленькие" значения $d$. Точная формулировка такова. Пусть $y \geqslant 25$. Если $d>\frac{y^2-2}{12y} \approx y/12$, то уравнение (2) заведомо неразрешимо. Это утверждение не очевидно, но его можно доказать.

Таким образом, в поисках контрпримера мы можем перебирать только пары $(y,d)$ с условием $y \geqslant 25$, $d \leqslant \frac{y^2-2}{12y}$, $d$ свободно от квадратов и имеет простые делители указанного выше вида. Для каждой такой пары нужно предварительно вычислить символ Якоби $(d/y^2-1)$ и, если он равен единице, решать уравнение (2). (В случае нечетного $y$ нужно из знаменателя символа Якоби изъять двойки или просто ограничиться четными значениями $y$.)

[lel0lel]

wrest в сообщении #1411204 писал(а):

Кстати, вот решений где $ly=x-1$ не попадалось вовсе.

При условии что $y<\sqrt{l}$ так и должно быть.
Распишу подробнее.
Пусть $l\geq 2$. Если справедливо $x\equiv \pm1\pmod{l}$, тогда $x=k l\pm1$. Подставим в исходное уравнение $x=k l+1$ $(k\in \mathbb{Z})$. Заметим следующее: если $k<0$, то исследуется вопрос о существовании решений для которых $x>0$ и $x\equiv -1\pmod{l}$; если $k\geq 0$, то исследуется вопрос о существовании решений для котороых $x>0$ и $x\equiv 1\pmod{l}$. После раскрытия скобок:

$$k^2 l-y^2 l+l+2k-y^2=0.$$

Из полученного видно что $y^2=s l+2 k$, подставляем этот результат в уравнение и после преобразований получаем $l=(k-1)^2/s-1$ (здесь $s\ne 0$, иначе целочисленных решений нет, в этом легко убедиться). Из последнего равенства имеем $sl=(k-1)^2-s$; используя это в $y^2=s l+2 k$, получаем $y^2=k^2+1-s$. Итак, мы свели вопрос нахождения решений для которых $x\equiv \pm1\pmod{l}$ к вопросу нахождения целочисленных решений следующей системы:

$$l=\frac{(k-1)^2}{s}-1\,\,\, \text{ и }\,\,\, y^2=k^2+1-s.$$

В таком виде эту систему удобно исследовать. Поскольку мы рассматриваем случай $l\geq 2$, то из первого уравнения следует что $s>0$. Теперь используем лемму nnosipov, чтобы найти допустимые значения $s$. Если уравнение имеет целочисленные решения, то найдётся такое, для которого $y^2<l$. Тогда, используя полученную систему, имеем неравенство в целых числах

$$k^2+1-s<\frac{(k-1)^2}{s}-1,\,\,\text{ целое число } \frac{(k-1)^2}{s}-1\geq 2.$$

Получаем ответ $s=1, k<0$; ход решения, отбрасывая детали, описывается слоганом: "делить -- это Вам не вычитать!" Заметим, что случай $k<0$ соответствует $x>0$ и $x\equiv -1\pmod{l}$, это и наблюдается в экспериментах, проводимых с ограничивающим условием $y<\sqrt{l}$.

Подводя итог:
1) Если $l\geq 3$ такое, что из сравнения $x^2\equiv 1\pmod{l}$ (которое верно по условию) с необходимостью следует $x\equiv \pm1\pmod{l}$, тогда исходное уравнение имеет решение только если $l=t^2-1$. Из чего следует, что $l$ не может быть простым числом большим трёх, а также не может быть степенью простого большего двух.
2) Если $l=t^2-1$, тогда в положительной области есть следующие решения $((t+1)(t^2-1)+1,t+1), ((t-1)(t^2-1)-1,t-1)$.

[nnosipov]

lel0lel в сообщении #1411316 писал(а):

а также не может быть степенью простого большего двух

Кстати, да. Таким образом, исходная задача решена и даже с запасом.

[wrest]

lel0lel в сообщении #1411316 писал(а):

1) Если $l\geq 3$ такое, что из сравнения $x^2\equiv 1\pmod{l}$ (которое верно по условию) с необходимостью следует $x\equiv \pm1\pmod{l}$,

То есть, осталось показать что $l$ именно такое...

[lel0lel]

Не совсем так. Таких $l$ мало, примером служат простые числа. Надо с другими $l$ теперь разбираться, про них ничего не утверждается.

[nnosipov]

wrest в сообщении #1411322 писал(а):

То есть, осталось показать что $l$ именно такое...

Это нельзя показать, вот Ваш же пример:

wrest в сообщении #1411194 писал(а):

Например $l=120, y=3, x=341$

Здесь $x^2 \equiv 1 \pmod{l}$, но оба сравнения $x \equiv \pm 1 \pmod{l}$ не имеют места.

[wrest]

nnosipov в сообщении #1411325 писал(а):

Это нельзя показать, вот Ваш же пример:

А, ну да...
Остается недоказанным, что всегда $l=t^2-1$