求解中国剩余定理的矩阵变换方法

求解中国剩余定理的矩阵变换方法福建师范大学郑开杰内容提要1综合评价21CRT及其经典算法2矩阵变换方法3算例比较4教学心得2020/7/921CRT及其经典算法CRT的中国起源:物不知其数3原文曰“今有物不知其数,三三数之剩二;五五数之剩三;七七数之剩二.问物几何?”(《孙子算经》下卷第26题)四句歌诀(大衍求一术)三人同行七十稀,五树梅花廿一枝;七子团圆正半月,除百零后便得知.(数书九章、算法统宗)解法原文:“术曰:三三数之剩二,置一百四十,五五数之剩三,置六十三,七七数之剩二,置三十,并之,得二百三十三,以二百一十减之即得.凡三三数之剩一,则置七十,五五数之剩一,则置二十一,七七数之剩一,则置十五.一百六以上,以一百五减之即得.”Date31CRT及其经典算法CRT在西方:高斯1801年建立的同余理论3CRT的数学描述3Date41CRT及其经典算法CRT解的存在唯一性3定理(中国剩余定理)定有解,且在模意义下,解是唯一的Date51CRT及其经典算法CRT算法1(石生明《近世代数初步》)3Date61CRT及其经典算法CRT算法1:非两两互素情况3Date71CRT及其经典算法CRT算法(石生明《近世代数初步》)3Date81CRT及其经典算法几点教学疑问3步3中的逆元计算及步4中的最小公倍式的计算,一般需用到整数的辗转相除法,计算量不小所接触到的教材,均只讲除数两两互素的情况初衷3很显然,CRT是同余方程组问题很显然,同余方程组可以等价地转化为整数环上的线性方程组问题很自然,会将二者结合,且一定会想到用初等变换方法求解一切都是水到渠成,以前难道没有人这么想法吗?Date9问题转化32矩阵变换方法,.Date10