Связь цепных дробей и алгоритма Евклида — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показаны 4 промежуточные версии 4 участников) | |||
Строка 1: | Строка 1: | ||
− | + | Пусть <tex>\alpha\in\mathbb{Q}</tex> {{---}} рациональное число. Тогда ее разложение в [[цепная дробь|цепную дробь]] соответствует [[алгоритм Евклида|алгоритму Евклида]]. В самом деле, пусть <tex>\alpha=\frac{a}{b}, a, b \in \mathbb{Z}, b>0</tex>. Применим алгоритм Еквлида к числам <tex>a</tex> и <tex>b</tex>. | |
− | |||
− | |||
− | |||
− | Пусть <tex>\alpha\in\mathbb{Q}, \alpha=\frac{a}{b}, a, b \in \mathbb{Z}, b>0</tex>. | ||
На первом шаге получаем число <tex>r_1</tex>. | На первом шаге получаем число <tex>r_1</tex>. | ||
− | + | :<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>\frac{b}{r_1}</tex>. | На втором шаге попробуем узнать <tex>\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>b=r_1q_2+r_2, \frac{b}{r_1}=q_2 + \frac{1}{(\frac{r_1}{r_2})}</tex> | ||
− | |||
На следующих шагах узнаем <tex>\frac{r_i}{r_{i+1}}</tex> | На следующих шагах узнаем <tex>\frac{r_i}{r_{i+1}}</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+\cdots+\frac{1}{q_n+\frac{1}{q_{n+1}}}} = \langle q_1, q_2,\cdots, q_{n+1}\rangle</tex> | |
− | + | :<tex>q_1, q_2,\cdots, q_n</tex> {{---}} неполные частные из алгоритма Евклида | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | Последовательно подставляя, получаем : | ||
− | |||
− | <tex>\frac{a}{b}=q_1+\frac{1}{q_2+\cdots+\frac{1}{q_n+\frac{1}{q_{n+1}}}} = \langle q_1, q_2,\cdots, q_{n+1}\rangle</tex> | ||
− | |||
− | <tex>q_1, q_2,\cdots, q_n</tex> {{---}} неполные частные из алгоритма Евклида | ||
[[Категория:Теория чисел]] | [[Категория:Теория чисел]] |
Текущая версия на 19:35, 4 сентября 2022
Пусть цепную дробь соответствует алгоритму Евклида. В самом деле, пусть . Применим алгоритм Еквлида к числам и .
— рациональное число. Тогда ее разложение вНа первом шаге получаем число
.На втором шаге попробуем узнать
.На следующих шагах узнаем
Последовательно подставляя, получаем:
- — неполные частные из алгоритма Евклида