欧几里德算法和连续有理分式展开

Here are some definitions of continued fractions we'll be using.

To find a contined fraction of a rational number, we find the largest integer from whatever is remaining, and then reduce it to a similar problem, except smaller. For example, to find the continued fraction of $\frac{29}{13}$, we know that the largest integer less than $\frac{29}{13}$ is $2$. So, we know $$\dfrac{29}{13}=2+\dfrac{1}{x}$$ for some $x$. We solve the equation for $x$, to get $$\dfrac{13}{3}=x.$$ Then, we continue similarly to get $$x=4+\dfrac{1}{3}.$$ So, when we plug this back in to our first equation, we have $$\dfrac{29}{13}=2+\dfrac{1}{4+\dfrac{1}{3}}=[2,4,3].$$

Right! In the division algorithm, we find the largest multiple less than some integer and then the remainder. Let's try to see if these two processes are related.

Let's use our previous example so that we don't need to do as much work. We use the Euclidean algorithm, which is the division algorithm iterated repeatedly to divide $29$ by $13$: $$29=13(2)+3$$ $$13=3(4)+1$$ $$3=1(3)+0$$

Wow! Isn't that a surprise? The quotients we get are exactly the numbers in the continued fraction! Let's try to figure out why this works.

Where would $\frac{29}{13}$ come from in the first place? Well, the only equation that has both $29$ and $13$ is the first one, so let's try to get a $\frac{29}{13}$. $$29=13(2)+3\implies \frac{29}{13}=2+\frac{3}{13}.$$ This is exactly what we needed! Now we proceed in a similar fashion to find $\frac{3}{13}$. $$13=3(4)+1\implies \frac{3}{13}=\dfrac{1}{\frac{13}{3}}=\dfrac{1}{4+\frac{1}{3}}.$$ We substitute this and we get $$\dfrac{29}{13}=2+\dfrac{1}{4+\dfrac{1}{3}}.$$

Great! Now it's time to try to formulate a proof.

Suppose we have the following equations: $$a=bq_1+r_1$$ $$b=r_1q_2+r_2$$ $$r_1=r_2q_3+r_3$$ $$\vdots$$ $$r_{n-2}=r_{n-1}q_n+r_n$$ Then, we can rearrange each of them so that we have what we want: $$a=bq_1+r_1\implies \frac{a}{b}=q_1+\frac{r_1}{b}$$ $$b=r_1q_2+r_2\implies \frac{b}{r_1}=q_2+\frac{r_2}{r_1}$$ $$r_1=r_2q_3+r_3\implies \frac{r_1}{r_2}=q_3+\frac{r_3}{r_2}$$ $$\vdots\qquad\qquad\qquad\qquad\vdots$$ $$r_{n-2}=r_{n-1}q_n+r_n\implies \frac{r_{n-2}}{r_{n-1}}=q_n+\frac{r_n}{r_{n-1}}.$$

Now, it's time to substitute repeatedly. $$\begin{align} \dfrac{a}{b}&=q_1+\dfrac{1}{q_2+\frac{r_2}{r_1}}\\ &=q_1+\dfrac{1}{q_2+\dfrac{1}{q_3+\frac{r_3}{r_2}}}\\ &\qquad\qquad \vdots\\ &=q_1+\dfrac{1}{q_2+\dfrac{1}{\ddots+\dfrac{1}{q_n}}}\\ &=[q_1,q_2,\cdots,q_n]. \end{align}$$ This is exactly what we wanted to prove.