具体数学-第11课(Stern-Brocot树和同余关系二)

简介: 我们接着上节课讲到的Stern-Brocot树继续往下讲.

无理数近似表示


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

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

值得一提的是,无理数 image.png 的LR表示很有规律性:

image.png

最后值得一提的是,欧几里得算法和有理数的Stern-Brocot树表示有密切的关系。给定image.png ,根据之前的算法,它的LR表达式首先是 image.png 个R,然后是 image.png 个L,依次下去,这些系数恰好就是求最大公因数的时候用到的系数。

同余关系


同余定义为:

image.png

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

同样可以写作:

image.png

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

image.png

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

image.png

因此可以得到

image.png

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

如果

image.png

image.png 互素的时候,我们可以得到

image.png

同样

image.png

更一般的情况下,我们有

image.png

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

image.png

第三条性质是中国剩余定理的特例,今后我们再做证明。

独立剩余


同余的应用之一就是剩余系,将整数 x 表示为一组互素的模的剩余(余数)序列:

image.png

其中模 m 两两互素。

通过这个剩余序列可以确定出 x 的通解,其实可以看出来,这就是中国剩余定理的另一种表示形式。

这种表示形式有很多好处,比如可以直接在每个维度上面进行加减乘法。例如对于 image.png 的剩余系,有如下表示:

image.png

那么 image.png 就可以这样计算:

image.png

所以

image.png

相关文章
|
2天前
|
算法 测试技术 C++
【动态规划】【 数学】C++算法:514自由之路
【动态规划】【 数学】C++算法:514自由之路
|
2天前
|
自然语言处理
数学基础从高一开始1、集合的概念
数学基础从高一开始1、集合的概念
41 0
|
2天前
数学基础从高一开始4、集合的基本运算2
数学基础从高一开始4、集合的基本运算2
20 0
|
2天前
数学基础从高一开始3、集合的基本运算
数学基础从高一开始3、集合的基本运算
27 0
|
7月前
计算机科学中的树
二叉树 ▪ 二叉查找树 ▪ 笛卡尔树 ▪ Top tree ▪ T树 自平衡二叉查找树
36 0
|
2天前
|
JavaScript
判断关系属于哪一种范式(期末考试必看)
判断关系属于哪一种范式(期末考试必看)
8 1
|
2天前
|
自然语言处理
数学基础从高一开始2、集合间的基本关系
数学基础从高一开始2、集合间的基本关系
24 0
|
2天前
|
Java C++ Python
试题 基础练习 Huffuman树
试题 基础练习 Huffuman树
15 0
|
9月前
|
数据采集 存储 算法
图论:探索节点与关系的数学世界
引言 本文仅仅作为图论的概述,由于种种原因没有进行排版(笔者不太会用这个编辑器),超链接为扩展内容,大家可以点击详细学习。
73 0
|
11月前
离散数学_九章:关系(4)(一)
离散数学_九章:关系(4)(一)
63 0