密码中的数学系列——连分数定理

其中也用到了辗转相除法的思想

定义

当a和b满足

$$|x-\frac{a}{b}|<\frac{1}{2\cdot b^2}$$

时，则$\frac{a}{b}$是x的一个连分数近似。

例子

把 $\frac{1314}{520}$ 进行连分数展开，形式就是对分子分母做辗转相除。

$$\begin{align*} \frac{1314}{520} &= 2+\frac{274}{520}\\\\ \frac{520}{274} ~&= 1+\frac{246}{274}\\\\ \frac{274}{246} ~&=1+\frac{32}{246}\\\\ \frac{246}{32} ~&=7+\frac{22}{32}\\\\ \frac{32}{22} ~&=1+\frac{10}{22}\\\\ \frac{22}{10} ~&=2+\frac{2}{10}\\\\ \frac{10}{2} ~&=5+0 \end{align*}$$

所以 $\frac{1314}{520}$ 展开连分数为

$$\frac{1314}{520}=2+\frac{1}{1+\frac{1}{1+\frac{1}{7+\frac{1}{1+\frac{1}{2+\frac{1}{5+0}}}}}}$$

运用

可以从上面一个例子看出，

我们通过连分数展开可以轻松知道每一层的分子与分母，如果对无理数或者两个很大的数字分数进行连分数展开，那么我们会得到很多很多层分子分母，此时就可以只拿较多的层数，然后计算成一个分数，得到其的一个近似值

还是 $\frac{1314}{520}$ ，我们从连分数展开的第四层断开，即把7后面的分式约等于0

有

$$\begin{align*} \frac{1314}{520}&\approx2+\frac{1}{1+\frac{1}{1+\frac{1}{7+0}}}\\ &=2+\frac{1}{1+\frac{1}{\frac{8}{7}}}\\ &=2+\frac{1}{\frac{15}{8}}\\ &=\frac{38}{15} \end{align*}$$

即 $\frac{1314}{520}$ 的近似值为 $\frac{38}{15}$

这么，我们可以从一个小数中拿到其近似值的分子与分母，也可以从一个分数中提取分子与分母