Уравнение Пелля — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 8 промежуточных версий 4 участников)
Строка 1: Строка 1:
{{В разработке}}
 
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Уравнение вида <tex>x^2-dy^2=1</tex>, где <tex>d\in\mathbb{N}</tex> не является квадратом, называется уравнением Пелля
+
Уравнение вида <tex>x^2-dy^2=1</tex>, где <tex>d\in\mathbb{N}</tex> не является квадратом, называется '''уравнением Пелля'''.
 +
Как правило, стоит задача поиска всех целых корней этого уравнения при данном <tex>d</tex>.
 
}}
 
}}
  
 
У этого уравнения есть тривиальное решение <tex>x=1, y=0</tex>.  
 
У этого уравнения есть тривиальное решение <tex>x=1, y=0</tex>.  
 +
{{Теорема
 +
|statement=
 +
Любое решение уравнения Пелля {{---}} подходящая дробь для <tex>\sqrt{d}</tex>.
 +
|proof=
 +
Рассматриваем <tex>x,y>0</tex>, остальные корни получатся из симметрии. Так как <tex>\sqrt{d}\geqslant 1</tex>, то <tex>x>y>0</tex>.
 +
<tex>x+\sqrt{d}y>2y</tex>. Следовательно <tex>1=x^2-dy^2=(x-\sqrt{d}y)(x+\sqrt{d}y)>(x-\sqrt{d}y)2y</tex>. Разделим обе части на <tex>2y^2</tex> получим :
 +
<tex>\frac{x}{y}-\sqrt{d} < \frac{1}{2y^2}</tex>. Значит по [[Цепные дроби как приближение к числу#contFracCrit|теореме о приближении]] <tex>\frac{x}{y}</tex> является подходящей дробью для <tex>\sqrt{d}</tex>.
 +
}}
  
 +
== Существование решения уравнения Пелля ==
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Любое решение уравнения Пелля - подходящая дробь для <tex>\sqrt{d}</tex>.
+
Уравнение Пелля имеет нетривиальное решение. Доказательство через цепные дроби.
 
|proof=
 
|proof=
Рассматриваем <tex>x,y>0</tex>, остальные корни получатся из симметрии. Так как <tex>\sqrt{d}\geqslant 1</tex>, то <tex>x>y>0</tex>.
+
Разложим <tex>\sqrt{d}</tex> в цепную дробь. <tex> \sqrt{d}=a_0+\frac{1}{a_1+\cdots+\frac{1}{a_0+\sqrt{d}}}</tex>. Значит <tex>\sqrt{d}=\frac{P_{n-1}(a_0+\sqrt{d})+P_{n-2}}{Q_{n-1}(a_0+\sqrt{d})+Q_{n-2}}</tex>, отсюда <tex>P_{n-1}a_0+P_{n-1}\sqrt{d}+P_{n-2}=Q_{n-1}d+(Q_{n-1}a_0+Q_{n-2})\sqrt{d}</tex>. Отсюда получаем систему
<tex>x+\sqrt{d}y>2y</tex>. Следовательно <tex>1=x^2-dy^2=(x-\sqrt{d}y)(x+sqrt{d}y)>(x-\sqrt{d}y)2y</tex>. Разделим обе части на <tex>2y^2</tex> получим :
+
<tex>\begin{cases}
<tex>\frac{x}{y}-\sqrt{d} < \frac{1}{2y^2}</tex>. Значит по теореме о приближении <tex>\frac{x}{y}</tex> является подходящей дробью для <tex>\sqrt{d}</tex>.
+
P_{n-2}=Q_{n-1}d-P_{n-1}a_0 \\
 +
Q_{n-2}=P_{n-1}-Q_{n-1}a_0 \\
 +
\end{cases}</tex>
 +
 
 +
Умножаем первое на <tex>Q_{n-1}</tex> и вычитаем второе, умноженное на <tex>P_{n-1}</tex>. Получаем <tex>(-1)^{n+1}=P_{n-2}Q_{n-1}-Q_{n-2}P_{n-1}=Q_{n-1}^2d-P_{n-1}Q_{n-1}a_0-P_{n-1}^2+Q_{n-1}P_{n-1}a_0=Q_{n-1}^2d-P_{n-1}^2</tex>. Если <tex>n</tex> нечётное, то мы нашли решение. Пусть <tex>n</tex> чётное. Тогда <tex>x^2-dy^2=-1\Rightarrow (x-\sqrt{d}y)(x+\sqrt{d}y)=-1</tex>. <tex>(x-\sqrt{d}y)^2=x^2+dy^2-2xy\sqrt{d}</tex> в тоже время <tex>(x-\sqrt{d})^2=\frac{1}{(x+\sqrt{d}y)^2}=\frac{1}{(x^2+dy^2)+2xy\sqrt{d}}</tex>. В итоге получаем <tex>1=(x^2+dy^2-2xy\sqrt{d})(x^2+dy^2+2xy\sqrt{d})=(x^2+dy^2)^2-(2xy)^2d</tex>.
 
}}
 
}}
 +
 +
== Другое доказательство существования решения ==
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Строка 31: Строка 45:
 
Положим <tex>\epsilon=\sqrt{d}</tex>. Для любого натурального <tex>n>1</tex> в силу леммы существуют такие натуральные числа <tex>a_n</tex> и <tex>b_n</tex>, что <tex>b_n < n</tex> и <tex>~|a_n-b_n\sqrt{d}|<\frac{1}{n}</tex>. Далее : <tex>~|a_n^2-db_n^2|=~|a_n-b_n\sqrt{d}|\cdot~|a_n+b_n\sqrt{d}|\leqslant\frac{1}{n}~|a_n-b_n\sqrt{d}+2b_n\sqrt{d}|\leqslant 1+2\sqrt{d}</tex>. Поэтому <tex>a_n^2-db_n^2</tex> принимает конечное число значений. Но <tex>n</tex> принимает бесконечное число значений. Поэтому существует такое число <tex>c</tex>, что для него есть бесконечно много пар <tex>(a_n, b_n)</tex>, таких что <tex>a_n^2-db_n^2=c</tex>.
 
Положим <tex>\epsilon=\sqrt{d}</tex>. Для любого натурального <tex>n>1</tex> в силу леммы существуют такие натуральные числа <tex>a_n</tex> и <tex>b_n</tex>, что <tex>b_n < n</tex> и <tex>~|a_n-b_n\sqrt{d}|<\frac{1}{n}</tex>. Далее : <tex>~|a_n^2-db_n^2|=~|a_n-b_n\sqrt{d}|\cdot~|a_n+b_n\sqrt{d}|\leqslant\frac{1}{n}~|a_n-b_n\sqrt{d}+2b_n\sqrt{d}|\leqslant 1+2\sqrt{d}</tex>. Поэтому <tex>a_n^2-db_n^2</tex> принимает конечное число значений. Но <tex>n</tex> принимает бесконечное число значений. Поэтому существует такое число <tex>c</tex>, что для него есть бесконечно много пар <tex>(a_n, b_n)</tex>, таких что <tex>a_n^2-db_n^2=c</tex>.
  
Рассмотрим остатки от деления на <tex>~|c|</tex> чисел <tex> a_n, b_n</tex>. Количество остатков конечно, а пар бесконечно, поэтому существуют две различные пары <tex> (a_1, b_1),(a_2,b_2)</tex> такие, что <tex>a_1^2-db_1^2=c=a_2^2-вb_2^2</tex> и <tex> a_1\equiv a_2(mod~|c|)</tex>, <tex>b_1\equiv b_2(mod~|c|)</tex>.
+
Рассмотрим остатки от деления на <tex>~|c|</tex> чисел <tex> a_n, b_n</tex>. Количество остатков конечно, а пар бесконечно, поэтому существуют две различные пары <tex> (a_1, b_1),(a_2,b_2)</tex> такие, что <tex>a_1^2-db_1^2=c=a_2^2-db_2^2</tex> и <tex> a_1\equiv a_2(mod~|c|)</tex>, <tex>b_1\equiv b_2(mod~|c|)</tex>.
  
 
<tex>\frac{a_2+b_2\sqrt{d}}{a_1+b_1\sqrt{d}}=\frac{(a_1-b_1\sqrt{d})(a_2+b_2\sqrt{d})}{a_1^2-db_1^2}=\frac{(a_1a_2-db_1b_2)+(a_1b_2-a_2b_1)\sqrt{d}}{c}</tex>.  
 
<tex>\frac{a_2+b_2\sqrt{d}}{a_1+b_1\sqrt{d}}=\frac{(a_1-b_1\sqrt{d})(a_2+b_2\sqrt{d})}{a_1^2-db_1^2}=\frac{(a_1a_2-db_1b_2)+(a_1b_2-a_2b_1)\sqrt{d}}{c}</tex>.  
Строка 39: Строка 53:
 
Поскольку <tex>a_1a_2-db_1b_2\equiv a_1^2-b_1^2d\equiv c\equiv 0(mod~|c|)</tex> и <tex>a_1b_2-a_2b_1\equiv a_1b_1-a_1b_1 \equiv 0(mod~|c|)</tex>, то числа <tex> x = \frac{a_1a_2-b_1b_2d}{c}</tex> и <tex>y = \frac{a_1b_2-a_2b_1}{c}</tex> целые. <tex>x^2-dy^2=(x-y\sqrt{d})(x+y\sqrt{d}) = \frac{a_2-b_2\sqrt{d}}{a_1-b_1\sqrt{d}}\frac{a_2+b_2\sqrt{d}}{a_1+b_1\sqrt{d}} = \frac{a_2^2-db_2^2}{a_1^2-db_1^2}=\frac{c}{c}=1</tex>. Поэтому <tex>(x, y) </tex> - искомое нетривиальное решение уравнения Пелля.
 
Поскольку <tex>a_1a_2-db_1b_2\equiv a_1^2-b_1^2d\equiv c\equiv 0(mod~|c|)</tex> и <tex>a_1b_2-a_2b_1\equiv a_1b_1-a_1b_1 \equiv 0(mod~|c|)</tex>, то числа <tex> x = \frac{a_1a_2-b_1b_2d}{c}</tex> и <tex>y = \frac{a_1b_2-a_2b_1}{c}</tex> целые. <tex>x^2-dy^2=(x-y\sqrt{d})(x+y\sqrt{d}) = \frac{a_2-b_2\sqrt{d}}{a_1-b_1\sqrt{d}}\frac{a_2+b_2\sqrt{d}}{a_1+b_1\sqrt{d}} = \frac{a_2^2-db_2^2}{a_1^2-db_1^2}=\frac{c}{c}=1</tex>. Поэтому <tex>(x, y) </tex> - искомое нетривиальное решение уравнения Пелля.
 
}}
 
}}
 +
 +
[[Категория:Теория чисел]]

Текущая версия на 19:18, 4 сентября 2022

Определение:
Уравнение вида [math]x^2-dy^2=1[/math], где [math]d\in\mathbb{N}[/math] не является квадратом, называется уравнением Пелля. Как правило, стоит задача поиска всех целых корней этого уравнения при данном [math]d[/math].


У этого уравнения есть тривиальное решение [math]x=1, y=0[/math].

Теорема:
Любое решение уравнения Пелля — подходящая дробь для [math]\sqrt{d}[/math].
Доказательство:
[math]\triangleright[/math]

Рассматриваем [math]x,y\gt 0[/math], остальные корни получатся из симметрии. Так как [math]\sqrt{d}\geqslant 1[/math], то [math]x\gt y\gt 0[/math]. [math]x+\sqrt{d}y\gt 2y[/math]. Следовательно [math]1=x^2-dy^2=(x-\sqrt{d}y)(x+\sqrt{d}y)\gt (x-\sqrt{d}y)2y[/math]. Разделим обе части на [math]2y^2[/math] получим :

[math]\frac{x}{y}-\sqrt{d} \lt \frac{1}{2y^2}[/math]. Значит по теореме о приближении [math]\frac{x}{y}[/math] является подходящей дробью для [math]\sqrt{d}[/math].
[math]\triangleleft[/math]

Существование решения уравнения Пелля

Теорема:
Уравнение Пелля имеет нетривиальное решение. Доказательство через цепные дроби.
Доказательство:
[math]\triangleright[/math]

Разложим [math]\sqrt{d}[/math] в цепную дробь. [math] \sqrt{d}=a_0+\frac{1}{a_1+\cdots+\frac{1}{a_0+\sqrt{d}}}[/math]. Значит [math]\sqrt{d}=\frac{P_{n-1}(a_0+\sqrt{d})+P_{n-2}}{Q_{n-1}(a_0+\sqrt{d})+Q_{n-2}}[/math], отсюда [math]P_{n-1}a_0+P_{n-1}\sqrt{d}+P_{n-2}=Q_{n-1}d+(Q_{n-1}a_0+Q_{n-2})\sqrt{d}[/math]. Отсюда получаем систему [math]\begin{cases} P_{n-2}=Q_{n-1}d-P_{n-1}a_0 \\ Q_{n-2}=P_{n-1}-Q_{n-1}a_0 \\ \end{cases}[/math]

Умножаем первое на [math]Q_{n-1}[/math] и вычитаем второе, умноженное на [math]P_{n-1}[/math]. Получаем [math](-1)^{n+1}=P_{n-2}Q_{n-1}-Q_{n-2}P_{n-1}=Q_{n-1}^2d-P_{n-1}Q_{n-1}a_0-P_{n-1}^2+Q_{n-1}P_{n-1}a_0=Q_{n-1}^2d-P_{n-1}^2[/math]. Если [math]n[/math] нечётное, то мы нашли решение. Пусть [math]n[/math] чётное. Тогда [math]x^2-dy^2=-1\Rightarrow (x-\sqrt{d}y)(x+\sqrt{d}y)=-1[/math]. [math](x-\sqrt{d}y)^2=x^2+dy^2-2xy\sqrt{d}[/math] в тоже время [math](x-\sqrt{d})^2=\frac{1}{(x+\sqrt{d}y)^2}=\frac{1}{(x^2+dy^2)+2xy\sqrt{d}}[/math]. В итоге получаем [math]1=(x^2+dy^2-2xy\sqrt{d})(x^2+dy^2+2xy\sqrt{d})=(x^2+dy^2)^2-(2xy)^2d[/math].
[math]\triangleleft[/math]

Другое доказательство существования решения

Лемма:
Для любого вещественного числа [math] \epsilon[/math] и натурального [math]N[/math] существует такое целое число [math] a [/math] и натуральное число [math] b [/math], что [math]b\leqslant N[/math] и [math] ~|b\epsilon - a|\leqslant \frac{1}{N+1}[/math]
Доказательство:
[math]\triangleright[/math]

Рассмотрим числа 0 и 1, а также дробные части чисел [math]\epsilon, 2\epsilon, \cdots, N\epsilon[/math]. Если все расстояния между этими [math]N+2[/math] числами было больше [math]\frac{1}{N+1}[/math], то приходим к противоречию. Значит какое-то из расстояний не превосходит [math]\frac{1}{N+1}[/math].

Если [math]~|{b2\epsilon} - {b1\epsilon}|\leqslant \frac{1}{N+1}[/math], где [math]1\leqslant b1 \lt b2 \leqslant N[/math], то [math]~|(b2\epsilon-[b2\epsilon]) - (b1\epsilon-[b1\epsilon])| \leqslant \frac{1}{N+1}[/math]. Так что берём [math]b = b2-b1[/math] и [math]a = [b2\epsilon]-[b1\epsilon] [/math]. Два других случая очевидны.
[math]\triangleleft[/math]
Теорема:
Уравнение Пелля имеет нетривиальное решение.
Доказательство:
[math]\triangleright[/math]

Положим [math]\epsilon=\sqrt{d}[/math]. Для любого натурального [math]n\gt 1[/math] в силу леммы существуют такие натуральные числа [math]a_n[/math] и [math]b_n[/math], что [math]b_n \lt n[/math] и [math]~|a_n-b_n\sqrt{d}|\lt \frac{1}{n}[/math]. Далее : [math]~|a_n^2-db_n^2|=~|a_n-b_n\sqrt{d}|\cdot~|a_n+b_n\sqrt{d}|\leqslant\frac{1}{n}~|a_n-b_n\sqrt{d}+2b_n\sqrt{d}|\leqslant 1+2\sqrt{d}[/math]. Поэтому [math]a_n^2-db_n^2[/math] принимает конечное число значений. Но [math]n[/math] принимает бесконечное число значений. Поэтому существует такое число [math]c[/math], что для него есть бесконечно много пар [math](a_n, b_n)[/math], таких что [math]a_n^2-db_n^2=c[/math].

Рассмотрим остатки от деления на [math]~|c|[/math] чисел [math] a_n, b_n[/math]. Количество остатков конечно, а пар бесконечно, поэтому существуют две различные пары [math] (a_1, b_1),(a_2,b_2)[/math] такие, что [math]a_1^2-db_1^2=c=a_2^2-db_2^2[/math] и [math] a_1\equiv a_2(mod~|c|)[/math], [math]b_1\equiv b_2(mod~|c|)[/math].

[math]\frac{a_2+b_2\sqrt{d}}{a_1+b_1\sqrt{d}}=\frac{(a_1-b_1\sqrt{d})(a_2+b_2\sqrt{d})}{a_1^2-db_1^2}=\frac{(a_1a_2-db_1b_2)+(a_1b_2-a_2b_1)\sqrt{d}}{c}[/math].

[math]\frac{a_2-b_2\sqrt{d}}{a_1-b_1\sqrt{d}}=\frac{(a_1+b_1\sqrt{d})(a_2-b_2\sqrt{d})}{a_1^2-db_1^2}=\frac{(a_1a_2-db_1b_2)-(a_1b_2-a_2b_1)\sqrt{d}}{c}[/math].

Поскольку [math]a_1a_2-db_1b_2\equiv a_1^2-b_1^2d\equiv c\equiv 0(mod~|c|)[/math] и [math]a_1b_2-a_2b_1\equiv a_1b_1-a_1b_1 \equiv 0(mod~|c|)[/math], то числа [math] x = \frac{a_1a_2-b_1b_2d}{c}[/math] и [math]y = \frac{a_1b_2-a_2b_1}{c}[/math] целые. [math]x^2-dy^2=(x-y\sqrt{d})(x+y\sqrt{d}) = \frac{a_2-b_2\sqrt{d}}{a_1-b_1\sqrt{d}}\frac{a_2+b_2\sqrt{d}}{a_1+b_1\sqrt{d}} = \frac{a_2^2-db_2^2}{a_1^2-db_1^2}=\frac{c}{c}=1[/math]. Поэтому [math](x, y) [/math] - искомое нетривиальное решение уравнения Пелля.
[math]\triangleleft[/math]