1 整除性和带余除法
1.1 整除
设 $a$,$b$ 均为正数, 若存在整数 $m$ 使得 $a=m\times b$ 成立, 则成为非零数 $b$ 整除 $a$, 换而言之, 若 $b$ 除 $a$ 没有余数, 则认为 $b$ 整除 $a$. 表示为 $b|a$, 同时也称为:$b$ 是 $a$ 的一个引子.
(注意, 小的能够整数大的. 在用 $|$ 表示的时候, 小数在前, 大数在后.$m$ 可正负数都可以, 但是不能为 0)
因此有如下性质:
若 $a|1$, 则 $a=\pm 1$
若 $a|b$ 且 $b|a$, 则 $a=\pm b$
若 $a|b$ 且 $b|c$, 则 $a|c$, 例如 $2|4$,$4|8$, 那么 $2|8$
对于任意整数 $m$,$n$, 若 $b|g$ 且 $b|h$, 那么 $b|(m/times g+ n/times h)$, 例如 $3|6$,$3|9$, 那么 $3|(6n+9m)
若 $b|g$, 那么就存在 $g_1$, 使得 $g$ 可以表示为 $g=b\times g_1$
1. 2 带余数除法
对于给定的任意一个正整数 $n$ 和任意非负整数 $a$, 若用 $n$ 除 $a$, 得到整数商 $q$ 和整数余数 $r$, 则满足:
$a=q\times n +r$, $0 \le r \le n $ 且 $q=\lfloor a|n \rfloor $
其中 $\lfloor a|n \rfloor$ 表示向下取整, 例如,$\lfloor 1.9 \rfloor = 1$.
称为带余除法.
2 最大公因子
欧几里得算法是数论中一个最基本的技巧, 用于求两个正整数的最大公因子.
互素: 如果两个整数只有一个整数的公因子 $1$, 称为互素
2.1 最大公因子
最大公因子必须是正数.
当 $a=m\times b$ 时, 称 $b$ 是 $a$ 的一个因子.
使用 $d=gcd(a,c)$, 称 $d$ 为 $a$ 和 $b$ 的最大公因子.
定义 $gcd(0,0)=0$,$gcd(a,0)=|a|$
如果 $c$ 是 $a$ 和 $b$ 的最大公因子, 那么 $a$,$b$ 的所有因子都是 $c$ 的一个因子.
例如 $gcd(30,24)=6$, 而 $2$,$3$ 都是 $24$ 和 $30$ 的因子, 并且也是 $6$ 的因子.
因为要求最大公因子必须是正数, 因此一般来说都是 $gcd(|a|,|b|)$
2.1 欧几里得算法
欧几里得算法的步骤是:
假设求 $a$,$b$ 的最大公因子 $d$, 并且假设 $0 \le b\le a$
使用带余除法,$b$ 除 $a$ 可以表示为:$a=b q_1 \times b + r_1$,$0 \le r_1 <b$
当 $r_1 =0$ 时, 可知 $b$ 整除 $a$, 且 $a$ 中不存在比 $b$ 大的因子了. 就比如 $gcd(18,6)$,18 \div 6 =3 $
当 $r_1 \neq 0 $ , 那么一定有 $b|r_1$, 因为:$d|a$ 且 $d|b$, 那么一定有 $d|(a-q_1 \times b)$ . 因此 $gcd(a,b)=gcd(b,r_1 )$.
3 模运算 $mod$
如果 $a$ 说是一个整数,$n$ 是一个正整数, 那么我们定义 $a \div n$ 的余数为 $a$ 模 $n$. 整数 $n$ 称为模数.
$a=q\times n+ r$ ,$0 \leqr<n; q=\lfloor a \div n \rfloor$ 等价于 $a=\lfloor a \div n \rfloor \times n + (a mod n)$
3.1 同余性质
如果 $(a mod n = (b mod n))$, 则称整数 $a$,$b$ 是模 $n$ 同余的. 可以表示为 $a \equiv b(mod n)$, 其含义还有:$a(mod b) = a\times (a mod b)$. 其意思就是 $a$ 和 $b$ 对 $n$ 取模的结果相同
若 $n|(a-b)$, 则 $a \equiv b(mod n)$. 因此等价于:$a \equiv b \times (b mod n)$
若 $a\equiv b(mod n)$, 则有 $b \equiv a(mod n)$ . 对称?
若 $a\equiv b(mod n)$,$b \equiv c(mod n)$, 则有 $a \equiv c(mod n)$
3.2 模运算
运算符 $mod$ 将所有的整数映射到集合 ${0,1,2\ldots n-1}$.
模运算具有如下的性质:
- $[(a mod n)+(b mod \n)] mod n=(a+b) mod n$
- $[(a mod n)-(b mod \n)] mod n=(a-b) mod n$
- $[(a mod n)\times (b mod \n)] mod n=(a\timesb) mod n$
也就是说除了除法以外都满足结合律. 但是注意, 不是简单的结合律!
加法逆元: 就是相反数
乘法逆元: 乘法逆元, 是指数学领域群 $G$ 中任意一个元素 $a$, 都在 $G$ 中有唯一的逆元 $a'$, 具有性质 $a×a'=a'×a=e$, 其中 $e$ 为该群的单位元.
例如:$4 \times X \equiv 1 mod 7$ 就是 $4 \times X = 7\times k +1$
另外有如下的性质:
满足加法和乘法交换律: $(w+x) mod n = (x+w) mod n$, 乘法也满足
满足加法和乘法的结合律:$(x\times y\times z) mod \n n=(x\times (y\times x)) mod n$
满足分配律:$(x\times (y+z)) mod n = (x\times y+x\times z) mod n$
单位元: 加 $0$ 或乘 $1$ 不改变结果
剩余类, 使用 $[m]$ 表示一个集合, 意思是该集合内所有的数 (包含正负数), 对 $n$ 取模的结果相同.
4 素数
或是质数
数论的核心是素数: 当一个整数 $p>1$, 他的因子只有 $\pm 1$ 和 $\pm p$ 时, 成这个数为素数.
任意一个数都可以分解为:$a=p_1^{a_1}+p_2^{a_2}+p_3^{a_3}+\dots +p_m^{a_m}$. 也就是多个素数的成绩形式.
从这个角度来解释整除, 其所含有的素数相同 (次数可能不同)
从这个角度来解释最大公因子, 则是两个数都含有的最大的那个素数.
5 费马定理和欧拉函数
5.1 费马定理
若 $p$ 是素数,$a$ 是整数, 且不能被 $p$ 整除 (a 中不含素数 $p$), 那么:
$a^{p-1} \equiv 1( mod p)$
就是说, 对 $p$ 取模, 结果是 1.
而更一般的形式是:
$a^{p} \equiv a( mod p)$
5.2 欧拉函数
欧拉函数:$\phi(n)$ 只的是小于 $n$ 且与 $n$ 互素的正整数的个数. 其中 $\phi(1)=1$
因此, 如果 $p$ 是素数, 那么 $\phi(p)=p-1$: 因为, 素数与任何数都互素, 而小于 $p$ 的有 $p-1$ 个
且, 满足 $\phi(p_1 \times p_1) = (p_1 -1)\times (p_2 -1)$.
对于任意两个互素的 $p_1$ 和 $p_2$, 有:$p_1^{\phi(p_2)} \equiv 1( mod p_1)$, 其实是费马定理的特别形式, 也就是说底数也是一个素数.
因此也可以表示为:$p_1^{\phi(p_2)+1} \equiv p_1 ( mod p_2)$
6 素数测试
很多密码算法需要随机选取一个或是多个非常大的叔叔, 因此需要一个能确定给定的大数是否是素数的方法.
跳过.
7 中国剩余定理
问题: 找出所有的整数 $x$, 它们被 $3$,$5$,$7$ 整除时余数分别为 $2$,$3$,$2$, 那所有解的形式为 $23+105\times k$
// 定义: 令 $a=p_1 \times p_2 \times \dots \times \p_n$, 其中因子 $p_i$ 两两互素
中国余数定理的用途之一是: 给出了是模 $M$ 的大数运算转化为相对较小数的运算.
来源: http://www.bubuko.com/infodetail-2582453.html