同余关系及其在计算机领域的应用 例:假设信用卡的标志码为5546199723355004,检查该卡的有效性 解: 1.0.2=05·2=103.2=62.2=49.2=181.2=24.2=85.2=10 2.0+1+6+4+9+2+8+1=31 3.5+6+9+7+3+5+0+4=39 4.31+39=70 5.70=0(mod10) 所以这张卡的标志码有效
同余关系及其在计算机领域的应用 : 55461997 2335 5004 mod 例 假设信用卡的标志码为 ，检查该卡的有效性。 解： 1.0 2=0 5 2=10 3 2=6 2 2=4 9 2=18 1 2=2 4 2=8 5 2=10 2.0+1+6+4+9+2+8+1=31 3.5+6+9+7+3+5+0+4=39 4.31+39=70 5.70 0（ 10） 所以这张卡的标志码有效
2.1一次同余式组 o本节介绍一次同余式组的解法及其应用举例 o在公元三世纪前,《孙子算经》里已提出了下面的同余 式组 x=b,(mod m,, x=b2(mod m,),., x=bk (mod mk)(1) o这种形式的问题,并且很好地解决了它.《孙子算经》 里所提出的问题之一如下 “今有物不知其数,三三数之剩二,五五数之剩三,七七 数之剩二.问物几何?”“答日二十三
2.1 一次同余式组 本节介绍一次同余式组的解法及其应用举例． 在公元三世纪前,《孙子算经》里已提出了下面的同余 式组 xb1 (mod m1 ), xb2 (mod m2 ),…, xbk (mod mk ) (1) 这种形式的问题, 并且很好地解决了它.《孙子算经》 里所提出的问题之一如下: “今有物不知其数, 三三数之剩二, 五五数之剩三, 七七 数之剩二. 问物几何？” “答日二十三
2.1一次同余式组 o把这个问题的提法用同余式的式子来表达,它可 表示成解同余式组 X=2 (mod 3) x=3(mod 5), X=2(mod 7) 其中x是所求物数 o关于同余式组: x=a(mod 3), xEb(mod 5), XEb(mod 7) 的一般解为: x=70a+21b+15c(mod105) 15:51:43
15:51:43 2.1 一次同余式组 把这个问题的提法用同余式的式子来表达，它可 表示成解同余式组 x2(mod 3), x3(mod 5), x2(mod 7) 其中x是所求物数. 关于同余式组: xa(mod 3), xb(mod 5), xb(mod 7) 的一般解为: x 70a+21b+15c (mod 105)
2.1一次同余式组 o这个解法,在明朝程大位的《算法统宗》(1593)里 有下面一首诗歌: 人同行七十稀, 五树梅花甘一枝, 七子团圆整半月 除百零五便得知。 o关于解同余式组的问题,在我国古代有极光辉的研 究成果.我国古代数学家孙子发明了下面的中外驰 名的定理,在国外誉为中国剩余定理,在国内称为 孙子定理 15:51:43
15:51:43 2.1 一次同余式组 这个解法, 在明朝程大位的《算法统宗》(1593)里 有下面一首诗歌: 三人同行七十稀， 五树梅花甘一枝， 七子团圆整半月， 除百零五便得知。 关于解同余式组的问题, 在我国古代有极光辉的研 究成果. 我国古代数学家孙子发明了下面的中外驰 名的定理, 在国外誉为中国剩余定理, 在国内称为 孙子定理
2.1一次同余式组 定理1一次同余式组 X=b, (mod m1), x=b2(mod m2)(1 有解if(m,m2)(b1-b2),且当(1)有解时对模[m1,m2l有唯一解 证明:设(1)有解x0,(m1,m2)=d,则有: X≡b1(modm1),X b2(mod m2) mI=dq1, m2-=ag2 于是,xb1=dqg1m1,xo-b2=dq2m2,因此,d|(b1-b2) 若(m,m2)(b-b2),则因x=b1modm1)可表示为:x=b1+my,代 入x=b2(modm)得: m1y=(02 b1)( mod m 2)(2) 因为(m1,m2)=d,d|(b2-b1),(②)有解,设为yo,且对模m2/d有唯 解: y=yo(mod(m2/d)) 15:51:43
15:51:43 2.1 一次同余式组 定理1 一次同余式组 xb1 (mod m1 ), xb2 (mod m2 ) (1) 有解 iff (m1 ,m2 )|(b1 -b2 ), 且当(1)有解时对模[m1 ,m2 ]有唯一解. 证明： 设(1)有解x0 , (m1 ,m2 )=d, 则有: x0b1 (mod m1 ), x0b2 (mod m2 ) m1=dq1 , m2=dq2 于是, x0 -b1=dq1m’1 , x0 -b2=dq2m’2 , 因此, d|(b1 - b2 ). 若(m1 ,m2 )|(b1 -b2 ),则因xb1 (mod m1 )可表示为: x=b1+m1y, 代 入xb2 (mod m2 )得: m1y(b2 -b1 )(mod m2 ) (2) 因为(m1 ,m2 )=d, d|(b2 -b1 ), (2)有解, 设为y0 , 且对模m2 /d有唯 一解: yy0 (mod (m2 /d))