1.2  等价关系

1.2 等价关系

数学的一项重要任务是在纷繁复杂的个体中发现它们的某种共性，并且利用这种共性解决问题.等价关系就是为实现这样一个目的而引入的.本节的目的就是对于这种在数学中最常见的等价关系作一个初步的研究.

设A是一个非空集合，a，b是集合A的两个元素，如果这两个元素之间具有某种特定的关系或者性质，则我们把这个事实记作a～b，并称a，b具有关系～.

关系在数学中无处不在.例如，在实数集合R上的等于关系、小于关系、大于等于关系等都是这里所说的关系的例子，当然它们都有各自特定的符号=、<、≥.在所有平面图形组成的集合上，我们最熟悉的关系有直线的垂直、平行、三角形全等关系，当然它们也都有各自常用的符号⊥、∥、≅等.

等价关系是一种重要且具有良好性质的关系，其定义如下：

定义1.6 设A是一个非空集合，～是定义在A上的一个关系，并且满足下面三个条件：

（1）反身性 对任意的a∈A，都有a～a；

（2）对称性 对任意的a，b∈A，如果a～b，那么有b～a；

（3）传递性 对任意的a，b，c∈A，如果a～b且b～c，那么有a～c，则称这个关系～为集合A上的一个等价关系.

例1.3 考虑实数集合R，很容易验证，在R上定义的实数相等关系就是一种等价关系.小于关系不是一种等价关系，因为反身性和对称性都不成立.

例1.4 考虑所有的平面直线组成的集合L，如果我们可以认为每一条直线都是和自身平行的，那么平行关系就是L上的一个等价关系.但是垂直关系却不可能是等价关系，因为反身性和传递性都不可能是成立的.

例1.5 考虑平面上所有三角形组成的集合△，容易验证，全等关系和相似关系都是△上的等价关系.

例1.6 考虑平面上所有圆形组成的集合☉，在其上定义关系～₁，如果对两个圆a，b∈☉，它们有共同的圆心，那么a～₁b.这个关系可以称之为同心圆关系.

再定义关系～₂，如果对两个圆a，b∈☉，它们有相等的面积，那么a～₂b.这个关系可以称之为等积关系.

非常显然的是这里定义的同心圆关系与等积关系都是☉上的等价关系.但是，这两个等价关系显然是不同的.

下面我们在整数集合Z上定义一种重要的等价关系，即同余关系，并研究它的一些基本性质.

定义1.7 设n是一个大于1的正整数，若a，b是整数且n整除a-b，则称整数a和b模n是同余的，记作a≡b（modn）.

命题 整数模n的同余关系是一种等价关系，也就是说，

（1）反身性 对任意的整数a，有a≡a（modn）；

（2）对称性 对任意的整数a，b，如果a≡b（modn），那么b≡a（modn）；

（3）传递性 对任意的整数a，b，c，如果a≡b（modn）且b≡c（modn），那么a≡c（modn）.

证明略.

例1.7 任何两个奇数模2都是同余的，任何两个偶数模2也都是同余的。

例1.8 15和22模7是同余的，15和-6模7也是同余的，即

15≡22（mod7），15≡-6（mod7）.

定理1.1 若a≡b（modn）及a₁≡b₁（modn），则(https://www.daowen.com)

a±a₁≡b±b₁（modn），aa₁≡bb₁（modn）.

证明：由条件可知，n|a-b及n|a₁-b₁.又因为

（a±a₁）-（b±b₁）=（a-b）±（a₁-b₁），

aa₁-bb₁=a（a₁-b₁）+b₁（a-b），

所以，定理中的两个等式都成立.证毕.

定理1.2 若ab≡ac（modn）且（a，n）=1，则b≡c（modn）.

证明：由条件有n|a（b-c），又（a，n）=1，所以n|b-c，即b≡c（mod n）.证毕.

例1.9 计算3¹⁰⁰除以14的余数.

解：简单计算得到3²≡9（mod14），3³≡-1（mod14），所以3⁹⁹≡-1（mod14），进而有3¹⁰⁰≡（-1）×3≡11（mod14）.所以，3¹⁰⁰除以14的余数是11.

定理1.3（Fermat小定理） 设p是素数，（a，p）=1，则a^p-1≡1（modp）.

证明：若（a，p）=1，考虑p-1个数a，2a，…，（p-1）a，由定理1.2可见这p-1个数一定是模p互不同余的，并且没有一个数是和零同余的.这样，a，2a，…，（p-1）a分别除以p的余数应该是1，2，…，p-1的一个排列，利用定理1.1有

a×2a×…×（p-1）a≡1×2×…×（p-1）（modp），

再利用定理1.2有

a^p-1≡1（modp）.

推论 设p是素数，则a^p≡a（modp）.

Pierre de Fermat（1601—1665）是一位法国数学家，他的职业是法官，数学只是他的业余爱好.Fermat是现代数论研究的先驱，他在1640年给出这个重要定理.Fermat还是解析几何的创立者之一.作为微积分学的先行者，Fermat成功地解决了求曲线切线的问题.此外，他还研究了素数的平方和表示、Fermat素数等问题.他还提出了著名的Fermat猜想：不定方程xⁿ+yⁿ=zⁿ在n≥3时没有正整数解.这个猜想在1994年已经变成Fermat-Wiles定理了.

习题

1.2.1. 请给出一些等价关系.

1.2.2. 请给出一些关系，使之只满足反身性、对称性、传递性这三个条件中的一个或者两个.

1.2.3. 计算5²⁰⁰除以18的余数.

1.2.4. 求出7³⁶⁵的最后两位数.

1.2.5. 证明：7|2222⁵⁵⁵⁵+5555²²²².

1.2.6. 利用Fermat小定理求解下列同余式方程.

（1）6x≡5（mod7）；（2）5x≡7（mod11）；

（3）28x≡9（mod43）；（4）106x≡29（mod89）.