博客

同余式性质应用非常广泛，在处理某些整除性、进位制、对整数分类、解不定方程等方面的问题中有着不可替代的功能，与之密切相关的的数论定理有欧拉定理、费尔马定理和中国剩余定理。

基础知识

三个数论函数

对于任何正整数均有定义的函数，称为数论函数。在初等数论中，所能用到的无非也就有三个，分别为：高斯(Gauss)取整函数[

x

]及其性质，除数函数

d

(

n

)和欧拉(Euler)函数



和它的计算公式。

1．




高斯(Gauss)取整函数[



]

设



是实数，不大于



的最大整数称为



的整数部分，记为[



]；



称为



的小数部分，记为｛



｝。例如：［0.5］＝0，



等等。

由



的定义可得如下性质：

性质1.



；

性质2.



；

性质3.设



，则



；

性质4.



;



;

性质5.






；

性质6.对于任意的正整数



，都有如下的埃米特恒等式成立：

；

为了描述性质7，我们给出如下记号：若



，且







，则称为



恰好整除



，记为



。例如：我们有



等等，其实，由整数唯一分解定理：


任何大于


1


的整数







能唯一地写成







的形式，其中







为质（素）数（







）。我们还可以得到：







。

性质


7.


若







，则

请注意，此式虽然被写成了无限的形式，但实际上对于固定的



，必存在正整数



，使得



，因而



，故



，而且对于



时，都有



。因此，上式实际上是有限项的和。另外，此式也指出了乘数



的标准分解式中，素因数



的指数



的计算方法。

2


．除数函数

d

(

n

)

正整数



的正因数的个数称为除数函数，记为

d

(

n

)。这里给出

d

(

n

)的计算公式：

d



(

n

)


＝



，



为素数唯一分解定理中的指数。为了叙述地更加明确，我们组出素数唯一分解定理。

算术基本定理（素数唯一分解定理）



：任何一大于1的整数均可以分解为素数的乘积，若不考虑素数乘积的先后顺序，则分解式是唯一的。

例如：



。当一个整数分解成素数的乘积时，其中有些素数可以重复出现。例如在上面的分解式中，2出现了三次。把分解式中相同的素数的积写成幂的形式，我们就可以把大于1的正整数



写成







（


1


）

此式称为







的标准分解式。这样，算术基本定理也可以描述为大于1的整数的标准分解式是唯一的（不考虑乘积的先后顺序）。

推论1

.若



的标准分解式是（1）式，则



是



的正因数的充要条件是：

（


2


）

应说明（


2


）不能称为是







的标准分解式，，其原因是其中的某些







可能取零值（







也有可能不含有某个素因数







，因而







）

推论




2



.


设







，且







，若