初等数论四大定理

• 威尔逊定理

• 欧拉定理（数论中的欧拉定理）

• 中国剩余定理（又称孙子定理）

• 费马小定理

相关定义

积性函数

积性函数：对于任意互质的整数和有性质的数论函数

完全积性函数：对于任意整数和有性质的数论函数

积性函数的性质

性质一

这和算数基本定理有关

若将n表示成质因子分解式

则有

性质二

若f为积性函数且有

则f为完全积性函数

非积性函数

冯·曼戈尔特函数：当n是质数p的整数幂，，否则

不大于正整数n的质数的数目

整数拆分的数目：一个整数能表示成正整数之和的方法的数目

取余的性质

对于基本的四种运算而言，加减乘都符合“分配率”，唯独除法不满足。

如果要实现除法，那么必须把除法转换为乘法，假设是关于的逆元。

完全剩余系

完全剩余系： 从模n的每个剩余类中各取一个数，得到一个由n个数组成的集合，叫做模n的一个完全剩余系。完全剩余系常用于数论中存在性证明。

在模n的剩余类中各取一个元素，则这n个数就构成了模n的一个完全剩余系。

命n为一个自然数，a，b为整数。如果a-b为n的整数倍，则称a，b关于n同余，用同余式记之。否则称a，b关于n不同余，记为。我们称n为同余式的模。同余式满足：

- 反射性（reflection），即

- 对称性（symmetry），即由可得

- 传递性（transitivity），即由 , 可得

因此，可以利用同余关系将整数分类，凡同余的数属于一个类，于是异类中的数皆不同余。共得到整数的n个类。在每一个类中各取一个数作为代表所成的集合称为模n的一个完全剩余系。

举例

取最小非负剩余为代表，则得完全剩余系{0,1,2,...,n-1}。剩余类的代表相加得一数属于另一类，这个类仅与相加两数所在的类有关，而与代表的选取无关。于是，可以定义剩余类间的加法，以0所在的类O为单位元，则剩余类的全体关于加法构成一个交换群。当然在剩余类之间可以定义乘法。但关于除法就不一定可能，例如：，，但是

一个数除以4的余数只能是0，1，2，3，{0，1，2，3}和{4，5，-2，11}是模4的完全剩余系。可以看出0和4，1和5，2和-2，3和11模4同余，这4组数分别属于四个剩余类。

性质

(m,n)=1 -> m、n两个数的最大公约数是1

1. 对于n个整数，其构成模n的完全系等价于其关于模n两两不同余

2. 若构成模n的完系，，则也构成模n的完系

3. 若构成模n的完系，则

剩余类

剩余类，亦称同余类，是一种数学的用语，为数论的基本概念之一。

设模为n，则根据余数可将所有的整数分为n类，把所有与整数a模n同余的整数构成的集合叫做模n的一个剩余类，记做[a]。并把a叫做剩余类[a]的一个代表元。

定义

一个整数被正整数n除后，余数有n中情形：0，1，2，3，。。。，n-1，他们彼此对模n不同余。这表明，每个整数恰与这n个整数中的某一个对模n同余。这样一来，按模n是否同余对整数集进行分类，可以将整数集分成n个两两不相交的子集。我们把（所有）对模n同余的整数构成的一个集合叫做模n的一个剩余类。

模m的剩余类具有以下性质

1. 每一个整数恰包含在某一个类里()

2. 两个整数x，y属于同一类的充分必要条件是

剩余类与完全剩余类

由此可引出抽象代数中的重要概念，如群论中的陪集，环论中的剩余类等。任取n，这n个数(o, 1, ..., n-1)称为模n的一个完全剩余类。每个数称为相应类的代表元。最常用的完全剩余系是{0, 1, ..., n-1}。

1. 若，则n个整数，构成一个完全剩余系数的充分必要条件是这n个除n的余数两两不相等。

2. 若，当为完全剩余系时，也为完全剩余系数。

3. 若，则当是完全剩余系数时，也构成完全剩余系

剩余类与简化剩余类

在剩余类选取一个与n互素代表元构成简化剩余类

1. ，当为简化剩余系时，也为简化剩余系数。

2. 若，则当是简化剩余系数时，也构成完全剩余系

缩系

简化剩余系也称既约剩余系、缩系，是数学术语。

缩系的定义：如果一个模m的剩余类里面的数与m互素（显然，只需有一个与m互素，其余的均与m互素）就把它叫做一个与模m互素的剩余类，在与模m互素的全部剩余类中，各取一数所组成的集叫做模m的一组简化剩余系

若整数模n分别对应中所有m个与n互素的自然数，则称集合为模n的一个缩系

缩系的性质：

1. 对于任意的与n互质的正整数k，若{}为模n的一个缩系，(k,n)=1，则{}也为模n的一个缩系

2.

威尔逊定理

欧拉定理

中国剩余定理

费马小定理

费马小定理(Fermat's little theorem)是数论中的一个重要定理，在1636年由 皮埃尔·德·费马 提出。如果p是一个质数，而(整数a不是p的倍数)，则有

根据费马小定理，可以发现也成立。可知是关于的逆元。所以求的逆元，就直接用快速幂求就可以

LL power(LL a, int x) {
	LL ans = 1;
	while(x) {
		if(x&1) ans = (ans * a) %mod;
		a = (a * a) %mod;
		x >>= 1;
	}
	return ans;
}

LL inv(LL a) {
	return power(a, mod - 2);
}

实际上，它是欧拉定理的一个特殊情况（即）

有些学家独立制作相关的假说（有时也被错误的称为中国的假说），当成立时，p是素数。这是费马小定理的一个特殊情况。然而，这一假说的前设是错误的：例如，341，而341=11*31是一个伪素数。所有的伪素数都是此假说的反例。

如上所述，中国猜测仅有一半是正确的。符合中国猜测但不是素数的数被称为伪素数。

更极端的反例是卡迈克尔数：假设a与561互质，则被561除都余1.这样的数被称为卡迈克尔数，561是最小的卡迈克尔数。

验证推倒

引理1

若a,b,c为任意三个整数，m为正整数，且(m,c)=1，则当时有

证明：可得可得。因为(m,c)=1即m,c互质，c可以约去，可得

引理2

设m是一个整数且m>1，b是一个整数且(m,b)=1。如果是模m的一个完全剩余系，则也构成模m的一个完全剩余系。

证明：若存在2个整数同余即，根据引理1则有。根据完全剩余系的定义可知这是不可能的，因此不存在两个整数同余。

所以构成模m的一个完全剩余系。

构造素数的完全剩余系

因为，由引理2可得 也是的一个完全剩余系。由完全剩余系的性质，

即

易知，同余式两边可约去，得到

计算除以13的余数

故余数为3

证明对于任意整数a而言，恒为2730的倍数。13-1为12，12的正因数有1，2，3，4，6，12，分别加1，为2，3，4，5，7，13，其中2，3，5，7，13为质数，根据定理 为2的倍数、为3的倍数、为5的倍数、为7的倍数、为13的倍数，即的倍数。

>>> n =221
>>> a = 38
>>> pow(a ,n -1,n)
1

"""221 may be a prime number."""
import random
def isprime(n,k=128):
    if n<2:
        return False
    for _ in range(k):
        a = random.randrange(1,n)
        if pow(a,n-1,n)!=1:
        return False
    return True