tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> 理学 >>

初等数论 第一章 整除5-7


§5 算术基本定理
整数分解唯一性定理也称算术基本定理, 在给

出并证明该定理前, 先介绍预备定理.

定理 若p为素数, 则a不能被p整除当且仅当: (p,a)=1

2015-4-28

11:26

定理1
设a1,a2,…,an都是正整数,且p是素数. 若p|a1a2…an, 则至少有一个ar, 使得p|ar, 其中1≤r≤n. 证明 假设 ai不能被p整除, 1≤i≤n. 从p是一素数

和定理得到(p,a1)=(p,a2)=…=(p,an)=1. 所以由定
理5推论得到(p,a1a2…an)=1, 这与题设p|a1a2…an

矛盾, 故必有一ar, 使得p|ar, 其中1≤r≤n.

2015-4-28

11:26

推论
设p1,p2,…,pn和p都是素数, n≥2. 若p|p1p2…pn,

则至少有一个pr, 使得p=pr.
证明 由p| p1p2…pn和定理1知, 至少存在一个pr, 使得p|pr. 由于pr是素数, 故它只有二个正因数1 和pr. 由p≠1和p| pr, 所以: p= pr.

2015-4-28

11:26

定理2 (整数分解唯一性定理)
每个大于1的正整数a均可分解成有限个素数 之积, 并且若不计素因数的次序, 其分解是唯 一的. 证明 先证分解式的存在性. 唯一性. 当a=2时, 分解式显然是唯一的. 现设 比a小的正整数其分解式均是唯一的. 考虑正 整数 a, 假设 a有两个分解式 a=plp2…pk和 a=q1q2…ql, 其中pl,p2,…,pk和q1,q2,…,ql都是素 数.
2015-4-28 11:26

于是p1| q1q2…ql , 根据定理1知必有一qi, , 使得 p1|qi,不妨令i=1, 即p1|q1, 显然p1=q1. 令a’=a/p1, 则a’=p2p3…pk, a’=q2q2…ql. 若a’=1, 则a= p1=q1, 即a’的分解式唯一. 若a’>1, 注意到a’<a, 从而 由归纳假设知, a’的分解式是唯一的. 因此k=l,

并且 p1=q1,…,pk=qk, 再由p1=ql, 知a分解式也是
唯一的.
2015-4-28 11:26

若将a的分解式中相同素因数合并为它的幂 数, 则任意大于1的整数a只能分解成一种形 式:

a ? p1 p2 ... ps

?1

?2

?s

(2)

p1 < p2 < … < ps
n≥1, 其中p1,p2,…,ps是互不相同的素数, ? ,1

,…,? s 是正整数. 并称其是 a的标准分解式.
2015-4-28 11:26

推论3
使用式(2)中的记号,有 (ⅰ) d 是a的正因数的充要条件是 d=

p p

e1 1

e2 2

p

es s

(3)

ei?Z,0 ≤ ei ≤ ?i,1 ≤ i ≤ s; (ⅱ) n的正倍数m必有形式

m=

p1 p2

?1

?2

ps

?s

M,M?N,?i?N,

?i ? ?i,1 ≤ i ≤ s。
2015-4-28 11:26

推论 设正整数a与b的标准分解式是 ?k ?1 ?l ?1 a ? p1 pk q1 ql
其中pi (1 ≤ i ≤ k),qi (1 ≤ i ≤ l)与ri (1 ≤ i ≤ s)
是两两不相同的素数, ?i , ?i (1 ≤ i ≤ k),

b ? p1

?1

pk r1

?k ?1

rs

?s

?i(1 ≤ i ≤ l)与?i(1 ≤ i ≤ s)都是非负整数,则
?k ? = min{? , ? }, 1 ≤ i ≤ k, , p1 ? pk i i i ?s [a, b] = p ?1 ? p ?k q ?1 ?q ?l r ? 1 , 1 1 k l 1 ?rs ?i = max{?i, ?i},1 ≤ i ≤ k。

(a , b) =

?1

2015-4-28

11:26

推论4
设正整数a与b的分解式是

a ? p1 p2

?1

?2

ps ,b ? p1 p2

?s

?1

?1

ps

?s

其中p1, p2, ?, ps 是互不相同的素数,?i,?i

(1 ≤ i ≤ k)都是非负整数,则

(a, b) ? p1 p2 [a, b] ? p1 p2
?1

?1

?1

ps , ?i ? min{? i , ?i }, 1 ? i ? s,
?s

?s

?1

ps , ?i ? max{? i , ?i }, 1 ? i ? s。

2015-4-28

11:26

推论5
设a,b,c,k是正整数,ab = ck ,(a, b) = 1,则存在正整数 u,v,使得a = uk,b = vk,c = uv,(u, v) = 1。
?s ?1 ?2 c ? p p ... p 证明 设 1 2 s ,其中p1, p2, ?, ps 是互不相同的素

数, ?i (1 ≤ i ≤ s)是正整数。又设
?1 ? 2 b ? p1 p2

?s ?1 ps ,a ? p1?1 p2

ps?s

其中?i ,?i(1 ≤ i ≤ s)都是非负整数。显然 min{?i , ?i} = 0, ?i ? ?i = k ?i ,1 ≤ i ≤ s,

因此,对于每个i(1 ≤ i ≤ s),等式

?i = k?i ,?i = 0与?i = 0,?i = k?i有且只有一个成立。
这就证明了推论。证毕。
2015-4-28 11:26

推论6
设a是正整数, ? (a)表示a的所有正因数的个数.若a有 标准素因数分解式(2),则

? (a) ? (?1 ?1) (?s ?1) ? ? ( p1 )...? ( ps )
推论7 设a是正整数, ? (a)表示a的所有正因数的之和.
若a有标准素因数分解式(2),则
?1 ?1 p1 ?1 ? (a) ? p1 ? 1 ? s ?1 p1 ? 1 s p1 j ? 1 ?? ps ? 1 p j ?1 j ?1 ? ?1

?1

?s

? ? ( p1 )...? ( ps )
2015-4-28 11:26

?1

?s

例1 证明:(a,[b,c])=[(a,b),(a,c)]

? (180) 例2 求? (180) ,
1 例3 求 ? d |a d

(d ? 0)

2015-4-28

11:26

§7 函数[x]与{x} , n!的分解式

2015-4-28

11:26

定义1 设x是实数,以[x]表示不超过x的最大整数, 称它为x的整数部分,即[x]是一个整数且满足 [x] ≤ x <[x]+1. 又称{x} = x ? [x]为x的小数部分。

2015-4-28

11:26

定理1 设x与y是实数,则
(ⅰ) x ≤ y ? [x] ≤ [y]; (ⅱ) 若x=m+v, m是整数, 0 ≤ v< 1, 则m= [x], v={x},

特别地,若0 ≤ x < 1,则[x] = 0,x ={x} ;
(ⅲ) 若m是整数,则[m ? x] = m ? [x];
? [ x] ? [ y ] ( ⅳ ) [ x ? y] = ? ?[ x] ? [ y ] ? 1
? ? [ x] (ⅴ) [?x] = ? ?? [ x] ? 1

若 {x} ? { y} ? 1 ; 若 {x} ? { y} ? 1

11:26

若 x?Z 若 x?Z
2015-4-28

? 0 {?x} = ? ?1 ? {x}

若 x?Z 若 x?Z
m m

.

(ⅵ)对正整数m有[[ x]] ? [ x ] (ⅶ)设a和N是正整数.那么,正整数 1, 2,
N 中被a整除的正整数的个数是 [ ] a

,N

2015-4-28

11:26

证明
能被a整除的正整数是a, 2a, 3a, ?,因此,若数 1, 2, ?, N中能被a整除的整数有k个,则 N ka ≤ N < (k ? 1)a ? k ≤ N/a < k ? 1 ? k = [ ] a 证毕。 由以上结论我们看到,若b是正整数,那么对于任意 的整数a,有 a ? b[ a ] ? b{a}

b

b

即在带余数除法 a = bq ? r,0 ≤ r < b a a 中有 q ? [ ] ,r ? b{ } b b
2015-4-28 11:26

定理2
设n是正整数,n! = p1 ? n [ ] 式,则 ?i = ? r r ?1 p
i

?1

p2 ? pk

?2

?k

是n!的标准分解

(1)

证明 对于任意固定的素数p,以p(k)表示在k的标准分
解式中的p的指数,则

p(n!) = p(1) ? p(2) ? ? ? p(n).
以nj表示p(1), p(2), ?, p(n)中指数等于j的个数,那么

p(n!) = 1?n1 ? 2?n2 ? 3?n3 ? ? ,
数a的个数,所以,由定理有
2015-4-28 11:26

(2)

| a的整 显然,nj就是在1, 2, ?, n中满足pj?a并且pj + 1 ?

nj = [

n p
j

]?[

n p
j ?1

]

将上式代入式(2),得到即式(1)成立。
n n n n n n p(n !) ? 1([ ] ?[ 2 ]) ? 2([ 2 ] ?[ 3 ]) ? 3([ 3 ] ?[ 4 ]) ? p p p p p p n ? ?[ r ]。 r ?1 p
?

2015-4-28

11:26

推论
设n是正整数,则
r ?1 p n! = ?

?[ pr ]

?

n



p?n

其中 ?表示对不超过n的所有素数p求积。
p?n

2015-4-28

11:26

例2 求20!的标准素因数分解式

例3 20!的十进位表示中有多少个零?

例4 设整数aj>0(1 ≤ j ≤ s),并且 n=a1+a2+…+as.证明:n!/a1!a2! …as!是整数.
2015-4-28 11:26

例5
设n是正整数,1 ≤ k ≤ n ? 1,则

Ck n

n! ? ?N k! ( n ? k )!
n

(3)

若n是素数,则n? C k ,1 ≤ k ≤ n ? 1. 证明 由定理2,对于任意的素数p,整数n!,k!与 (n ? k)!的标准分解式中所含的p的指数分别是
n?k ] 与 [ ? r ] r
? r ?1

?[
r ?1

?

n p

], ? [ r
r ?1
?

?

k p
n p

p

利用例4可知

?[
r ?1

r

] ? ?[
r ?1

?

k p
r

] ? ?[
r ?1

?

n?k p
r

]

2015-4-28

11:26

因此 C k 是整数。 n 若n是素数,则对于1 ≤ k ≤ n ? 1,有 (n, k!) = 1,(n, (n ? k)!) = 1 ? (n, k!(n ? k)!) = 1, n ? ( n ? 1)! 由此及 C k ?N, n ? k! ( n ? k )! 推出k!(n ? k)!?(n ? 1)!,从而n?C k .证毕.
n

2015-4-28

11:26



推荐相关:

初等数论中的整除问题

特征 6:若一个整数能被 2 和 3 整除,则这个数能被 6 整除。 特征 7:若...初等数论 第一章 整除5-... 265人阅读 23页 免费 喜欢此文档的还喜欢 初等...


初等数论

初等数论 - 第一章 整数的唯一分解定理 第一节 整除性 教学重点:应用带余数除法 定义 1 设 a,b 是整数,b ≠ 0,如果存在整数 c,使得 a = bc 成立,则...


初等数论

第一部分:整除 初接触初等数论,经过《初等数论》课本知整除理论是初等数论的基础...整除可约性 a∣bó ma∣mb(m≠0) 5) 整除与符号无关 a∣bó∣a∣∣∣...


初等数论中的整除问题

特征 6:若一个整数能被 2 和 3 整除,则这个数能被 6 整除。 特征 7:若...初等数论(1)数的整除 654人阅读 5页 2下载券 初等数论 第一章 整除理.....


初等数论

初等数论 - 初等数论学习总结 ? 第一章 整除 例题选讲 例 1.请写出 10 个连续正整数都是合数. 解: 11!+2,11!+3,……,11!+11。 例 2. 证明连续三...


(填空题50道)第一章 数的整除性

(填空题50道)第一章 数的整除性_理学_高等教育_教育专区。2011 年 2 月《初等数论第一章 第 1 页共 5 页 第一章二、填空题 数的整除性 5 1、 n ...


初等数论(1)整除

初等数论(1)整除_理学_高等教育_教育专区。初等数论(1)---数的整除初等数论...a 。补充:关于整除的一些小结论: 一个整数被 2,3,4,5,7,8,9,11,13 ...


(选择题24道)第一章 数的整除性

(选择题24道)第一章 数的整除性 - 2011 年 2 月《初等数论》题库第一章 第一章 一、选择题 1、下列各整数中,不能被 3 整除的是( A. 123456 答案:C...


初等数论期末复习资料

初等数论期末复习资料_工学_高等教育_教育专区。数论教案 §1 整数的整除 带余...删去 5 后面的被 5 整除的数(从 25 开始),5 后面剩下的第一个数 7 是...


17春秋华师《初等数论》在线作业

华师《初等数论》在线作业 一、单选题(共 20 道试题,共 60 分。 ) 1. ...7 不整除(12,15) D. 7 不整除[12,15] 正确答案: 11. 如果 3|n,5|n...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com