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) 注:利用余数进行分类讨论的方法,当除 数较小时是非常有用的.


推荐相关:

初等数论第一章整除_图文.ppt

初等数论第一章整除 - 第一章 整除 §1 整除与带余除法 1.1定义:a, b


初等数论 第一章 整除1-4_图文.ppt

初等数论 第一章 整除1-4 - 《初等数论》 教师:何艳 2015-4-28


初等数论 第一章 整除1-4_图文.ppt

初等数论 第一章 整除1-4 - 数论的基本内容 按照研究方法的不同,数论可分为


初等数论 第一章 整除5-7_图文.ppt

初等数论 第一章 整除5-7 - §5 算术基本定理 整数分解唯一性定理也称算术


初等数论1整除_图文.pdf

初等数论1整除 - 《初等数论(闵嗣鹤、严士健)》第三版... 初等数论1整除_数学_自然科学_专业资料。《初等数论(闵嗣鹤、严士健)》第三版 第一章 整数的可除性整除...


初等数论-第一章_图文.ppt

初等数论-第一章 - 第一章 一、整除的概念 整数的可除性 带余数除法 二、最大公因数与辗转相除法 三、整除的进一步性质 四、质数 算术基本定理 五、取整函数...


初等数论§1整除_图文.ppt

初等数论§1整除 - 第一章 整数的可除性 整除性理论是初等数论的基础,本章要介


§2初等数论--整除_图文.ppt

§2初等数论--整除 - 数论是竞赛数学中最重要的一部分,特别是在1991 年,


初等数论第一章.doc

初等数论第一章 - 第一章 整除理论 整除性理论是初等数论的基础。本章要介绍带余


初等数论第一章1_图文.ppt

初等数论第一章1 - 初等数论 Number Theory 第一章 整除理论 ?


x初等数论-第一章_图文.ppt

x初等数论-第一章 - 《初等数论》 教师:何艳 数论的基本内容 按照研究方法的不同,数论可分为 初等数论 解析数论 代数数论 几何数论 参考书目 1、南基洙主编《...


§2初等数论--整除_图文.ppt

§2初等数论--整除 - 第一章 整数的可除性 整除性理论是初等数论的基础,本章


初等数论第一章3_图文.ppt

初等数论第一章3 - 初等数论 Number Theory 第一章 整除理论 ?


初等数论第一章2_图文.ppt

初等数论第一章2 - 初等数论 Number Theory 第一章 整除理论 ?


初等数论第一章4_图文.ppt

初等数论第一章4 - 初等数论 Number Theory 第一章 整除理论 ?


初等数论第一章5_图文.ppt

初等数论第一章5 - 初等数论 Number Theory 第一章 整除理论 ?


初等数论第一章7_图文.ppt

初等数论第一章7 - 初等数论 Number Theory 第一章 整除理论 ?


初等数论第一章6_图文.ppt

初等数论第一章6 - 初等数论 Number Theory 第一章 整除理论 ?


初等数论.doc

初等数论 - 第一章整除理论 整除性理论是初等数论的基础。本章要介绍带余数除法,


1.1.1数论简介与整除_图文.ppt

1.1.1数论简介与整除 - 初等数论 郑州师范学院 数统学院 陈宏道 一 初等数论及其主要内容 数论是研究整数性质的一门很古老的数学 分支,其初等部分是以整数的...

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