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

初等数论第一章整除


第一章

整 除

§1 整除与带余除法
1.1定义:a, b是两个整数,b不为零,若存 在一个整数q,使得等式a=b q成立,就称b 整除a, 或a能被b整除,记作b∣a,此时b称 为a的因子,a 称为b 的倍数。
a?0

否则的话,就称b 不整除a,记成b?a. 显然对任意的 a有1|a , a|0 ( a ? 0 )

第一章

整 除

§1 整除与带余除法
1.1定义:a, b是两个整数,b不为零,若存 在一个整数q,使得等式a=b q成立,就称b 整除a, 或a能被b整除,记作b∣a,此时b称 为a的因子,a 称为b 的倍数。
a?0

否则的话,就称b 不整除a,记成b?a. 显然对任意的 a有1|a , a|0 ( a ? 0 )

1. 2 性质 1、b|a ? ± b | ±a ? |b| | |a|
2、c|b,b|a? c|a.

? bc|ac (c≠0 ) 3、b|a,
? c|ma+nb 4、c|a,c|b, ? b|ac 5、 b|a,
6、 b|a (a ≠0 ) ?|b| ?|a|
7、 b|a (a ≠0 ) ? | a
a b

例1:设 x, y 为整数,且5 | x ? 9 y 则 5 | 8x ? 7 y
证:因为 8x ? 7 y
? 8( x ? 9 y) ? 65y
因为5 | x ? 9 y
所以有



5 | 65y

5 | 8x ? 7 y

例2:证明若3|n,7|n,则21|n
证:因为3|n,所以n= 3n1 又因为7|n,所以 7 | 3n1 显然有 7 | 7n 1 则有 7 | 7n1 ? 2 ? 3n1 即 7 | n1 有 n1 ? 7n2 即有 n ? 21n2 所以有21|n
3n1

例3:证明若A=3237n-632n-855n+235n

则有(1)5|A, (2)397|A
证: (1) A=(3237n-632n)-(855n-235n)

=(3237-632)×u-(855-235)×v
=5(521×u-124×v) (u,v∈Z) ∴5|A

(2)A=(3237n-855n)-(632n-235n)
=(3237-855)×s-(632-235)×t =397(6×s-t) ∴ 397|A (s,t∈Z)

例4:证明2003|(20022002+20042004-2005)

证:20022002=(2003-1)2002 =2003M1+1
20042004=(2003+1)2002=2003M2+1 ∴20022002+20042004-2005 =2003(M1+M2-1) 由定义有 2003|(20022002+20042004-2005)

n 注:1、
2、

a ? b ? (a ? b)M1
n
n

a ? b ? (a ? b)M 2 , 2?n
n

3、

(a ? b) ? aM3 ? b ,
n n

例5、试证明任意一个整数与它的各位数 字和的差必能被9整除。

证:设整数a= an10n ? an?110n?1 ? ?a110 ? a0100

a ? ? ai ?an (10n ? 1) ? an?1 (10n?1 ? 1) ? ?a1 (10 ? 1)
i ?0 n

=

9an M1 ? 9an?1M 2 ? ?9a1

= 9(an M1 ? an?1M 2 ? ?a1 ) 注:整数的十进制表示

=

9M

所以任一整数与其数字之和的差能被9整除 a= an10 ? an?110
n n?1

? ?a110 ? a010

0

例6: 证明对于任意整数n, 整数. 证明: 因为 =
n ( n ?1)( n ? 2) 6 n ( n ?1)( n ? 2) 6
n 3

n 3
n 6

?

n2 2

?

n3 6



?

n2 2

?

n3 6

2 ( n ? 3n ? 2) =

分子是三个连续整数的乘积, 是3!的倍数, 即 整数.
n 是整数,所以 3

?

n2 2

?

n3 6



注:这里用了连续n个整数的乘积是n!的 倍数的结论.

注:连续n个整数的乘积是n!的倍数。 a、当n个整数都大于零时,由
m( m?1)?( m? n?1) n!

?C

n m? n?1

而组合数为整数,可知连续n个整数的乘积是n! 的倍数。 b、当n个整数中有一个为零时,显然成立。

c、当n个整数都小于零时,因为整除与符号无 关,所以 连续n个整数的乘积是n!的倍数。

带余除法
两整数之间的整除关系是特殊的,不整 除是普遍的,一般的有下面的定理 2.1带余除法定理:设a是整数,b是非零整 数,则存在两个惟一的整数q,r,使得 a=bq+r,其中 0 ? r ?| b |

注:其中q称为a被b除的不完全商,r称为a 被b除所得的余数。r=0时,即为整除的情形。

证:存在性:考虑b>0,先证明存在性。作数列 …,-3b,-2b,-b,0,b,2b,3b,…,则一定存在整数q使
qb ? a ? (q ? 1)b令r=a-bq,有a=bq+r且 0 ? r ? b

惟一性:设另有 q1 , r1 满足 a ? bq1 ? r1 ,则有 b | q1 ? q |?| r1 ? r |(*),若 q1 ? q 则(*)式左 边 大于b,而右边显然小于b,矛盾。所以有 q1 ? q, r1 ? r 这样就证明了惟一性。 问题:当b<0时,如何证?

2. 2带余除法定理作用
(1)带余除法可以将全体整数进行分类,从而 可将无限的问题转化为有限的问题。这是一种 很重要的思想方法. 例如取b=2,任意整数a可写成2q,或2q+1的形 式,即把整数分成奇数和偶数 取b=3则整数可分成3k ,3k+1,3k+2( 3k-1)三种 类型. (2)在不同整数a和b之间建立了a=bq+r联系. (3)为将要学习的同余理论建立了基础.

例1:证明连续三个整数中必有一个数被3整 除。
证:设这三个连续整数为a,a+1,a+2。又由 带余除法可设a=3k,3k+1,3k+2三种情形. (1) 当a=3k时,由定义3|a。

(2) 当a=3k+1时,此时a+2=3(k+1),故3|a+2.
(3) 当a=3k+2时,此时a+1=3(k+1), 故3|a+1. 所以不论何种情况都有连续三个整数中必有 一个数是3倍数.

注: (1)连续n个整数中必有一个数被n整除。 可作为一个定理,在证明整除问题时非常 有用。 (2)注意整数的各种表示。 例2: 证明若a不是5的倍数,则



中有且仅有一个数被5整除

证明: 这四个数有一个是5的倍数 若 5 | a ? 1或 又 所以 即 a ? 1, a ? 1 有且仅有一个数被5整除
2 2

5 | a ?1



5 | a ?1
2

2 5 | a ? 2 若 5| a ?2 或 则 5 | a ?1

例2:任意给出的五个整数,必有三个整数的和被3整除

证:设五个整数为ai , i ? 1,2,3,4,5又设
ai ? 3qi ? ri ,0 ? ri ? 3

下面分两种情况讨论

(1)设五个余数中0,1,2都出现不妨设
有 r1 ? 0, r2 ? 1, r2 ? 2 a1 ? a2 ? a3 ? 3(q1 ? q2 ? q3 ) ? 3

即 a1 ? a2 ? a3 被3整除。
(2)设五个余数中0,1,2至少有一个不出 现,这样由抽屉原理,至少有三个数的余数 相同,不妨设 r1 ? r2 ? r3 ? r 从而
a1 ? a2 ? a3 ? 3(q1 ? q2 ? q3 ) ? 3r即 3| a1 ? a2 ? a3

例3:任意给出的n个整数,必有若干个整 数的和被n整除。 证:设这n个整数为 ai , i ? 1,2,? , ,n 作 s1 ? a1 , s2 ? a1 ? a2 ,
sn ? a1 ? a2 ? ?? an

??

0 ? ri ? n

由带余除法有 si ? nqi ? ri , (i ? 1,2,?, n)

(1)若有余数为零,不妨设为 ri ? 0
则有 n | si ,从而证明了结论.

(2)否则由抽屉原理,至少有两个余数相等, 不妨设

则有

ri ? rj (i ? j )

n | s j ? si

即和 ai ?1 ? ai ?2 ? ?? a j 能被n整除. 注:抽屉原理在一些证明中是非常有用的.

例4:对任意的整数 x ,有 3 | x( x ? 1)(2 x ? 1) 证:由带余除法x 必为下列三种形式之一:
当 x ? 3k 时,有

3 | x,

当 x ? 3k ? 1时,有 2 x ? 1 ? 6k ? 3 ,所以 3 | 2 x ? 1

当 x ? 3k ? 2 时,有 x ? 1 ? 3k ? 3 ,所以 3 | x ? 1
综上所述都有 3 | x( x ? 1)(2 x ? 1) 注:利用余数进行分类讨论的方法,当除 数较小时是非常有用的.



推荐相关:

初等数论

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


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

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


初等数论中的整除问题

初等数论中的整除问题_数学_自然科学_专业资料。初等数论中的整除问题 摘要:整除...初等数论(1)数的整除 654人阅读 5页 2下载券 初等数论 第一章 整除理.....


初等数论1——整除性

初等数论1——整除性_数学_自然科学_专业资料。第四讲 初等数论 1——整除性本讲概述数论是数学中极其重要又非常迷人的一个分支,目前我们仅学习初等数论中较浅的...


初等数论 第一章 整数的可除性

初等数论 第一章 整数的可除性 - 第一章 整数的可除性 第一章 整数的可除性 §1 整除 整数集对于加、减、乘三种运算都是封闭的,但是对于除法运算不封闭。...


初等数论教案

初等数论教案 - 第一章 整除理论 整除性理论是初等数论的基础。本章要介绍带余数除法, 辗转相除法,最大公约数,最小公倍数,算术基本定理以及它们 的一些应用。 ...


初等数论中的整除问题

初等数论中的整除问题 - 龙源期刊网 http://www.qikan.com.cn 初等数论中的整除问题 作者:李子萍 来源:《科技资讯》2014 年第 01 期 摘要:整除初等数论中....


初等数论(1)整除

初等数论(1)整除_理学_高等教育_教育专区。初等数论(1)---数的整除初等数论...(1)一个整数能被 2 或 5 整除的特征是:这个数的末位数字能被 2 或 5 ...


[第11讲] 初等数论(1)整除(中)

[第11讲] 初等数论(1)整除(中)_数学_自然科学_专业资料。4 整除 本讲中所...初等数论 第一章 整除理... 61页 1下载券 初等数论(1)数的整除 5页 2...


初等数论期末复习资料

初等数论期末复习资料 - 数论教案 §1 整数的整除 带余除法 1 整数的整除 设 a,b 是整数,且 b≠0,如果有整数 q,使得 a=bq,则称 b 整除 a,记为 b|...

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