同余定理

程序设计

发布日期: 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 }$
{\varphi }

函数定理）是一个关于同余的性质。欧拉定理表明，若

$n,a$

n,a

)为正整数，且

$n,a$

n,a

)互素（即

$\gcd(a,n)=1$

\gcd(a,n)=1

），则

$a^{ {\varphi (n)}}\equiv 1{\pmod n}$

a^{ {\varphi (n)}}\equiv 1{\pmod n}

即{

$a^{ {\varphi (n)}}$

a^{ {\varphi (n)}}

)与1在模n下同余；φ(n)为欧拉函数。欧拉定理得名于瑞士数学家莱昂哈德·欧拉。欧拉定理实际上是费马小定理的推广。

2.1欧拉函数

在数论中，对正整数n，欧拉函数

$\varphi (n)$

\varphi (n)

)是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为φ函数（由高斯所命名）或是欧拉总计函数[1]（totient function，由西尔维斯特所命名）。欧拉函数实际上是模n的同余类所构成的乘法群（即环

${\mathbb {Z}}/n{\mathbb {Z}}$

{\mathbb {Z}}/n{\mathbb {Z}}

)的所有单位元组成的乘法群）的阶。这个性质与拉格朗日定理一起构成了欧拉定理的证明。 1736年，欧拉证明了费马小定理 [2]：

假若

$p$

为质数，

$a$

为任意正整数，那么

$a^{p}-a$

a^{p}-a

可被

$p$

整除。

然后欧拉予以一般化：

假若

$a$

与

$n$

互质，那么

$a^{\varphi (n)}-1$

{\displaystyle a^{\varphi (n)}-1}

可被

$n$

整除。亦即，

$a^{ {\varphi (n)}}\equiv 1{\pmod n}$

a^{ {\varphi (n)}}\equiv 1{\pmod n}

。

其中

$\varphi (n)$

\varphi (n)

即为欧拉总计函数。如果

$n$

为质数，那么

$\varphi (n)=n-1$

{\displaystyle \varphi (n)=n-1}

)，因此，有高斯的版本[3]：

假若

$p$

为质数，

$a$

与

$p$

互质（

$a$

不是

$p$

的倍数），那么

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

a^{ {p-1}}\equiv 1{\pmod p}

。

2.1.1欧拉函数的值

$\varphi (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}}$

\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)$

\varphi (mn)=\varphi (m)\varphi (n)

)。当A与B是互素时，Euler(A*B)=Euler(A)*Euler(B)，即欧拉函数是积性函数，但不是完全积性函数。证明：设A, B, C是跟m, n, _mn_互质的数的集，据中国剩余定理，

$A\times B$

A\times B

)和

$C$

)可建立双射(一一对应)的关系。（或者也可以从初等代数角度给出欧拉函数积性的简单证明）因此

$\varphi (n)$

\varphi (n)

)的值使用算术基本定理便知，

若

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

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)$

\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}$

\alpha _{p}

是使得

$p^{ {\alpha }}$

p^{ {\alpha }}

)整除

$n$

的最大整数

$\alpha$

\alpha

（这里

$\alpha _{ {p_{i}}}=k_{i}$

\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$

\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$

a^{p}-a

是p的倍数，可以表示为

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

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

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

$a^{ {p-1}}\equiv 1{\pmod {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.$

(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)$

(S)

有解，并且通解可以用如下方式构造得到：

设
$M = m_1 \times m_2 \times \cdots \times m_n = \prod_{i=1}^n m_i$
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 = M/m_i, \; \; \forall i \in \{1, 2, \cdots , n\}
)，即
$M_{i}$
M_{i}
是除了mi以外的n − 1个整数的乘积。
设
$t_i = M_i^{-1}$
t_i = M_i^{-1}
)为
$M_{i}$
M_{i}
)模
$m_{i}$
m_{i}
)的数论倒数：
$t_i M_i \equiv 1 \pmod {m_i}, \; \; \forall i \in \{1, 2, \cdots , n\}.$
t_i M_i \equiv 1 \pmod {m_i}, \; \; \forall i \in \{1, 2, \cdots , n\}.
方程组
$(S)$
(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}.$
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$
M
)的意义下，方程组
$(S)$
(S)
只有一个解：
$x = \sum_{i=1}^n a_i t_i M_i.$
x = \sum_{i=1}^n a_i t_i M_i.
。