中国剩余定理

关键词: 代数    同余

孙子定理,国际上称为中国剩余定理(Chinese Remainder Theorem),它的内容是:

若整数

  两两互素,那么同余方程组

有解,并且它的解为

其中,

  ,

  ,

  满足

  。

历史

孙子定理源于我国古代《孙子算经》中著名的“物不知数”问题:“今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?”

明代数学家程大位在他著的《算法统宗》(1593年)中用一首诗道出了此问题的解法:

三人同行七十稀,五树梅花廿一枝,

七子团圆整半月,除百零五便得知。

这首诗的意思用现代数学语言写出来就是:

  ,其中

  分别是除以3, 5, 7的余数,在上述问题中分别取2, 3, 2。

但上面的讨论都只限于模2, 3, 5的情形,而第一个研究一般情况的数学家是秦九韶。他在1247年成书的《数书九章》中研究了这个定理。

近世交换环及推广

  为有单位元的交换环,

  ,…,

  为环

  的理想,并且当

  

  

  时,

  +

  =

  .则有典范的环同构

  /(

  

  …

  

  )

  

  /

  

  …

  

  /

  ,

其中环同构由映射

  +

  

  …

  

  

  (

  +

  ,

  +

  ,…,

  +

  )给出。

关键词: 代数    同余

孙子定理,国际上称为中国剩余定理(Chinese Remainder Theorem),它的内容是:

若整数

  两两互素,那么同余方程组

有解,并且它的解为

其中,

  ,

  ,

  满足

  。

历史

孙子定理源于我国古代《孙子算经》中著名的“物不知数”问题:“今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?”

明代数学家程大位在他著的《算法统宗》(1593年)中用一首诗道出了此问题的解法:

三人同行七十稀,五树梅花廿一枝,

七子团圆整半月,除百零五便得知。

这首诗的意思用现代数学语言写出来就是:

  ,其中

  分别是除以3, 5, 7的余数,在上述问题中分别取2, 3, 2。

但上面的讨论都只限于模2, 3, 5的情形,而第一个研究一般情况的数学家是秦九韶。他在1247年成书的《数书九章》中研究了这个定理。

近世交换环及推广

  为有单位元的交换环,

  ,…,

  为环

  的理想,并且当

  

  

  时,

  +

  =

  .则有典范的环同构

  /(

  

  …

  

  )

  

  /

  

  …

  

  /

  ,

其中环同构由映射

  +

  

  …

  

  

  (

  +

  ,

  +

  ,…,

  +

  )给出。


相关内容

  • 中国剩余定理及其应用
  • 第26卷第6期 2005年11月通化师范学院学报JOU RNAL OF T ONGHU A T EACHERS . COLL EGE V ol. 26No. 6N ov. 2005 中国剩余定理及其应用 王海鹃, 王镁衔12¹ (1. 通化师范学院 数学系, 吉林通化134002; 2. 通化钢铁公 ...

  • 中国剩余定理的归纳及其应用3
  • LUOYANG NORMAL UNIVERSITY 2012届 本科毕业论文 中国剩余定理的归纳及其应用 院(系)名称 专 业 名 称 学 生 姓 名 数学科学学院 数学与应用数学 任晓燕 080414001 王众杰 讲师 2012.5 学 号 指 导 教 师 完 成 时 间 中国剩余定理的归纳及其 ...

  • 初等数论中的几个重要定理 高中数学竞赛
  • 初等数论中的几个重要定理 基础知识 定义(欧拉(Euler)函数)一组数的 , 的剩余,即 且对于任意的 .并定义 ,若 称为是模的既约剩余系,如果对任意 是对模 =1,则有且仅有一个 中和 互质的数的个数, 称为欧拉(Euler )函数. 这是数论中的非常重要的一个函数,显然中与 互素的数的个数, ...

  • 论分工与就业的关系_发展经济学两大定理及其现实意义的初步考察
  • 1999年第5期No. 5, 1999 浙江社会科学 1999年9月Sept . , 1999 ZHEJ IANG SOCIAL SCIENCES 论分工与就业的关系 发展经济学两大定理及其现实意义的初步考察 内容提要 白小虎 斯密定理和杨格定理是发展经济学上两大定理.本文先就两大定理之间的关系展开 ...

  • 中国剩余定理的几点应用
  • 2002年第6期 中学数学 45 中国剩余定理的几点应用 223001 江苏省淮阴工学院经济管理系 张积羽430062 湖北大学数学系 刘合国 中国剩余定理在代数学里起着重要的作用, 它是我们祖先智慧的结晶. 这个定理现在已被表述成极为一般的形式, 这里我们采用多项式的语言来叙述它, 但所使用的方法 ...

  • "韩信点兵"问题的一种新解法探索
  • "韩信点兵"问题的一种新解法探索 陈佳1 唐海军 何聪 曾雪彪 (四川文理学院 数学与财经学院 四川 达州 635000) 摘要:通过研究韩信点兵问题得到关于中国剩余问题的一般解法,加深了对数论中一次同余式的认识,有助于中学生解决数学竞赛问题以及学习算法. 关键词:剩余问题:同余 ...

  • 中国剩余定理 非互质
  • 此文档由KIDx 制作 (于2014年2月22日修正,加粗红色为修正部分) 问题描述:给出bi ,ni 的值,且n1, n2, n3,-, ni两两之间不一定互质,求Res 的值? 解:采用的是合并方程的做法. 这里将以合并第一第二个方程为例进行说明 由上图前2个方程得(设k1.k2为某一整数) : ...

  • 垄断劳动力市场_最低工资限制和不平等
  • 2008年第11期No . 11, 2008 浙 江 社 会 科 学 ZHEJ I ANG S OC I AL SC I ENCES 2008年11月Nov . , 2008 垄断劳动力市场.最低工资限制和不平等 □ 王弟海 内容提要 关于劳动力垄断市场对于加总经济和社会福利水平的影响, 现有主流经 ...

  • 信息论基础
  • <信息论基础>课程教学大纲 课程编号:(0531305) 课程名称:信息论基础 参考学时:48 其中实验或上机学时:0 先修课及后续课:先修课:概率论.信号与系统 后续课:通信原理.数字图像处理.语音信号处理 说明部分 1.课程性质 本课程是电子信息类专业的技术基础课 2.课程教学的目的 ...