同余问题

2019-03-03 14:08:08


同余概述

1.基本定义及定理

定义1:给定正整数 $m$ ,若 $m%a==m%b$ ,则记做 $a\equiv b (mod\quad m)$ 。

定义2:整数集合 $Z$ 被分为 $m$ 个不同的集合,这些集合被称为模 $m$ 的剩余类(同余类)。每个同余类的任意两个整数都是模 $m$ 同余的。

定理1: $a\equiv b(mod \quad m)$ ,当且仅当 $m|(a-b)$ 。

定理2: $a\equiv b(mod \quad m)$ 。当且仅当存在整数 $k$ ,满足 $a=b+km$ 。

费马小定理:若 $p$ 为质数,则对于任意整数 $a$ ,满足 $a^p \equiv a(mod \quad p)$ 。

欧拉函数:即: $\phi(n)$ ,表示小于 $n$ 的正整数中与 $n$ 互质的数的个数。一般的, $\phi(n)=x\times \prod_{i=1}^{k}{1-\frac{1}{p_i}}$ ,其中 $p_i$ 为 $n$ 的质因数, $k$ 为 $n$ 的质因数的个数。特殊的, $\phi(1)=1$ 。

欧拉定理:若正整数 $a,n$ 互质,则 $a^{\phi(n)}\equiv 1 (mod \quad n)$ 。

欧拉定理推论:

若正整数 $a,n$ 互质,则对于任意正整数 $b$ ,有 $a^b\equiv a^{b\quad mod\quad \phi(n)}(mod \quad n)$

证明:

设 $b=q\times \phi(n)+r$ ,其中 $0 \leq r \leq \phi(n)$ ,即: $r=b\quad mod \quad \phi(n)$ 。

于是: $a^b\equiv a^{q\times \phi(n)+r}\equiv (a^{\phi(n)})^q \times a^r \equiv 1^q \times a^r \equiv a^r \equiv a^{b \quad mod \quad \phi(n)} (mod \quad n)$ 。

证毕。

2.同余的性质

同余不满足同除性,即不满足 $a/n \equiv b/n (mod \quad m)$ 。