Mengzelev's Blog

问题求解学习笔记-数论基础

Word count: 790 / Reading time: 3 min
2019/03/30 Share

数学归纳法

你都懂的

辗转相除法(Division Algorithm)

定理2.9(辗转相除法): $a,b$为整数,满足$b>0$,则存在唯一的整数$q$和$r$使得$a=bq+r$,此处$0\le r<b$

$a\mid b$: $a$能整除$b$,$b$能被$a$整除

定理2.10: $a,b$为非零整数,则存在整数$r,s$使得gcd($a,b)=ar+bs$. $gcd(a,b)$是唯一的。但$r,s$不唯一

推论2.11: $a,b$为互质的整数,则存在整数$r,s$使得$ar+bs=1$【事实上是当且仅当的关系】

欧几里得算法(The Euclidean Algorithm)

使用多次除法得到一个递减的序列来求出gcd$(a,b)$
$b=aq_1+r$
$a=r_1q_2+r_2$
$r_1=r_2q_3+r_3$
$\vdots$
$r_{n-2}=r_{n-1}a_n+r_n$
$r_{n-1}=r_nq_{n+1}$
将这一系列等式反过来书写可以得到$d$的表示(略)

质数

引理2.13(Euclid): $a,b$为整数,$p$为质数。如果$p\mid ab$,则$p\mid a$或$p\mid b$

定理2.14(Euclid): 质数的个数是无限的

定理2.15(算术基本定理Fundamental Theorem of Arithmetic): $n$为大于1的整数,则$n=p_1p_2\cdots p_k$,其中$p_1,…,p_k$为质数。这个分解是唯一的,即若$n=q_1q_2\cdots q_l$,则$k=l$且$q_i$只是$p_i$的排列

以下内容出自CZ

$\mathbb{Z}_n$上的乘法逆元

乘法逆元(multiplicative inverse): $a’\cdot_{n}a=1$,则称$a’$是$a$在$\mathbb{Z}_n
$中的乘法逆元

引理2.5: 设$a$在$\mathbb{Z}_n$中存在乘法逆元$a’$. 则对于任意$b\in\mathbb{Z}n$,等式$a\cdot{n}x=b$有唯一解$x=a’\cdot_{n}b$.

推论2.6: 若存在$b\in\mathbb{Z}n$使得$a\cdot{n}x=b$的$a$无解,则$a$在$\mathbb{Z}_n$上不存在乘法逆元

定理2.7: 若$\mathbb{Z}_n$中的元素有一个乘法逆元,则它的乘法逆元是唯一的。
因此可以用$a^{-1}$来表示乘法逆元。

引理2.8: $a\cdot_{n}x=1$有解当且仅当存在整数$x,y$使得$ax+ny=1$

定理2.9: $a$在$\mathbb{Z}_n$中有乘法逆元当且仅当存在整数$x,y$使得$ax+ny=1$

推论2.10: 若$a\in\mathbb{Z}_n$且$x,y$是满足$ax+ny=1$的整数,则$a$在$\mathbb{Z}_n$中的乘法逆元是$x\bmod n$

引理2.11: 若存在整数$x,y$使得$ax+ny=1$,则$a,n$互质

定理2.12(欧几里得除法定理): 同最TJ的定理2.9

引理2.13: 若$j,k,q,r$是满足$k=jq+r$的正整数,则gcd($j,k$)=gcd($r,j$)

欧几里得扩展算法

其实就是计算$x$和$y$的算法

定理2.15: 两个正整数$j$和$k$互质当且仅当存在整数$x,y$使得$jx+ky=1$

推论2.16: 对于任意正整数$n$A,$\mathbb{Z}_n$的元素$a$有乘法逆元当且仅当$gcd(a,n)=1$

推论2.17: 对任意质数$p$,$\mathbb{Z}_p$的任意非零元素存在乘法逆元。

计算乘法逆元

跑欧几里得算法求出满足$ax+ny=1$的$x$,就是$a$在$\mathbb{Z}_n$中的乘法逆元

CATALOG
  1. 1. 数学归纳法
  2. 2. 辗转相除法(Division Algorithm)
    1. 2.1. 欧几里得算法(The Euclidean Algorithm)
    2. 2.2. 质数
    3. 2.3. $\mathbb{Z}_n$上的乘法逆元
    4. 2.4. 欧几里得扩展算法
    5. 2.5. 计算乘法逆元