首先声明:下文中所有的类似”因数“”整数“等的字眼,除特别说明,全部是对于正数而言,不包括负数或者是(0)。
Case 1. 欧拉定理
欧拉定理即:
对于 (p) 为素数,(a) 为任意正整数,存在
[a^{varphi_p} equiv 1 pmod p
]
其中 (gcd(a,p)=1).
说明: (varphi_p) 为 (leq p) 的数中与 (p) 互质的数的个数。
证:
令
[S = varphi_p
]
构造数列:
[X_1,X_2 cdots X_S
]
满足对于 (1 leq i leq S) 有:
[gcd(X_i,p)=1
]
显然存在这样的构造。
下面,由:
[gcd(X_i,p)=1
]
[gcd(a,p)=1
]
可得
[gcd(X_i cdot a , p)=1
]
即
[prod_{i=1}^S X_i equiv prod_{i=1}^S X_i cdot a pmod p
]
下面证明另一个定理。
证 (1).
定理 (1).
对于
[a equiv b pmod p
]
且 (gcd(c,p)=1)
则:
[frac{a}{c} equiv frac{b}{c} pmod p
]
这是因为除以(c)不会影响对(p)的取模。
回到原证,可得:
[prod_{i=1}^S a equiv 1 pmod p
]
代入 (S = varphi_p)
即为:
[a^{varphi_p} equiv 1 pmod p
]
得证。
Case 2. 费马小定理
费马小定理即:对于 (p) 为素数, (a) 为正整数,有:
[a^{p-1}equiv 1 pmod p
]
其中 (gcd(a,p)=1).
首先,我们有欧拉定理:
[a^{varphi_p} equiv 1 pmod p
]
当 (p) 为质数,显然 (varphi_p = p-1) ,则:
[a^{p-1} equiv 1 pmod p
]
得证。
Case 3. 威尔逊定理
威尔逊定理即:对于 (p) 为素数,有:
[(p-1)! equiv -1 pmod p
]
证 (1).
定理 (2):
对于质数 (p) ,在 (2 - (p-2)) 中不存在任何一个数自己是自己的逆元。
反证:若存在,设为 (a). 即:
[a^2 equiv 1 pmod p
]
[a^2-1 equiv 0 pmod p
]
[(a-1)(a+1) equiv 0 pmod p
]
必然存在 (a-1=0) 或 (a+1=p)
则:
(a=1) 或 (a=p-1)
所以,在 (2 - (p-2)) 中不存在任何一个数自己是自己的逆元。
得证。
证 (2).
定理 (2) :
(a) 是 (b) 的逆元 和 (b) 是 (a) 的逆元这两句话,必然同时成立或同时不成立。
反证:若其中一个成立,另一个不成立。必然有:
(ab equiv 1 pmod p)
此时两个都成立。矛盾。
得证。
证 (3).
定理 (3):
对于 (p) 为质数且 (p>2),可以将 (2 - (p-2)) 的数两两分为一组,满足每组的两个数互为逆元。
显然,由定理 (1) 和 定理 (2) 可知 逆元的一一配对性。
得证。
下面回到原证。
根据定理 (3) ,直接分为 (S) 组,并将第 (i) 组的第一个称为 (a_i) ,第二个称为 (b_i).
此时:
[(p-1)! equiv prod_{i=2}^{p-2} i cdot (p-1) equiv prod_{i=1}^S ( a_i cdot b_i ) cdot (p-1) equiv ( prod_{i=1}^S 1 ) cdot (p-1) equiv (p-1) equiv -1 pmod p
]
得证。
Case 4. 孙子定理
孙子定理(也称中国剩余定理)即:
对于:
[S=
egin{cases}
x equiv a_1 pmod {m_1} \
x equiv a_2 pmod {m_2} \
vdots \
x equiv a_n pmod {m_n}
end{cases}
]
且 (m_i) 两两互质,此时:
(S) 必然有解,并且在 (prod_{i=1}^n m_i) 中只有一个解。(对于任意的 (a_i))
Case 4.1 证明存在性
构造法:
令
[M = prod_{i=1}^n m_i
]
[M_i = frac{M}{m_i}
]
[t_i cdot M_i equiv 1 pmod m_i
]
(即 (t_i) 为 (M_i) 关于 (m_i) 的逆元。
此时 (S) 的 解 (x) 满足:
[xequiv sum_{i=1}^n a_i cdot t_i cdot M_i pmod M
]
如何说明该解成立?
对于任何一组方程 (x equiv a_i pmod m_i)
除了 (a_i cdot M_i cdot t_i) 这一项满足:
[a_i cdot M_i cdot t_i equiv a_i pmod m_i
]
其余项均有:
[a_j cdot M_j cdot t_j equiv 0 pmod m_i
]
这是因为,(j
ot = {i}) 时,必然 (M_j equiv 0 pmod m_i).
所以其它项对 (m_i) 的取模没有影响,满足该式。
进而 (S) 被满足。
Case 4.2 证明唯一性
由于:
[xequiv sum_{i=1}^n a_i cdot t_i cdot M_i pmod M
]
所以,如果存在两个数 (x_1) ,(x_2) 均满足上式,且均 ( x_2)
必然有:
[x_1 - x_2 equiv 0 pmod M
]
由于 (x_1,x_2 < M) ,所以 (x_1 - x_2 < M).
再由上述可知
[x_1 = x_2
]
由此“存在两个数”的假设矛盾。
得证。
Case 5. 应用
Case 5.1 欧拉定理与费马小定理
可以发现,费马小定理是欧拉定理的一种特殊情况。
如果求 (a) 关于 (p) 的逆元且 (p) 为质数,由费马小定理有:
[a^{p-1} equiv 1 pmod p
]
得出:
[a imes a^{p-2} equiv 1 pmod p
]
所以 (a) 关于 (p) 的逆元即为 (a^{p-2}).
用快速幂计算,可以达到单次查询 (O(log p)) 的时间复杂度。
Case 5.2 威尔逊定理
当我们求 ((n-1)! mod n) 时:((n>1))
如果 (n) 为质数,由威尔逊定理得答案为 (n-2).
如果 (n) 为合数,先证明算术基本定理(或称唯一分解定理):
证 (1).
定理 (1).
大于1的自然数必可写成质数的乘积。
反证:若存在一些不可写成质数乘积的数,设其其中最小的为 (n).
首先 (n>1) ,那么 (n) 只会是质数或者合数。
如果 (n) 是质数,那么 (n=n) 就是质数的乘积形式。
否则,(n) 必然是合数,存在 (a imes b = n) 且 (a,b
由于 (n) 是不满足该性质“最小”的数,所以 (a) 与 (b) 均满足,均可表示为质数的乘积;那么 (n) 也可以被表示为质数的乘积。矛盾。
得证。
我们回到原证:
(n) 为合数,将 (n) 质因数分解,则其标准分解式为:
[n=prod_{i=1}^k {p_i}^{a_i}
]
其中 (p_i) 为质数, (a_i) 为正整数。
由于算术基本定理,存在这样的分解。下面将 (p_i) 取出,也就是 (n) 的所有质因子为:
[p_1,p_2 cdots p_k
]
其中对于 (1 leq i < k) ,有 (p_i < p_{i+1})
那么,(p_k) 也就是 (n) 最大质因子必然 (
这是因为 (n-1 | n) 当 (n>2) 时恒不成立。
也就是说,对于 (1 leq i leq k) ,都存在:
[p_i < n-1
]
也就是说, ((n-1)!) 中包含 (n) 的所有质因子。
证 (2).
定理 (2) :
如果一个数 (n) 的所有质因子的指数都比另一个数 (a) 的小(或等于)。此时可以得出:
[n | a
]
这是显然的一个定理,只需说明,不必证明。
证 (3).
推论 (3) :(其中 (n) 为合数)
[n | (n-1)!
]
由定理 (2) 推论:
假设 (n) 有质因子 (p) ,则其个数最多为 ({log}_p n).
而在 ((n-1)!) 中,则有:
[sum_{p|i}^{n-p} {log}_p i
]
很显然,这是多于 (n) 的个数(也有可能等于)。读者可以自证。
由于 (n) 是合数,显然 (n geq 4).
但是,对于 (n=4) 的合数情况,不满足 (4 | 3!),所以应当特殊判断之。
而 $3! mod 4 = 6 mod 4 = 2 $.
回到原证,由定理 (3) 可知:
[n | (n-1)!
]
这可以说明:
[(n-1)! mod n = 0
]
所以最终结论为:
求 ((n-1)! mod n) 的值((n>1)):
如果 (n) 为质数,那么答案为 (n-1).
否则 (n) 为合数,那么当 (n=4) 时答案为 (2) ,否则为 (0).
Case 5.3 算术基本定理(唯一分解定理)
算术基本定理上面已经证毕。而其应用就在于:
可以将一个 (>1) 的 合数 表达为若干个质数的乘积。其应用广泛,若
[n=prod_{i=1}^k {p_i}^{a_i}
]
(其中 (p_i) 为质数,(a_i) 为正整数)
则具有以下的应用:
1.求 (n) 的因数个数。此时由组合可以得到,(n) 的因数个数为 (prod_{i=1}^k (a_i+1)).
求 (n) 的因数之和。此时仍然由组合可以得到,(n) 的因数之和为 (prod_{i=1}^k sum_{j=0}^{a_i} (p_i)^j)
可以重新定义 (gcd(a,b)) 和 (operatorname{lcm}(a,b)).也可以证明 (gcd(a,b) cdots operatorname{lcm}(a,b)=a imes b).
证 (1).
定理 (1).
[gcd(a,b) cdots operatorname{lcm}(a,b)=a imes b
]
首先,将 (a) 和 (b) 质因数分解为:
[a=prod_{i=1}^k {p_i}^{a1_i}
]
[b=prod_{i=1}^k {p_i}^{a2_i}
]
(其中 (p_i) 为质数,(a1_i) 与 (a2_i) 为自然数。即如果两个数中只有一个数是该质数的倍数,那么另一个数中该质数对应的指数就是 (0) )
由质因数分解可以得到:
[gcd(a,b) = prod_{i=1}^k {p_i}^{min(a1_i,a2_i)}
]
[operatorname{lcm}(a,b) = prod_{i=1}^k {p_i}^{min(a1_i,a2_i)}
]
由于:
[min(a,b)+max(a,b)=a+b
]
所以可以得到:
[gcd(a,b) cdot operatorname{lcm}(a,b) = prod_{i=1}^k ({p_i}^{min(a1_i,a2_i)} imes {p_i}^{min(a1_i,a2_i)}) = prod_{i=1}^k {p_i}^{a1_i+a2_i}
]
而:
(a imes b = prod_{i=1}^k {p_i}^{a1_i+a2_i}).
于是可以得到
[gcd(a,b) cdot operatorname{lcm}(a,b) = aimes b
]
得证。
由此可以证明 (sqrt{2}) 是无理数。
证 (1).
定理 (1).
(sqrt{2}) 是无理数。
反证:如果 (sqrt{2}) 是有理数,则其可以表示为:
[sqrt{2}=frac{a}{b}
]
其中 (gcd(a,b)=1)
于是我们可以得到:
[a^2 = 2b^2
]
那么 (2 | a^2),根据完全平方数的性质,存在 (2 | a).
另:如果 (2 | a) 不成立 则 (2 | a^2) 也不成立。矛盾。
由于 (2 | a) ,可以得到 (4 | a^2) ,进而:
(4 | 2b^2),即 (2 | b^2).同理可知 (2 | b).
此时: (2 | gcd(a,b)). 与之前我们假设的 (gcd(a,b)=1) 矛盾。
得证。
由此可以扩展为:
(sqrt{k}) 是无理数当且仅当 (k) 不是完全平方数。
证明素数个数无限。
证 (1).
定理 (1). 素数个数无限。
反证:假设有限,为 (k) 个,且这些质数为:
[p_1,p_2 cdots p_k
]
那么考虑
[(prod_{i=1}^k p_i )+1
]
该数不会被 (p_i) 的任何一个数筛掉。 ((1 leq i leq k))
所以这个数也是质数,并且这个数大于当前所有的质数。
那么,这与我们先前假设的“质数是有限个”是矛盾的。因为用这种方法可以不断加入新的质数并不断计算乘积、再加入新的质数。
得证。
当然还有一些更高级的应用,这里就不再赘述。
Case 5.4 孙子定理
孙子定理(即中国剩余定理)可以求:
[S=
egin{cases}
x equiv a_1 pmod {m_1} \
x equiv a_2 pmod {m_2} \
vdots \
x equiv a_n pmod {m_n}
end{cases}
]
其中(S)方程的解 (x mod (prod_{i=1}^n m_i)).
由此可以求出 满足 (S) 的最小的 (x).
当然,可以求出第 (k) 小。
这在数学域、计算机域都有极大的应用,可以将多个同余方程式合并为一个同余方程式,在解方程组时提供了极大的便利。