无理数近似表示
虽然说无理数不在Stern-Brocot树中,但是我们可以找到无限逼近它的分数。
方法仍然使用二叉搜索,不同的是,搜索过程不会终止,除非得到了我们想要的精度或者我们人为终止。
值得一提的是,无理数 的LR表示很有规律性:
最后值得一提的是,欧几里得算法和有理数的Stern-Brocot树表示有密切的关系。给定 ,根据之前的算法,它的LR表达式首先是 个R,然后是 个L,依次下去,这些系数恰好就是求最大公因数的时候用到的系数。
同余关系
同余定义为:
读作“a关于模m与b同余”,我们只讨论都是整数的情况。
同样可以写作:
同余是等价关系,满足自反律、对称律、传递律,即:
如果我们对同余两边的元素加减乘,同余仍然满足:
因此可以得到
然而对于除法同余并不总是成立,一些特殊条件下可能成立。
如果
当 互素的时候,我们可以得到
同样
更一般的情况下,我们有
还有许多性质我就直接列举了,不做证明了,证明很简单:
第三条性质是中国剩余定理的特例,今后我们再做证明。
独立剩余
同余的应用之一就是剩余系,将整数 x 表示为一组互素的模的剩余(余数)序列:
其中模 m 两两互素。
通过这个剩余序列可以确定出 x 的通解,其实可以看出来,这就是中国剩余定理的另一种表示形式。
这种表示形式有很多好处,比如可以直接在每个维度上面进行加减乘法。例如对于 的剩余系,有如下表示:
那么 就可以这样计算:
所以