同余定理

程序设计

发布日期: 2018-09-10

1.同余定理

同余定理是数论中的重要概念。给定一个正整数m，如果两个整数a和b满足（a-b）能够被m整除，即（a-b）/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。

1.1证明

充分性：若a和b用m相除留下相同的余数r，则 a=q1m+r, b=q2m+r,q1和q2为某两个整数，由此的a-b=(q1m+r)-(q2m-r)=m(q1-q2)，根据整除定义，我们有m|(a-b)，由同余式定义得出结论：a≡b(mod m) 必要性：若a和b用m相除留下相同的余数r，则 a=q1m+r,b=q2m+r,所以a-b=m(q1-q2) 故 m|(a-b)。

1.2同余性质

反身性：a≡a (mod m)
对称性：若a≡b(mod m)，则b≡a(mod m)
传递性：若a≡b(mod m)，b≡c(mod m)，则a≡c(mod m)
同余式相加：若a≡b(mod m)，b≡c(mod m)，则a ± c≡b ± d(mod m)
同余式相乘：若a≡b(mod m)，b≡c(mod m)，则ac≡bd(mod m)
线性运算：如果a≡b(mod m)，c≡d(mod m)，那么a ± c≡b ± d(mod m)，且a * c≡b * d(mod m)
除法：若ac ≡ bc (mod m) c≠0 则 a≡ b (mod m/gcd(c,m)) 其中gcd(c,m)表示c,m的最大公约数。特殊地 ,gcd(c,m)=1 则a ≡ b (mod m)
幂运算：如果a ≡ b (mod m)，那么a^n ≡ b^n (mod m)
若a ≡ b (mod m)，n|m,则 a ≡ b (mod n)
若a ≡ b (mod mi) (i=1,2…n) 则 a ≡ b (mod [m1,m2,…mn]) 其中[m1,m2,…mn]表示m1,m2,…mn的最小公倍数.

2.欧拉定理

在数论中，欧拉定理（也称费马-欧拉定理或欧拉 ${\varphi }$ 函数定理）是一个关于同余的性质。欧拉定理表明，若 $n,a$ )为正整数，且 $n,a$ )互素（即 $\gcd(a,n)=1$ ），则 $a^{ {\varphi (n)}}\equiv 1{\pmod n}$ 即{ $a^{ {\varphi (n)}}$ )与1在模n下同余；φ(n)为欧拉函数。欧拉定理得名于瑞士数学家莱昂哈德·欧拉。欧拉定理实际上是费马小定理的推广。

2.1欧拉函数

在数论中，对正整数n，欧拉函数 $\varphi (n)$ )是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为φ函数（由高斯所命名）或是欧拉总计函数[1]（totient function，由西尔维斯特所命名）。欧拉函数实际上是模n的同余类所构成的乘法群（即环 ${\mathbb {Z}}/n{\mathbb {Z}}$ )的所有单位元组成的乘法群）的阶。这个性质与拉格朗日定理一起构成了欧拉定理的证明。 1736年，欧拉证明了费马小定理 [2]：

假若 $p$ 为质数， $a$ 为任意正整数，那么 $a^{p}-a$ 可被 $p$ 整除。

然后欧拉予以一般化：

假若 $a$ 与 $n$ 互质，那么 $a^{\varphi (n)}-1$ 可被 $n$ 整除。亦即， $a^{ {\varphi (n)}}\equiv 1{\pmod n}$ 。

其中 $\varphi (n)$ 即为欧拉总计函数。如果 $n$ 为质数，那么 $\varphi (n)=n-1$ )，因此，有高斯的版本[3]：

假若 $p$ 为质数， $a$ 与 $p$ 互质（ $a$ 不是 $p$ 的倍数），那么 $a^{ {p-1}}\equiv 1{\pmod p}$ 。

2.1.1欧拉函数的值

$\varphi (1)=1$ （小于等于1的正整数中唯一和1互质的数就是1本身）。若n是质数p的k次幂， $\varphi (n)=\varphi (p^{k})=p^{k}-p^{ {k-1}}=(p-1)p^{ {k-1}}$ )，因为除了p的倍数外，其他数都跟n互质。欧拉函数是积性函数，即是说若m,n互质， $\varphi (mn)=\varphi (m)\varphi (n)$ )。当A与B是互素时，Euler(A*B)=Euler(A)*Euler(B)，即欧拉函数是积性函数，但不是完全积性函数。证明：设A, B, C是跟m, n, _mn_互质的数的集，据中国剩余定理， $A\times B$ )和 $C$ )可建立双射(一一对应)的关系。（或者也可以从初等代数角度给出欧拉函数积性的简单证明）因此 $\varphi (n)$ )的值使用算术基本定理便知，

若 $n=p_{1}^{ {k_{1}}}p_{2}^{ {k_{2}}}\cdots p_{r}^{ {k_{r}}}$

则 $\varphi (n)=\prod _{ {i=1}}^{r}p_{i}^{ {k_{i}-1}}(p_{i}-1)=\prod _{ {p\mid n}}p^{ {\alpha _{p}-1}}(p-1)=n\prod _{ {p|n}}\left(1-{\frac {1}{p}}\right)$ 。

欧拉函数的求法，Euler(A)=A(1-1/p1)(1-1/p2)….(1-1/pn)。（p为A的分解质因数中的不同的质因数）

其中 $\alpha _{p}$ 是使得 $p^{ {\alpha }}$ )整除 $n$ 的最大整数 $\alpha$ （这里 $\alpha _{ {p_{i}}}=k_{i}$ ）。例如 $\varphi (72)=\varphi (2^{3}\times 3^{2})=2^{ {3-1}}(2-1)\times 3^{ {2-1}}(3-1)=2^{2}\times 1\times 3\times 2=24$

2.1.1.1欧拉函数c++实现

1.对于素数A，有Euler(A)=A(1-1/A)=A-1。（A有且只有一个质因子，它自己） 2.如果对于任意数A和素数p，有A%p==0，那么Euler(A*p)=p*Euler(A)。（证明：设A的质因子为p,P1,P2,..Pn，那么A*p的质因子也一定是p,P1,P2,..Pn，所以Euler(A)=A\(1-1/p)(1-1/P1)…(1-1/Pn)，Euler(A*p)=A*p(1-1/p)(1-1/P1)…(1-1/Pn)，所以Euler(A*p)=Euler(A)*p。） 3.如果对于任意数A和素数p,有A%p!=0,那么A与p互素，所以Euler(A*p)=Euler(A)*Euler(p)=Euler(A)(p-1)。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int euler(int n) {
    int res = n;
    for (int i = 2; i*i <= n; i++) {
        if (n % i == 0) {
            n /= i;
            res = res - res / i;
        }
        while (n % i == 0)
            n /= i;
    }
    if(n>1)
        res =res - res/n;
    return res;
}
int main(){
    int n;
    while(cin>>n)
    cout<<euler(n)<<endl;

    return 0;
}

3.费马小定理

费马小定理是数论中的一个定理：假如 $a$ )是一个整数， $p$ )是一个质数，那么 $a^{p}-a$ 是p的倍数，可以表示为

$a^{p}\equiv a{\pmod {p}}$

如果a不是p的倍数，这个定理也可以写成

$a^{ {p-1}}\equiv 1{\pmod {p}}$ )[1]

这个书写方式更加常用。

4.中国剩余定理

用现代数学的语言来说明的话，中国剩余定理给出了以下的一元线性同余方程组：

$(S) : \quad \left\{ \begin{matrix} x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \\ \vdots \qquad\qquad\qquad \\ x \equiv a_n \pmod {m_n} \end{matrix} \right.$

有解的判定条件，并用构造法给出了在有解情况下解的具体形式。中国剩余定理说明：假设整数m1, m2, … , mn其中任两数互质，则对任意的整数：a1, a2, … , an，方程组 $(S)$ 有解，并且通解可以用如下方式构造得到：

设 $M = m_1 \times m_2 \times \cdots \times m_n = \prod_{i=1}^n m_i$ 是整数m1, m2, … , mn的乘积，并设 $M_i = M/m_i, \; \; \forall i \in \{1, 2, \cdots , n\}$ )，即 $M_{i}$ 是除了mi以外的n − 1个整数的乘积。
设 $t_i = M_i^{-1}$ )为 $M_{i}$ )模 $m_{i}$ )的数论倒数： $t_i M_i \equiv 1 \pmod {m_i}, \; \; \forall i \in \{1, 2, \cdots , n\}.$
方程组 $(S)$ 的通解形式为： $x = a_1 t_1 M_1 + a_2 t_2 M_2 + \cdots + a_n t_n M_n + k M= k M + \sum_{i=1}^n a_i t_i M_i, \quad k \in \mathbb{Z}.$ 在模 $M$ )的意义下，方程组 $(S)$ 只有一个解： $x = \sum_{i=1}^n a_i t_i M_i.$ 。