arongnet 阅读(1323) 评论(12)

中国余数定理(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:x→y。其中x称作y在X中的原象,y称为x在Y中的象。有时,映射也记做y = f(x)

如果X中任意一个元素在Y中只有一个象,称这个映射为一个单射。如果y中任意一个元素在X中都存在一个原象,则称呼映射为满射。

映射f:x→y,如果能找到象到原象的映射,则称为该映射的逆映射。

一个映射如果既是单射又是满射,则称该映射为一个一一映射

距离算子

集合S上定义的距离算子ρ指得是S×S到非负实数集合R+上得一个映射满足:

  1. ρ(x,y) ≥0,且当且仅当x=y时取0,非负律
  2. ρ(x,y) = ρ(y,x) 交换律
  3. ρ(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的另外一种表示形式,证明也很容易,在此我就不在赘述了。


评论列表
事实上
re: 中国余数定理(CRT)及其应用
中国余数定理的用途?用GOOGLE查一下就可以了。
meteor135
re: 中国余数定理(CRT)及其应用
这个问题可以统一表述为:已知整数m1、m2、...、mn彼此互质,则求整数x的方程

x mod m1 = a1
x mod m2 = a2
.......
x mod mn = an
有模M的唯一解,M =所有mi的乘积===================>什么乱七八糟的?
谁模谁啊?????
阿荣
当然是解模M啊
好像数论中都这么说
晓晓
我这儿有组密码,您可以尝试破解
密码内容如下:BA AB BA BC AC BB AB CC CB BC AC BA,提示:3*3*3=26+1.如果您能成功破解,烦劳将结果发到如下信箱:
sxx85@163.com
arong
我这儿有组密码,您可以尝试破解 2005-07-22 17:40 晓晓
很抱歉一直每看留言。下次有啥考校我的发到我信箱
这是一个利用3进制数进行简单加密的算法。密文是ILOVEYOU。
A=0
B=1
C=2
每三个字母表示一个三进制数,表示在字母表中的序号
孤帆
re: 中国余数定理(CRT)及其应用
看看PD雷达中的解举例模糊,就知道中国余数定理得用处了
wang
re: 中国余数定理(CRT)及其应用
原始问题是

Ai属于(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15)
i从一到十五
现在有
F=(A1+A2)%15+(A2+A3)%15+......+(A13+A14)%15+
(A14+A15)%15
求F的最小值
**********
re: 中国余数定理(CRT)及其应用
    28+3嗄 ) 门锝

发表评论
切换编辑模式