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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
  
 
<tex>a=bq_1+r_1, \frac{a}{b}=q_1+\frac{1}{(\frac{b}{r_1})}</tex>
 
<tex>a=bq_1+r_1, \frac{a}{b}=q_1+\frac{1}{(\frac{b}{r_1})}</tex>
 +
 +
<tex>b=r_1q_2+r_2, \frac{b}{r_1}=q_2 + \frac{1}{(\frac{r_1}{r_2})}</tex>
 +
 +
<tex>r_1=r_2q_3+r_3, \frac{r_1}{r_2}=q_3+\frac{1}{(\frac{r_2}{r_3})}</tex>
 +
 +
<tex>\cdots</tex>
 +
 +
<tex>r_{n-2}=r_{n-1}q_n+r_n, \frac{r_{n-2}}{r_{n-1}}=q_n+\frac{1}{(\frac{r_{n-1}}{r_n})}</tex>
 +
 +
<tex>r_{n-1}=r_nq_{n+1}, \frac{r_{n-1}}{r_n}=q_{n+1}</tex>
 +
 +
Следовательно :
 +
 +
<tex>\frac{a}{b}=q_1+\frac{1}{q_2+\frac{1}{q_3+\cdots+\frac{1}{q_n+\frac{1}{q_{n+1}}}}} = \langle q_1, q_2,\cdots, q_{n+1}\rangle</tex>

Версия 18:30, 30 июня 2010

Эта статья находится в разработке!

Пусть [math]\alpha\in\mathbb{Q}, \alpha=\frac{a}{b}, a, b \in \mathbb{Z}, b\gt 0[/math]. При данных условиях разложение дроби [math]\frac{a}{b}[/math] эквивалентно алгоритму Евклида для чисел [math]a[/math] и [math]b[/math]:

[math]a=bq_1+r_1, \frac{a}{b}=q_1+\frac{1}{(\frac{b}{r_1})}[/math]

[math]b=r_1q_2+r_2, \frac{b}{r_1}=q_2 + \frac{1}{(\frac{r_1}{r_2})}[/math]

[math]r_1=r_2q_3+r_3, \frac{r_1}{r_2}=q_3+\frac{1}{(\frac{r_2}{r_3})}[/math]

[math]\cdots[/math]

[math]r_{n-2}=r_{n-1}q_n+r_n, \frac{r_{n-2}}{r_{n-1}}=q_n+\frac{1}{(\frac{r_{n-1}}{r_n})}[/math]

[math]r_{n-1}=r_nq_{n+1}, \frac{r_{n-1}}{r_n}=q_{n+1}[/math]

Следовательно :

[math]\frac{a}{b}=q_1+\frac{1}{q_2+\frac{1}{q_3+\cdots+\frac{1}{q_n+\frac{1}{q_{n+1}}}}} = \langle q_1, q_2,\cdots, q_{n+1}\rangle[/math]