初等数论四大定理

费马小定理(Fermat's little theorem)

费马小定理：假假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。即$a^{p}\equiv a{\pmod {p}}$ <!--more-->

证明：

法一: gcd（a，p）=1,将$1\cdot a,2\cdot a,....(p-1)\cdot a$共(p-1)个数，将他们分别除以p，余数分别为$r_{1},r_{2}......r_{p-1}$,则集合{$r_{1},r_{2}......r_{p-1}$}为{1，2，3...（p-1)}的重排列，即1,2,3,....,(p-1)在余数中恰好各出现一次，（对于任两个相异$k\cdot a$而言（k=1,2,3....(p-1)），其差不是p的倍数（所以不会有相同余数），且任一个$k\cdot a$亦不为p的倍数（所以余数不为0）。)

$$1\cdot2\cdot\cdot\cdot(p-1)\equiv(1\cdot a)\cdot(1\cdot a)\cdot\cdot\cdot((p-1)\cdot a)(mod p)\Rightarrow W \equiv W\cdot a^{p-1} (mod p)$$

W=1·2·3·...·(p-1)，且(W, p) = 1，因此将整个公式除以W即得到： $\Rightarrow$ $a^{p-1}\equiv a{\pmod {p}}$ 例：计算$2^{100}$除以13的余数 ${2^{100} \equiv 2}$

剩余定理

对于一元线性同余方程组： $$ S：\begin{cases} x \equiv a_{1} \pmod {m_{1}}\ x \equiv a_{2} \pmod {m_{2}}\ ...\ x \equiv a_{n} \pmod {m_{n}} \end{cases} 有解的判定条件。$$

假设整数m1, m2, ... , mn其中任两数互质，则对任意的整数：a1, a2, ... , an，方程组 ${(S)}$有解，并且通解可以用如下方式构造得到： 1.设 ${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$是整数$m_1, m_2, ... , m_n$的乘积，并设${M_{i}=M/m_{i},\;\;\forall i\in {1,2,\cdots ,n}}$，即 ${M_{i}} $是除了mi以外的n − 1个整数的乘积。

2.设 ${t_{i}=M_{i}^{-1}}$模 ${m_{i}}$的数论倒数： ${t_{i}M_{i}\equiv 1{\pmod {m_{i}}},\;\;\forall i\in {1,2,\cdots ,n}.} .$

3.方程组 ${(S)}$的通解形式为：${ x=a_{1}t_{1}M_{1}+a_{2}t_{2}M_{2}+\cdots +a_{n}t_{n}M_{n}+kM=kM+\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}$的意义下，方程组 ${(S)}$ 只有一个解： ${x=\sum {i=1}^{n}a{i}t_{i}M_{i}.}$

威尔逊定理

威尔逊定理：当且仅当p为素数时，有:$(p-1)!\equiv-1(mod p)$ [判定一个自然数是否为素数的充分必要条件]

欧拉定理

若n,a为正整数，且n,a互质，(a,n)=1，则:$ a^{φ(n)}\equiv 1(mod n) $

欧拉函数：$\varphi(n)$ 求小于n与n互质的数的个数,当$\varphi(n)=p-1$即为质数时是费马小定理的定义