同余法求最大公约数

同余作为数论中最基本的概念,在数论中占有极为重要的地位,进而也极大地丰富了数学的内容,同余理论也以数论特有的思想、概念与方法来研究着整数的性质,而求两个或几个数的最大公约数是与整数的性质有关的基础和重要内容。我提出的用同余法求最大公约数,在丰富了求最大公约数的方法和同余理论的作用的基础上,同时为研究有关中小学数学教学和竞赛的问题提供了平台。

下面笔者给出自己在授课后发明的同余法求最大公约数的基础理论:

定理1 ɑ≡r(mod b)⇒(ɑ,b)=(r,b)

证明:设(ɑ,b)=p,(r,b)=q

其实,这个理论还可以推广到求多个数的最大公约数的情形:

定理2

证明:设(ɑ1,ɑ2,…,ɑn,b)=p,(r1,r2,…,rn,b)=q

即(ɑ1,ɑ2,…,ɑn,b)=(r1,r2,…,rn,b)

例:求(8127,11352,21672,27090)

总之,把同余知识用在求最大公约数上只是笔者个人在授课后的一点浅显认识,它能很快地解决一些甚至一些较大数字求最大公约数的问题,希望能对各位老师及学者在解决具体问题有所帮助。

摘要：求最大公约数的方法有很多种:分解质因数法,提取公因数法(短除法),辗转相除法,辗转相减法等。本文在上述方法的基础上,提出了同余法求最大公约数的理论及其推广形式,同时给出了严格证明,对求最大公约数的方法做出了进一步的完善。

关键词：最大公约数,同余法

参考文献

[1] 人民教育出版社中学数学室.代数与初等函数[M].人民教育出版社,1999.12.1.[1]人民教育出版社中学数学室.代数与初等函数[M].人民教育出版社,1999.12.1.

[2] 王元.高等师范院校小学教育专业数学教材《初等数论》[M].人民教育出版社,2003.9.[2]王元.高等师范院校小学教育专业数学教材《初等数论》[M].人民教育出版社,2003.9.

[3] 王进明.大学本科小学教育专业教材《初等数论》[M].人民教育出版社,2002.12.[3]王进明.大学本科小学教育专业教材《初等数论》[M].人民教育出版社,2002.12.