Периодичность цепных дробей — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 11 промежуточных версий 3 участников)
Строка 1: Строка 1:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Пусть <tex>\alpha</tex> приведённая квадратичная иррациональность, тогда её цепная дробь периодична.
+
Пусть <tex>\alpha</tex> приведённая [[квадратичная иррациональность]], тогда её [[цепная дробь]] периодична.
 
|proof=
 
|proof=
Число <tex>\alpha</tex> представимо в виде <tex>\frac{a+\sqrt{D}}{c}, a,c,D \in \mathbb{Z}</tex>. Назовём это видом Х.
+
Число <tex>\alpha</tex> представимо в виде <tex>\frac{a+\sqrt{D}}{c}, a,c,D \in \mathbb{Z}</tex> и <tex>a^2-D\vdots c</tex>. Назовём это видом Х.
  
Рассмотрим <tex>\alpha_1=\frac{1}{\alpha-q}, q=[\alpha]</tex>. Заметим, что <tex>\alpha_1>1</tex>. Преобразуем: <tex>\alpha_1=\frac{c}{a+\sqrt{D}-qc}=\frac{c(a-qc-\sqrt{D})}{(a-qc)^2-D}</tex>. Заметим, что <tex>(a-qc)^2-D\vdots c</tex>, значит <tex>\alpha_1</tex> представима в виде Х. Докажем, что <tex>\alpha_1</tex> приведённая. <tex>\overline{\alpha_1}=\frac{1}{\overline{\alpha}-[\alpha]}</tex>. Но <tex>\overline{\alpha}\in (-1;0), [alpha]>1</tex>, значит <tex>\overline{\alpha_1}\in(-1;0)</tex>.
+
Рассмотрим <tex>\alpha_1=\frac{1}{\alpha-q}, q=[\alpha]</tex>. Заметим, что <tex>\alpha_1>1</tex>. Преобразуем: <tex>\alpha_1=\frac{c}{a+\sqrt{D}-qc}=\frac{c(a-qc-\sqrt{D})}{(a-qc)^2-D}</tex>. Заметим, что <tex>(a-qc)^2-D\vdots c</tex>, значит <tex>\alpha_1</tex> представима в виде Х, где <tex>a'=(qc-a), c'=\frac{D-(a-qc)^2}{c}</tex> Докажем, что <tex>\alpha_1</tex> приведённая. <tex>\overline{\alpha_1}=\frac{1}{\overline{\alpha}-[\alpha]}</tex>. Но <tex>\overline{\alpha}\in (-1;0), [\alpha]>1</tex>, значит <tex>\overline{\alpha_1}\in(-1;0)</tex>.
  
Посмотрим теперь на возможные значения <tex>a</tex> и <tex>c</tex>. <tex>\alpha-\overline{\alpha}=\frac{2\sqrt{D}}{c}</tex>, откуда из возможных значения <tex>\alpha, \overline{\alpha}</tex>, следует <tex>c\in(0;2\sqrt{D})</tex>. Теперь ограничим a. <tex>\alpha+\overline{\alpha}=\frac{2a}{c}</tex>, отсюда <tex>a>0</tex>. <tex>\overline{\alpha}=\frac{a-\sqrt{D}}{c}\Rightarrow a < \sqrt{D}</tex>.
+
Посмотрим теперь на возможные значения <tex>a</tex> и <tex>c</tex>. <tex>\alpha-\overline{\alpha}=\frac{2\sqrt{D}}{c}</tex>, откуда из возможных значений <tex>\alpha, \overline{\alpha}</tex>, следует <tex>c\in(0;2\sqrt{D})</tex>. Теперь ограничим a. <tex>\alpha+\overline{\alpha}=\frac{2a}{c}</tex>, отсюда <tex>a>0</tex>. <tex>\overline{\alpha}=\frac{a-\sqrt{D}}{c}\Rightarrow a < \sqrt{D}</tex>.
  
 
Количество <tex>a,c</tex> конечно, а количество<tex>\alpha_n</tex> неограниченно. Значит в какой-то момент у нас зациклятся <tex>\alpha_n</tex> и цепная дробь станет периодичной.
 
Количество <tex>a,c</tex> конечно, а количество<tex>\alpha_n</tex> неограниченно. Значит в какой-то момент у нас зациклятся <tex>\alpha_n</tex> и цепная дробь станет периодичной.
 
}}
 
}}
 
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Строка 20: Строка 19:
 
Введём <tex>\beta_i=-\frac{1}{(\overline{\alpha_i})}\in(1;+\infty) \Rightarrow \alpha_i=-\frac{1}{(\overline{\beta_i})}</tex>.
 
Введём <tex>\beta_i=-\frac{1}{(\overline{\alpha_i})}\in(1;+\infty) \Rightarrow \alpha_i=-\frac{1}{(\overline{\beta_i})}</tex>.
  
<tex>\alpha_n=a_n+\frac{1}{\alpha_{n+1}}</tex> отсюда <tex>-\frac{1}{(\overline{\beta_n})}=a_n-\overline{\beta_{n+1}}\Rightarrow\overline{\beta_{n+1}}=a_n+\frac{1}{(\overline{\beta_n})}</tex>
+
<tex>\alpha_n=a_n+\frac{1}{\alpha_{n+1}}</tex> отсюда <tex>-\frac{1}{(\overline{\beta_n})}=a_n-\overline{\beta_{n+1}}\Rightarrow\overline{\beta_{n+1}}=a_n+\frac{1}{(\overline{\beta_n})}</tex>. Получаем, что <tex>\beta_{n+1}=a_n+\frac{1}{\beta_n}\Rightarrow[\beta_{n+1}]=a_n</tex>
 +
 
 +
Осталось только записать переходы <tex>\alpha_n=\alpha_m\Rightarrow\beta_n=\beta_m\Rightarrow a_{n-1}=a_{m-1}\Rightarrow\alpha_{n-1}=\alpha_{m-1}</tex>
 
}}
 
}}
 +
{{Теорема
 +
|author=Лагранж
 +
|statement=
 +
Число <tex>\alpha</tex> представимо в виде периодической цепной дроби тогда и только тогда, когда <tex>\alpha</tex> квадратичная иррациональность.
 +
|proof=
 +
<tex>\Rightarrow</tex>.
 +
 +
<tex>\alpha=\langle a_0,a_1,\cdots,\overline{a_k,\cdots a_n}\rangle</tex>, тогда введём <tex>\alpha_k=\langle \overline{a_k,\cdots, a_n}\rangle</tex>. Тогда <tex>\alpha_k=\langle a_k,\cdots, a_n, \overline{\alpha_k} \rangle</tex>. <tex>\alpha_k=\frac{P_n'\alpha_k+P_{n-1}'}{Q_n'\alpha_k+Q_{n-1}'}\Rightarrow Q_n'\alpha_k^2+(P_n'+Q_{n-1}')\alpha_k+P_{n-1}'=0</tex>
 +
Поэтому <tex>\alpha_k</tex> квадратичная иррациональность, так как иррационально и удовлетворяет уравнению с целыми коэффициентами. Аналогично получим, что <tex>\alpha = \frac{P_k\alpha_k+P_{k-1}}{Q_k\alpha_k+Q_{k-1}}</tex>. Поэтому и <tex>\alpha</tex> квадратичная иррациональность.
 +
 +
<tex>\Leftarrow</tex>.
 +
 +
Пусть <tex>a\alpha^2+b\alpha+c=0</tex>. Разложим <tex>\alpha</tex> в цепную дробь и для <tex>\forall k:\alpha=\frac{P_k\alpha_k+P_{k-1}}{Q_k\alpha_k+Q_{k-1}}</tex>. Подставим в уравнение и заменим коэффициенты <tex>A_k\alpha_k^2+B_k\alpha_k+C_k=0</tex>. Где <tex>A_k=aP_k^2+bP_kQ_k+cQ_k^2</tex>, <tex>B_k=2aP_kP_{k-1}+bP_{k-1}Q_k+bP_kQ_{k-1}+2cQ_kQ_{k-1}</tex> и <tex>C_k=aP_{k-1}^2+bP_{k-1}Q_{k-1}+cQ_{k-1}^2</tex>. Вычислим и упростим дискриминант и получим: <tex>B_k^2-4A_kC_k=b^2-4ac</tex>.
 +
 +
Ограничим <tex>A_k,B_k,C_k</tex>. По тому, что <tex>~|\alpha-\frac{P_k}{Q_k}|<\frac{1}{Q_k^2}</tex> имеем <tex>\frac{P_k}{Q_k}=\alpha-\frac{\epsilon}{Q_k^2},\epsilon\in(-1;1)</tex>.
 +
Отсюда <tex>\frac{A_k}{Q_k^2}=a(\frac{P_k}{Q_k})^2+b(\frac{P_k}{Q_k})+c=a\alpha^2+b\alpha+c-2a\alpha\frac{\epsilon}{Q_k^2}+a\frac{\epsilon^2}{Q_k^4}-b\frac{\epsilon}{Q_k^2}</tex>. Отсюда <tex>A_k=-2a\alpha\epsilon+a\epsilon-b\epsilon\Rightarrow~|A_k|\leqslant~|2a\alpha|+~|a|+~|b|</tex>. Далее <tex>C_k = A_{k-1}</tex>, значит тоже ограничено. Теперь <tex>B_k^2-4A_kC_k=b^2-4ac</tex> следовательно <tex>B_k^2\leqslant 4~|A_kC_k|+~|b^2-4ac|<4(2~|a\alpha|+~|a|+|b|)^2+~|b^2-4ac|</tex>. То есть коэффициенты ограничены, но <tex>k</tex> принимает бесконечное число значений, значит <tex>\exists i,j:\alpha_i=\alpha_j; i>j</tex> значит цепная дробь периодична.
 +
}}
 +
 +
[[Категория:Теория чисел]]

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

Теорема:
Пусть [math]\alpha[/math] приведённая квадратичная иррациональность, тогда её цепная дробь периодична.
Доказательство:
[math]\triangleright[/math]

Число [math]\alpha[/math] представимо в виде [math]\frac{a+\sqrt{D}}{c}, a,c,D \in \mathbb{Z}[/math] и [math]a^2-D\vdots c[/math]. Назовём это видом Х.

Рассмотрим [math]\alpha_1=\frac{1}{\alpha-q}, q=[\alpha][/math]. Заметим, что [math]\alpha_1\gt 1[/math]. Преобразуем: [math]\alpha_1=\frac{c}{a+\sqrt{D}-qc}=\frac{c(a-qc-\sqrt{D})}{(a-qc)^2-D}[/math]. Заметим, что [math](a-qc)^2-D\vdots c[/math], значит [math]\alpha_1[/math] представима в виде Х, где [math]a'=(qc-a), c'=\frac{D-(a-qc)^2}{c}[/math] Докажем, что [math]\alpha_1[/math] приведённая. [math]\overline{\alpha_1}=\frac{1}{\overline{\alpha}-[\alpha]}[/math]. Но [math]\overline{\alpha}\in (-1;0), [\alpha]\gt 1[/math], значит [math]\overline{\alpha_1}\in(-1;0)[/math].

Посмотрим теперь на возможные значения [math]a[/math] и [math]c[/math]. [math]\alpha-\overline{\alpha}=\frac{2\sqrt{D}}{c}[/math], откуда из возможных значений [math]\alpha, \overline{\alpha}[/math], следует [math]c\in(0;2\sqrt{D})[/math]. Теперь ограничим a. [math]\alpha+\overline{\alpha}=\frac{2a}{c}[/math], отсюда [math]a\gt 0[/math]. [math]\overline{\alpha}=\frac{a-\sqrt{D}}{c}\Rightarrow a \lt \sqrt{D}[/math].

Количество [math]a,c[/math] конечно, а количество[math]\alpha_n[/math] неограниченно. Значит в какой-то момент у нас зациклятся [math]\alpha_n[/math] и цепная дробь станет периодичной.
[math]\triangleleft[/math]
Теорема:
Пусть [math]\alpha[/math] приведённая квадратичная иррациональность, тогда её цепная дробь чисто периодична.
Доказательство:
[math]\triangleright[/math]

Докажем аналогичное утверждение [math]\alpha_n=\alpha_m\Rightarrow\alpha_{n-1}=\alpha_{m-1}[/math].

Введём [math]\beta_i=-\frac{1}{(\overline{\alpha_i})}\in(1;+\infty) \Rightarrow \alpha_i=-\frac{1}{(\overline{\beta_i})}[/math].

[math]\alpha_n=a_n+\frac{1}{\alpha_{n+1}}[/math] отсюда [math]-\frac{1}{(\overline{\beta_n})}=a_n-\overline{\beta_{n+1}}\Rightarrow\overline{\beta_{n+1}}=a_n+\frac{1}{(\overline{\beta_n})}[/math]. Получаем, что [math]\beta_{n+1}=a_n+\frac{1}{\beta_n}\Rightarrow[\beta_{n+1}]=a_n[/math]

Осталось только записать переходы [math]\alpha_n=\alpha_m\Rightarrow\beta_n=\beta_m\Rightarrow a_{n-1}=a_{m-1}\Rightarrow\alpha_{n-1}=\alpha_{m-1}[/math]
[math]\triangleleft[/math]
Теорема (Лагранж):
Число [math]\alpha[/math] представимо в виде периодической цепной дроби тогда и только тогда, когда [math]\alpha[/math] квадратичная иррациональность.
Доказательство:
[math]\triangleright[/math]

[math]\Rightarrow[/math].

[math]\alpha=\langle a_0,a_1,\cdots,\overline{a_k,\cdots a_n}\rangle[/math], тогда введём [math]\alpha_k=\langle \overline{a_k,\cdots, a_n}\rangle[/math]. Тогда [math]\alpha_k=\langle a_k,\cdots, a_n, \overline{\alpha_k} \rangle[/math]. [math]\alpha_k=\frac{P_n'\alpha_k+P_{n-1}'}{Q_n'\alpha_k+Q_{n-1}'}\Rightarrow Q_n'\alpha_k^2+(P_n'+Q_{n-1}')\alpha_k+P_{n-1}'=0[/math] Поэтому [math]\alpha_k[/math] квадратичная иррациональность, так как иррационально и удовлетворяет уравнению с целыми коэффициентами. Аналогично получим, что [math]\alpha = \frac{P_k\alpha_k+P_{k-1}}{Q_k\alpha_k+Q_{k-1}}[/math]. Поэтому и [math]\alpha[/math] квадратичная иррациональность.

[math]\Leftarrow[/math].

Пусть [math]a\alpha^2+b\alpha+c=0[/math]. Разложим [math]\alpha[/math] в цепную дробь и для [math]\forall k:\alpha=\frac{P_k\alpha_k+P_{k-1}}{Q_k\alpha_k+Q_{k-1}}[/math]. Подставим в уравнение и заменим коэффициенты [math]A_k\alpha_k^2+B_k\alpha_k+C_k=0[/math]. Где [math]A_k=aP_k^2+bP_kQ_k+cQ_k^2[/math], [math]B_k=2aP_kP_{k-1}+bP_{k-1}Q_k+bP_kQ_{k-1}+2cQ_kQ_{k-1}[/math] и [math]C_k=aP_{k-1}^2+bP_{k-1}Q_{k-1}+cQ_{k-1}^2[/math]. Вычислим и упростим дискриминант и получим: [math]B_k^2-4A_kC_k=b^2-4ac[/math].

Ограничим [math]A_k,B_k,C_k[/math]. По тому, что [math]~|\alpha-\frac{P_k}{Q_k}|\lt \frac{1}{Q_k^2}[/math] имеем [math]\frac{P_k}{Q_k}=\alpha-\frac{\epsilon}{Q_k^2},\epsilon\in(-1;1)[/math].

Отсюда [math]\frac{A_k}{Q_k^2}=a(\frac{P_k}{Q_k})^2+b(\frac{P_k}{Q_k})+c=a\alpha^2+b\alpha+c-2a\alpha\frac{\epsilon}{Q_k^2}+a\frac{\epsilon^2}{Q_k^4}-b\frac{\epsilon}{Q_k^2}[/math]. Отсюда [math]A_k=-2a\alpha\epsilon+a\epsilon-b\epsilon\Rightarrow~|A_k|\leqslant~|2a\alpha|+~|a|+~|b|[/math]. Далее [math]C_k = A_{k-1}[/math], значит тоже ограничено. Теперь [math]B_k^2-4A_kC_k=b^2-4ac[/math] следовательно [math]B_k^2\leqslant 4~|A_kC_k|+~|b^2-4ac|\lt 4(2~|a\alpha|+~|a|+|b|)^2+~|b^2-4ac|[/math]. То есть коэффициенты ограничены, но [math]k[/math] принимает бесконечное число значений, значит [math]\exists i,j:\alpha_i=\alpha_j; i\gt j[/math] значит цепная дробь периодична.
[math]\triangleleft[/math]