|
| 阅读上一个主题 :: 阅读下一个主题 |
| 作者 |
 |
 |
| 所跟贴 |
你不是说“中国古代数学家才从来没有创立什么普适的数学定理”吗？ -- 随便 - (65 Byte) 2005-1-07 周五, 上午4:05 (159 reads) |
随便
加入时间: 2004/02/14
文章: 24019
经验值: 64
|
|
|
作者：随便 在 罕见奇谈 发贴, 来自 http://www.hjclub.org
再给芦老补一次课。以前以为芦老还有两下子，怎么一捅
就掉底了。
费解中。。。
==================================================
中国余数定理(CRT)及其应用
中国余数定理(Chinese Remainder Theory,CRT)目前我还没有看出什么用处，作为数论里一个知识罗列一下吧。所以叫中国余数定理，是因为据信他是中国古代数学家在公元100年左右发现的。
笛卡儿积
笛卡儿积是集合论中很重要的概念，已知一组集合S1、S2、...、Sn，他们的笛卡儿积S定义为：
S = {(x1,x2,...,n) |
x1 ∈S1，
x2 ∈S2，
......
xn ∈Sn}
一个相关的概念叫关系，集合族S1、S2、...、Sn的一个关系定义为他们的笛卡儿积S的一个子集。如果这个子集是空集或者S本身，则称这个关系是一个平凡关系。
举例而言，集合N和N的笛卡儿集合为二维空间集合{(x,y) | x,y∈N}，而关系y=2x可以表示为笛卡儿集合的一个子集 {(x,2x)|x∈N}
映射
集合X和Y，如果存在一种关系，使得X中的任意一个元素x都对应于集合Y的一个元素y或者一组元素y，则称呼这种关系为X集合到 Y集合的一个映射，记做f →y。其中x称作y在X中的原象，y称为x在Y中的象。有时，映射也记做y = f(x)
如果X中任意一个元素在Y中只有一个象，称这个映射为一个单射。如果y中任意一个元素在X中都存在一个原象，则称呼映射为满射。
映射f→y，如果能找到象到原象的映射，则称为该映射的逆映射。
一个映射如果既是单射又是满射，则称该映射为一个一一映射
距离算子
集合S上定义的距离算子ρ指得是S×S到非负实数集合R+上得一个映射满足：
ρ(x,y) ≥0，且当且仅当x=y时取0，非负律
ρ(x,y) = ρ(y,x) 交换律
ρ(x,y) + ρ(y,z) ≥ ρ(x,z) 三角公式
运算
集合S上定义的二元运算是指S×S 到S的一个单射，即任意x,y∈S 存在z∈S，z = x⊙y是S×S中元素(x,y)在S中的象，其中⊙称呼为这个运算的运算符，运算也可以表示为一个二元函数关系，记做z = ⊙(x,y)
同态映射和同构映射
集合X到Y上的一个一一映射f，X、Y上分别定义了运算+和×（注意，这是抽象运算，和四则运算中的对应符号没有关系），
如果对于X中的任意元素x1、x2，他们在Y中的象分别是y1、y2，如果
x3=x1 +x2
y3=y1 ×y2
则y3是x3在Y上的象，也就是说
f(x1 +x2) = f( x1) × f( x2)
则称这个映射f为集合X到Y的一个同态映射。如果X,Y上还定义距离算子ρ和ρ'，且满足ρ(x1,x2) ＝ρ'(y1,y2) ，则称
这个同态映射为同构映射。
中国余数定理
如果整数M可以表示为n个彼此互质得整数mi得乘积，则M的完全余数集ZM和他所有因子的完全余数集的笛卡儿集合之间存在一个同态映射
也就是说，存在映射关系
A ∽(a1,a2,...,an)
B ∽(b1,b2,...,bn)
则
(A+B) mod M ∽((a1+b1) mod m1,(a2+b2) mod m2,..,(an+bn) mod mn)
(A-B) mod M ∽((a1-b1) mod m1,(a2-b2) mod m2,..,(an-bn) mod mn)
(A×B) mod M ∽((a1×b1) mod m1,(a2×b2) mod m2,..,(an×bn) mod mn)
A 到(a1,a2,...,an)的映射很简单，用关系式
ai = A mod mi
计算即可。
对于反向映射，可以这样计算：
定义Mi = M / mi
则由于mi和其他任意mj互质，Mi和mi也互质，根据
欧几里德算法和扩展欧几里德算法一文中所述，Mi
存在唯一的模mi的逆元Mi，令
ci = Mi Mi
则A = (a1c1 + a2c2 + ... + ancn) mod M
下面举一个例子，假设整数4×9×25 ＝ 900，数729是900的完全余数集中的一个元素，则按照上述关系可以得到对应关系
729 -> (1,0,4)
由(1,0,4)计算729可以这样进行：
M1 = 9*25 = 225，M1-1 mod 4 = 1
M2 = 4*25 = 100，M2-1 mod 9 = 1
M3 = 4*9 = 36，M3-1 mod 25 = 16
则729 = ( 1* 1 * 225 + 0 * 1 * 100 + 4 * 16 *36) mod 900
这也是一个古题的传统解法：一个数，被3除余一，被5除余2，被7除余一，问这个数是多少？套用上面公式，计算也太简单了。也就是M=3×5×7=105，计算105和(3,5,7)完全余数集之间的映射关系而已。
这个问题可以统一表述为：已知整数m1、m2、...、mn彼此互质，则求整数x的方程
x mod m1 = a1
x mod m2 = a2
.......
x mod mn = an
有模M的唯一解，M =所有mi的乘积
实际上，上述叙述是CRT的另外一种表示形式，证明也很容易，在此我就不在赘述了。
发表于 Friday, June 11, 2004 3:22 AM
评论
# re: 中国余数定理(CRT)及其应用 7/3/2004 4:06 AM 事实上
中国余数定理的用途？用GOOGLE查一下就可以了。
作者：随便 在 罕见奇谈 发贴, 来自 http://www.hjclub.org |
|
|
| 返回顶端 |
|
 |
- He, he, -- 芦笛 - (598 Byte) 2005-1-07 周五, 上午4:21 (180 reads)
|
|
|
您不能在本论坛发表新主题
您不能在本论坛回复主题
您不能在本论坛编辑自己的文章
您不能在本论坛删除自己的文章
您不能在本论坛发表投票
您不能在这个论坛添加附件
您不能在这个论坛下载文件
|
based on phpbb, All rights reserved.
|
