高等代数理论基础1：整数的可除性理论

整数的可除性理论

商和余数

Z中不能作除法,但有以下除法算式：

\forall a,b\in Z,b\neq 0,\exists q,r\in Z,使a=q\cdot b+r,(0\le r\lt |b|)

$其中q,r唯一,q称为b除a的商,r称为b除a的余数

因子和倍数

定义：\forall a,b\in Z,\exists c\in Z,使a=bc,则称b是a的因子,a是b的倍数

注：任何整数都是0的因子，但0不是任何非零整数的因子

b\neq 0时,b是a的因子\Leftrightarrow b除a余数为0\Leftrightarrow b|a

整除的性质

1.a|b,b|a\Rightarrow a=\pm b

2.a|b,b|c\Rightarrow a|c

3.a|b,a|c\Rightarrow \forall k,l\in Z,有a|(kb+lc)

4.a|b\Rightarrow (-a)|b,a|(-b)(所以,只讨论非负整数)

最大公因子

定义：设d为a和b的一个公因子,若a,b的任一因子都是d的因子,则称d是a,b的一个最大公因子

性质：

1.d_1,d_2都是a,b的最大公因子\Rightarrow d_1|d_2,d_2|d_1

\Rightarrow d_1=\pm d_2\Rightarrow d_1=d_2(d_1,d_2皆非负)

2.b|a时，b是a与b的最大公因子(a=0时,b是a,b的一个最大公因子)

3.a,b不全为零时a,b的最大公因子不为零,以(a,b)表示a,b的正的最大公因子,(a,b)唯一

辗转相除法求(a,b)

设b\neq 0,即b\gt 0

a=q_1b+r_1,\qquad 0\lt r_1\lt b,

b=q_2r_1+r_2,\qquad 0\lt r_2\lt r_1,

\cdots

r_{k-2}=q_kr_{k-1}+r_k,\qquad 0\lt r_k\lt r_{k-1},

r_{k-1}=q_{k+1}r_k+0

则(a,b)=(b,r_1)=(r_1,r_2)=\cdots=(r_{k-1},r_k)=r_k

性质：\exists u,v\in Z,使(a,b)=ua+vb

互素(互质)

定义：若(a,b)=1,则称a,b互素(互质)

性质：

1.(a,b)=1\Leftrightarrow \exists u,v\in Z,使ua+vb=1

2.(a,b)=1,a|bc\Rightarrow a|c

2.(a,c)=1,(b,c)=1\Rightarrow (ab,c)=1

素数(质数)

定义：a是一个大于1的整数,若除去1和本身外没有其他因子，则称a为一个素数

注：一个整数a(a＞1)至少有两个因子1和a,不等于1和a的因子叫a的真因子

性质：

1.素数p和任一整数a,或p|a,或(p,a)=1

2.素数p|a\cdot b\Rightarrow p|a或p|b

3.整数p\gt 1,\forall a\in Z,有p|a或(p,a)=1\Rightarrow p是一个素数

4.整数p\gt 1,\forall a,b\in Z,由p|ab可推出p|a或p|b\Rightarrow p是一个素数

注：若素数p是整数a的一个因子，则称p为a的一个素因子

因子分解及唯一性定理

任一大于1的整数a可分解为有限多个素因子的乘积：a=p_1p_2\cdots p_s,而且分解法是唯一的

即若有两种分解法

a=p_1p_2\cdots p_s,\quad a=q_1q_2\cdots q_t

其中p_1,\cdots,p_s;q_1,\cdots,q_t都是素数

则s=t,且重新将q_1,\cdots,q_t适当排列后可得

p_i=q_i,\quad i=1,2,\cdots,s

a的标准分解式

a的分解式中将同一个素因子合并写成方幂,且将素因子按大小排列得

a=p_1^{l_1}p_2^{l_2}\cdots p_r^{l_r},\quad p_1\lt p_2\lt\cdots\lt p_r,l_i\gt 0,i=1,\cdots,r

利用整数的分解式判断整除性及求最大公因子

将整数a,b的素因子合在一起,设为p_1,p_2,\cdots p_t
\begin{cases}a=p_1^{l_1}p_2^{l_2}\cdots p_t^{l_t},\qquad l_i\ge 0,i=1,2,\cdots,t\\\\ b=p_1^{d_1}p_2^{d_2}\cdots p_t^{d_t},\qquad d_i\ge 0,i=1,2,\cdots,t \end{cases}

a|b\Leftrightarrow l_i\le d_i,i=1,2,\cdots,t

(a,b)=p_1^{min(l_1,d_1)}p_2^{min(l_2,d_2)}\cdots p_t^{min(l_t,d_t)}

最小公倍数

定义：设a,b\in N,m是a,b的一个公倍数,若a,b的任一公倍数都是m的倍数,则称m为a,b的一个最小公倍数

注：a,b的最小公倍数唯一，记作[a,b]

利用整数的分解式求最小公倍数

对正整数a,b,

\begin{cases}a=p_1^{l_1}p_2^{l_2}\cdots p_t^{l_t},\qquad l_i\ge 0,i=1,2,\cdots,t\\\\ b=p_1^{d_1}p_2^{d_2}\cdots p_t^{d_t},\qquad d_i\ge 0,i=1,2,\cdots,t \end{cases}

[a,b]=p_1^{max(l_1,d_1)}p_2^{max(l_2,d_2)}\cdots p_t^{max(l_t,d_t)}

注：a\cdot b=(a,b)[a,b]

推广

可以将最大公因子及最小公倍数推广到有限多个整数a_1,a_2,\cdots,a_s

类似规定(a_1,a_2,\cdots,a_s)和[a_1,a_2,\cdots,a_s]

特别地,当a_1,a_2,\cdots,a_s全为正整数时

(a_1,a_2,\cdots,a_s)=(a_1,a_2,\cdots,a_{s-1}),a_s)

[a_1,a_2,\cdots,a_s]=[a_1,a_2,\cdots,a_{s-1}],a_s]

\exists u_1,u_2,\cdots,u_s\in Z,使得

u_1a_1+u_2a_2+\cdots+u_sa_s=(a_1,a_2,\cdots,a_s)

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 数论基础
    基本运算 取模(mod)取余(rem) 定义 给定一个正整数p，任意一个整数n，一定存在等式 ： n = kp +...
    passwd_阅读 1,687评论 0赞 3
  • 2018-06-14
    在C语言中,五种基本数据类型存储空间长度的排列顺序是: A)char B)char=int<=float C)ch...
    夏天再来阅读 3,392评论 0赞 2
  • 行测大礼包—（数字推理题725道详解）
    【1】7，9，-1，5，( ) A、4；B、2；C、-1；D、-3 分析:选D，7+9=16；9+（-1）=8；（...
    Alex_bingo阅读 19,096评论 1赞 19
  • RSA加密解密算法—数论基础
    本章涉及知识点1、素数的定义2、寻找素数算法—短除法3、寻找素数算法—筛选法4、互质关系5、欧拉函数的证明6、欧拉...
    PrivateEye_zzy阅读 4,592评论 0赞 6
  • 50道java初级编程题
    【程序1】 题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔...
    叶总韩阅读 5,162评论 0赞 41