108楼火车是运茶的
(碧云天,黄叶地)
发表于 2008-10-14 22:51
只看此人
同余
现在补充介绍同余的概念,并且证明费马小定理。这里讲的数都是整数。
顾名思义,同余就是指两个数除以同一个数,得到的余数相同,这个除数称为模;或者换一种等价的说法,如果两个数的差能够被模p整除,那么这两个数是模p同余的。形式上,把a和b同余于模p记为
a≡b(mod p)
在模明确的情况下,可以不用把后面括号里的东西写出来。
利用同余可以给整数分类。例如,取p=7,则任意一个整数必然同余于0, 1, 2, 3, 4, 5, 6中的某一个。把0当作星期天,一周就是这样周而复始,其实我们日常生活中常常使用同余的性质。月份也是一个典型的例子,十二月过后就是第二年的一月,没有十三月的说法。同余反映出一种周期性的现象。
同余的性质比较多,这边不一一列举。总而言之,只考虑同余的时候,一个数总是能被与它同余的另一个数代替。或者说,同余的数是彼此等价的。
现在看点有意思的。我们知道如果p是素数,那么1, 2, 3, ..., p-1和p都是互素的。而任意一个不是p的倍数的数都必然和这p-1个数中间的某一个模p同余。好了,如果a和p互素那么a同余于{1,2,...,p-1}中的某一个。再来看如果r和p互素,那么ra和p也是互素的(a已经和p是互素的,证明留给读者)。
考虑数a, 2a, 3a, ..., (p-1)a。如下性质成立:
1、它们两两不同余;
2、集合{a,2a,3a,...,(p-1)a}能够和{1,2,3,...,p-1}建立一一对应关系。
这里做简单的证明。1是容易的,因为假设某两个数ma和na同余的话,就会有(m-n)a能被p整除。我假设读者已经在上面证明了这是不可能的。2可以根据1来证明。首先任意一个ma (1<=m<=p-1)总是与{1,2,3...,p-1}中的某一个同余。其次,令1<=b<=p-1,可以用鸽笼原理证明{a,2a,3a,...,(p-1)a}中必有一个数与b同余。
换句话说,如果认为同余的两个数是等价的,那么a, 2a, 3a, ..., (p-1)a就是1, 2, 3, ..., p-1的一个排列。
现在把它们乘起来:
a * 2a * 3a * ... * (p-1)a
=1*2*3*...*(p-1)a^(p-1)
另一方面,我们刚刚知道:
a * 2a * 3a * ... * (p-1)a
≡1*2*3*...*(p-1)
这样就有:
1*2*3*...*(p-1)a^(p-1)≡1*2*3*...*(p-1)
或者:
1*2*3*...*(p-1)*(a^(p-1) - 1)≡0
即p能够整除1*2*3*...*(p-1)*(a^(p-1) - 1),必然的推论就是p能够整除a^(p-1) - 1,所以
a^(p-1)≡1(mod p)
这就是前面讲的费马小定理。.