高等代数理论基础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)$

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,590评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 86,808评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 151,151评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,779评论 1赞 277
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,773评论 5赞 367
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,656评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,022评论 3赞 398
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,678评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 41,038评论 1赞 299
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,659评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,756评论 1赞 330
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,411评论 4赞 321
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,005评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,973评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,203评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,053评论 2赞 350
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,495评论 2赞 343