1 前言
整个数学的发展史是和人类物质文明和精神文明的发展史交融在一起的。数学不仅是一种精确的语言和工具、一门博大精深并应用广泛的科学，而且更是一种先进的文化。它在人类文明的进程中一直起着积极的推动作用，是人类文明的一个重要支柱。自古（这里指1975年以前）数论拥有数学最纯粹部分的美称。同余理论是数论里的重要内容之一，同余这一特殊语言在数论中极为有用，其性质及应用的研究已引起许多学者的关注，人们之所以研究同余，是因为它历史悠久且硕果累累，也因为它有大量易于理解而令人着迷的问题，更因为它富裕智慧的魅力。前者的研究只是对同余的某个性质进行探讨，不够全面、彻底。本论文归纳总结了同余的若干性质，结合实例探究了同余性质在整除校验、构造校验位、解方程、求余数、素性判定等方面的应用。现代数论的发展始于德国数学家高斯（Gauss）,他是历史上最伟大的数学家之一，在19世纪初期发明了同余的语言。我们称两个整数a和b是模m同余的（其中m为正整数）是指m整除a-b。这种语言是我们我们在研究整除性关系的时候，变得像研究方程那样容易。
人们在日常生活中，不知不觉地在运用着大量的同余数知识。本论文用丰富的例子、通俗的语言、易懂的证明，介绍同余式的概念、计算方法及其应用，证明了费马小定理和中国剩余定理、整除、二次剩余的讨论和计算。提现了用同余性质解决问题的简洁性。在引入同余之前，人们研究整除关系所用的记号笨拙而且难用。而引入方便的记号对加速数论的发展起了重要作用。同时，本文还研究了一些特殊的同余式，如威尔逊定理和费马小定理、伪素数、欧拉定理。
本论文主要分为三个方面，第一阶段研究同余。将给出它的一些基本性质（等价性，传递性等）描述如何进行同余式的算术运算，还将研究含有未知数的同余方程，例如线性同余方程，多项式同余方程，线性同余方程组等。引出线性同余方程组，它们来源于古代中国难题：求一个数，它被3,5和7除所得余数为2,3和2。我们将如何运用著名的中国剩余定理来解像上一难题那样的线性同余方程组。我们还将学习怎样解多项式同余方程。最后，我们用同余语言来介绍一种（整数）分解方法，即波拉德ρ方法。第二阶段研究同余的应用。同余有广泛的应用，如利用同余展示怎样在计算机上做大整数的乘法。本论文广泛涉及了同余的各种类型的有趣的应用，首先，我们将指出如何利用同余进行整除性检验，比如已经熟知的如火如何判断一个整数能否被3或9整除的简单检验。然后会推导出一个可以确定历史上任何一天的星期数的同余式。还有利用同余编排循环赛程。我们也将讨论同余性质在计算科学中的一些应用，例如，应用在散列函数上，散列函数本身就有很多种应用，比如确定数据储存的计算机存储地址。最后，我们将给
1
出如何利用同余构造校验位，用来确定一个认证数是否被错误复制。如何利用同余从不同的途径对信息惊醒加密，或者利用同余产生随机数。最后一个阶段研究当今最流行的工具Maple或Mathematic如何用于执行数论中的计算。本论文将简单的描述一些对于同余的计算有用的命令，主要通过描述这两种系统中已经存在的命令，编程计算同余相关的问题。
2
2 同余
2.1 同余引言
同余在日常生活中随处可见。例如，钟表对于小时是模12或24的，对于分钟和秒是模60的；日历对于星期是模7的，对于月份是模12的水电表是模1000的，里程表通常是模100000的。我们有时需要将同余式转换为等式。
人们从孩提时代开始就知道每个星期有七天：从星期一到星期六，再加上一个星期日，接下来又是星期一。如果某一天是星期一，那么在它以后的第8天、第15天、第22天、……都是星期一。这些都是星期一的―天数‖有一个共性：它们除以7所得的余数都是1。也就是说，它们除以7是―同余的‖。 2.1.1 相关定义
定义 给定一个正整数m把它叫做模，如果用m去除整数a和b ，所得余数相同，我们就说a与b对模m同余，记作a?b(modm)。如果余数不相同，那么我们就说a与b对模m不同余，记作a?b(modm)。或设m是正整数，若a和b是整数，且
m(a?b)，则称a和b模m同余。如果a和b模m同余,则记
a?b(modm)。如果a和b模m不同余，则记m|(a,b)，并称a模m不同余b。整
数m称为同余的模。 2.1.2 相关性质定理
定理 2.1 a和b是整数，则a?b(modm)当且仅当存在整数k，使得
a?b?km。
证明 若a?b(modm)，则
m(a?b)。这说明存在整数k，使得
km?a?b，所以a?b?km。
?b反过来，若存在整数k使得a?b?km，则km?a。于是，m(a?b)a?b(modm),。
定理2.2 设m是大于0的整数，则模m的同余有下列性质： （1）自反性. 如果a是整数，则a?a(modm)。
（2）对称性. 如果a和b是整数，且a?b(modm)，则b?a(modm)。
3
（3）传递性. 如果a，b和c是整数，且a?b(modm)和b?a(modm)，则
a?c(modm)。
定理2.3 如果a,b,c和m均是整数，并且m大于0，同余式可以相加减，即若有a?b(modm)，c?d(modm) 则 （1）a?c?b?d(modm) （2）a?c?b?d(modm) （3）ac?bd(modm)
m?0，d?(c,m)并且有ac?bc(modm)， 定理2.4 如果a,b,c和m是整数，
那么a?b(modm/d)。
m?0，c与m互素，并且有ac?bc(modm) 推论2.4.1 如果a,b,c和m是整数，
则有a?b(modm)。
定理2.5 如果a,b,n和m是整数，并且n和m均大于0，a?b(modm)
nna?b(modm)。 则有
定理2.6 如果a,b,m1,m2,...,mk是整数，m1,m2,...,mk均大于0，且有
a?b(modm1),a?b(modm2),...,a?b(modmk)则a?b(mod?m1,m2,....mk?)。 推论2.6.1 如果 a?b(modm1),a?b(modm2),...,a?b(modmk)，其中，a,b是整数，
定理 2.7 若自然数n?2,ai?bi(modm),i?1,2.......n,
ai??bi(modm)则?i?1i?1nnm1,m2,...,mk是两两互素的整数，则a?b(modm1m2...mk)。
。
ni 定理2.8 设
f(x)??aixi?1 ，
g(x)??bixii?1n ，x?z。如果
ai?bi(modm)，
i?0,1,2,......n则f(x)?g(x)(modm)。
4
定理 2.9 若a?b(modm)
（1）当 dm，d?0时，a?b(modd)。
ab?m?mod? （2）d是a,b及模m的任一正公因数，则d?d??d???。
定理 2.10 设a,b?Z，且b?0，则存在唯一一对整数q,r，使得a=bq+r，其中0?r?b。
定义 一个模m完全剩余系是一个整数的集合，使得每个整数恰和此集合中的一个元素模m同余。
定理2.11 如果r1,r2,...,rm是一个模m完全剩余系，并且正整数a使得a与m互素，那么对于任何的整数b，ar1?b,ar2?b,...,arm?b都是模m的完全剩余系。 2.2 线性同余方程 设x是未知整数，形如
(modm ax?b ) （2-1）
的同余式称为一元线性同余方程。 如果我们有那么
x?x0是同余方程ax?b(modm)的一个解，并且
x1?x0(modm)，
ax1?ax0?b(modm)，所以x1也是一个解。因此，由文献[1]可知：如果一个
模m同余类的某个元素是解，则此同余类的所有元素都是解。那么，方程有多少个模m不同余的解等价于模m的m个同余类中有多少个给出方程的解。引用下面的定理，我们会得知一元线性同余方程在那种情况下有解，更进一步的在有解时方程有多少模m不同余的解。
定理2.12 设a,b和m是整数，m>0,(a,m)=d.若d不整除b，则ax?b(modm)无解。若d整除b,则ax?b(modm)恰有d个模m不同余的解。 在证明之前，我们先引入一个定理
定理2.13 设a,b是整数且d=(a,b)。如果d不整除c,那么方程ax?by?c没有整数解。如果d整除c，那么存在无穷多个整数解。另外，如果x?x0，y?y0
5