同余和剩余类

对于整数 $n>1$ ，同余关系（模n）具有自反性，对称性和传递性，即对任意的 $a,b,c\in Z$ ，有：

一个集合上的等价关系把这个集合分成若干个等价类。这个关系定义在集合Z上，因此它把Z恰好分成n个等价类，每个类包含与某整数模n同余的所有整数。可以表示为：

a = \{x\in Z| x(mod\ n )\equiv a\}

我们将上面每一个集合称为一个模n剩余类。显然，我们可以把 $Z_n$ 看做：

$Z_n = \{0,1,...,n-1\}$

如果把Z看作是Z的一个平凡子集，陪集 $nZ$ 是所有n的倍数的整数集合，即：

nZ=\{0,\plusmn n,... \}

群运算为加法运算的商群：

Z/nZ = \{x+nZ|x\in Z\}

$Z_n$ 中运算的同余性质

对任意的整数 $n>1$ ，if $a\equiv b (mod\ n) \and c\equiv d (mod\ n)$ , then $a \plusmn c \equiv b \plusmn d (mod\ n)$ , $ac \equiv bd (mod\ n)$

假设整数 $n>1,d\neq 0$ , if $ad\equiv bd (mod\ n)$ , then $a\equiv b (mod\ \frac{n}{\gcd(d,n)})$

如果 $f(x)$ 是整数集Z上的一个多项式，并且 $a\equiv b (mod\ n)$ ，其中整数 $n>1$ ，则 $f(a)\equiv f(b) (mod\ n)$

假设整数 $n>1$ ，同余式 $ax \equiv b(mod \ n)$ 可解当且仅当 $gcd(a,n)|b$

中国剩余定理

设正整数 $m_1, m_2, ...,m_k$ 两两互素，则：

$x \equiv a_i (\mod m_i)$ 方程组的解为：

$x \equiv \Sigma a_i M_i M_i ^{-1} (\mod M)$

其中 $M= m_1 m_2...m_k, M_i = M/m_i$

设 $\phi(n)$ 是一个欧拉函数，则：

$\phi (1) =1$ , 如果p是素数，则 $\phi(p) p-1$

欧拉 $\phi$ 函数是积性函数，如果 $gcd(m,n)=1$ ，则 $\phi(mn)=\phi(m)\phi(n)$

如果 $n=p_1^{e_1}p_2^{e_2}...p_k^{e_k}$ 的素分解，则 $\phi(n) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...({1-\frac{1}{p_k}})$

费马小定理：如果p是素数，则 $a^{p-1} \equiv 1 (\mod p), a^p\equiv a(\mod p)$

数学归纳法的证明：

$a=1$ ,显然

假设 $p | (a^p-a)$ ,考虑 $(a+1)^p-(a+1)= \Sigma_{k=0}^p C_p^ka^k-a-1=\Sigma_{k=1}^{p-1} C_p^ka^k+(a^p-a)$

由于 $C_p^k =\frac{p!}{k!(p-k)!}$ ，且p为质数，因此 $p|C_p^k$ ，即 $p|\Sigma_{k=1}^{p-1}C_p^k,p|(a^p-a)$ ，从而 $p|(a+1)^p-(a+1)$

欧拉定理：如果 $gcd (a,n) =1$ ，则 $a^{\phi(n)}\equiv 1(\mod n)$