发布时间 : 星期一 文章初等数论更新完毕开始阅读
算术基本定理(素数唯一分解定理):任何一大于1的整数均可以分解为素数的乘积,若不考虑素数乘积的先后顺序,则分解式是唯一的。 例如:
。当一个整数分解成素数的乘积时,其中有些素数可以重复出现。
例如在上面的分解式中,2出现了三次。把分解式中相同的素数的积写成幂的形式,我们就可以把大于1的正整数写成
(1)
此式称为的标准分解式。这样,算术基本定理也可以描述为大于1的整数的标准分解式是唯一的(不考虑乘积的先后顺序)。 推论1.若的标准分解式是(1)式,则
应说明(2)不能称为是有可能不含有某个素因数推论2.设
,且
是的正因数的充要条件是: (2)
的标准分解式,,其原因是其中的某些,因而
)
也是整数的次方。特别
可能取零值(
也
,若是整数的次方,则也是整数的平方。
地,若是整数的平方,则3. 欧拉(Euler)函数设正整数0,1,??的标准分解式是 例如:
以下我们讲述同余的概念:
中与互素的个数,称之为的欧拉函数,并记为
,则
的计算公式是:
;
.
。若
同余的概念是高斯(Gauss)在1800年左右给出的。设整数
,所得的余数相同,则称为与关于模
不同余。
,若对模
,则称和对模
不同余,记作
是正整数,若用去除
同余,记作,否则,
称为与关于模定义1.(同余)设若不然,则称
和
同余,记作。例如:
;,
等等。
当
时,
,则称是对模
的最小非负剩余。
除得的余数相同。对于固
由带余除法可知,和对模定的模性质1.
,模
同余的充要条件是与被
的同余式与通常的等式有许多类似的性质:
的充要条件是
也即
。
性质2.同余关系满足以下规律: (1)(反身性)(2)(对称性)若(3)(传递性)若(4)(同余式相加)若(5)(同余式相乘)若
; ,则,
,,
; ,则
,则,则
;
;
;
反复利用(4)(5),可以对多个两个的(模相同的)同余式建立加、减和乘法的运算公式。特别地,由(5)易推出:若
,
为整数且
,则未必能
;但是同余式的消去律一般并不成立,即从
推出
,可是我们却有以下结果:
(6)若,则
,即在与
,由此可以推出,若,则有
互素时,可以在原同余式两边约去而不改变模(这一点再
一次说明了互素的重要性)。
现在提及几个与模相关的简单而有用的性质: (7)若(8)若(9)若
两两互素时,则有
,,
|
,则,则
,则
; ; ;
,特别地,若
性质3.若性质4.设
,则
是系数全为整数的多项式,若
,则
;;
。
这一性质在计算时特别有用:在计算大数字的式子时,可以改变成与它同余的小的数字,使计算大大地简化。如例3。 定义2.设在取定某数
,是使
成立的最小正整,则称
为对模
的阶。
后,按照同余关系把彼此同余的整数归为一类,这些数称为模
划分为了
的剩余类。
一个类的任何一个数,都称为该类所有数的剩余。显然,同类的余数相同,不同类的余数不相同,这样我们就把全体整数按照模
。在上述的
剩余,可以得到
个数
,称为模
个剩余类:
个剩余类中,每一类任意取一个
的一个完全剩余系。例如关系模7,
下面的每一组数都是一个完全剩余系: 0,1,2,3,4,5,6; -7,8,16,3,-10,40,20; -3,-2,-1,0,1,2,3。 显然,一组整数成为模数关于模剩余系。模
的完全剩余系只需要满足两个条件(1)有
个数;(2)各
两两不同余。最常用的完全剩余系是最小非负完全剩余系及绝对值最小完全的最小非负完全剩余系是:0,1,2,???,
;即除数为
时,余数
可能取到的数的全部值。
当当
为奇数时,绝对值最小的完全剩余系是:为偶数时,绝对值最小的完全剩余系有两个:
;
;
。
以上只是我们个人对同余及剩余类的理解,为了方便大家研究,我们把有关材料上的具体概念给出,希望大家好好地研究: 定义3.(同余类)设类为模
的同余类。
来分类,确切地说,若和模
同余,则和属同一类,
,每一个这样的
说明:整数集合可以按模
否则不属于同一类,每一个这样的类为模的一个同余类。由带余除法,任一整数必恰
与0,1,??,因
此
模
中的一个模共
有
同余,而0,1,??,
个
不
同。
的
这同
个数彼此模余
类
不同余,,
即
例如,模2的同余类共有两个,即通常说的偶数类与奇数类,这两类中的数分别具有形式
和
(为任意整数)。
是正整数,把全体整按对模,其中
的余数分成
类,相应的
,称为模
个
定义4。(剩余类)设集合记为:
的一个剩余类。以下是几条常用性质: (1)
且
; 的一个里;
,则
的充要条件是
称为模
。
的完全剩余系,如果对任意有且。换一种说法更好理解: 中任取一个
,得
个数
(2)每一个整数仅在(3)对于任意
定义5.(完全剩余系)一组数仅有一个设
是对模为模
的剩余,即
的全部剩余类,从每个的一个完全剩余系。
组成的数组,叫做模说明:在
个剩余类中各任取一个数作为代表,这样的
的完系。换句话说,
个数
是模
个数称为模称为模
的一个完全剩
余系,简称模们彼此模
的一个完系,是指它
的最
不同余,例如0,1,2,??,的一个完系,这称作是模
小非负完系。 性质:(1) (2)若典例分析
个整数构成模
的一个完全剩余系
同时跑遍模
两两对模不同余; 的完全剩余系。
,则与
例1.试解方程:。
解:因为左边是整数,因而右边的分式也应该是整数,所以