具体数学-第11课（Stern-Brocot树和同余关系）

原文链接：

具体数学-第11课 - WeiYang Bloggodweiyang.com

Stern-Brocot树

我们接着上节课讲到的Stern-Brocot树继续往下讲。

LR序列表示

对于任意分数

，我们从

开始走到它所在的结点。如果向左走就记为L，向右走记为R，最终可以得到一个L和R的序列。例如

的表示就是LRRL。

这种表示产生了两个问题： 1. 给定满足正整数

和

互素的分数

，它所对应的LR序列是什么？ 2. 给定LR序列，它所表示的分数是什么？

第二个问题看起来更好解决一点，我们先解决第二个问题。 我们定义

例如

如果用代码实现的话，对于每个L或者R，如果是L，那么就把右边界设为中间值，如果是R，那么就把左边界设为中间值。

但是如何用数学式子来表达这一过程呢？

我们建立一个2阶方阵：

表示

的两个祖先分数

和

那么初始状态就可以表示为

如果遇到了向左符号L，那么

如果遇到了向右符号R，那么

所以我们将L和R定义成2阶方阵就行了：

所以

所以LRRL表示的分数为

那么第一个问题如何解决呢？ 同样可以用类似二叉搜索的方法来求出LR序列，也可以用矩阵的方法来求解，根据上面的L和R的方阵，可以发现：

对于L也有类似的性质，所以我们得到了如下的求解算法： 如果

，输出R，令

。 如果

，输出L，令

。

无理数近似表示

虽然说无理数不在Stern-Brocot树中，但是我们可以找到无限逼近它的分数。

方法仍然使用二叉搜索，不同的是，搜索过程不会终止，除非得到了我们想要的精度或者我们人为终止。

值得一提的是，无理数

的LR表示很有规律性：

最后值得一提的是，欧几里得算法和有理数的Stern-Brocot树表示有密切的关系。给定

，根据之前的算法，它的LR表达式首先是

个R，然后是

个L，依次下去，这些系数恰好就是求最大公因数的时候用到的系数。

同余关系

同余定义为：

读作“a关于模m与b同余”，我们只讨论都是整数的情况。

同样可以写作：

同余是等价关系，满足自反律、对称律、传递律，即：

如果我们对同余两边的元素加减乘，同余仍然满足：

因此可以得到

然而对于除法同余并不总是成立，一些特殊条件下可能成立。 如果

当

互素的时候，我们可以得到

同样

更一般的情况下，我们有

还有许多性质我就直接列举了，不做证明了，证明很简单：

其中

是

的素因子分解。 第三条性质是中国剩余定理的特例，今后我们再做证明。

独立剩余

同余的应用之一就是剩余系，将整数

表示为一组互素的模的剩余（余数）序列：

其中模

两两互素。

通过这个剩余序列可以确定出

的通解，其实可以看出来，这就是中国剩余定理的另一种表示形式。

这种表示形式有很多好处，比如可以直接在每个维度上面进行加减乘法。例如对于

的剩余系，有如下表示：

那么

就可以这样计算：

所以