数论初步(一)
主讲老师：李晓均
整数的整除性
定义：设a，b为二整数，且b≠０，如果有一整数c，使a＝bc，则称b是a的约数，a 是b的倍数，又称b整除a，记作b|a.
显然，１能整除任意整数，任意整数都能整除０.
性质：设a，b，c均为非零整数，则
①．若c|b，b|a，则c|a.
②．若b|a，则bc|ac
③．若c|a，c|b，则对任意整数m、n，有c|ma＋nb
④．若b|ac，且(a，b)＝1，则b|c
证明：因为(a，b)＝1
则存在两个整数s，t，使得
as＋bt＝1
∴ asc＋btc＝c
∵ b|ac ? b|asc
∴ b|(asc＋btc) ? b|c
⑤．若(a，b)＝1，且a|c，b|c，则ab|c
证明：a|c，则c＝as(s∈Z)
又b|c，则c＝bt(t∈Z)
又(a，b)＝1
∴ s＝bt'(t'∈Z)
于是c＝abt'
即ab|c
⑥．若b|ac，而b为质数，则b|a，或b|c
⑦．(a－b)|(a n－b n)(n∈N)，(a＋b)|(a n＋b n)(n为奇数)
整除的判别法：设整数N ＝121n 1a a a a -
①.2|a 1?2|N ，
5|a 1? 5|N
②.3|a 1＋a 2＋…＋a n ?3|N
9|a 1＋a 2＋…＋a n ?9|N
③.4|a a
? 4|N
25|a a
? 25|N
④.8|a a a
?8|N
125|a a a ?125|N
⑤．7||41n n a a a -－a
a a |?7|N
⑥．11||41n n a a a -－a a a
|?11|N
⑦．11|[(a 2n ＋1＋a 2n －1＋…＋a 1)－(a 2n ＋a 2n －2＋…＋a 2)]
?11|N
⑧．13||41n n a a a -－a a a |?13|N
推论：三个连续的整数的积能被６整除.
例题：
1.设一个五位数d a c b a ，其中d －b ＝3，试问a ，c 为何值时，这个五位数被11整除. 解：11|d a c b a
∴ 11|a ＋c ＋d －b －a
即11|c ＋3
∴ c ＝8
1≤a ≤9，且a ∈Z
2.设72|b 673a ，试求a ，b 的值.
解：72＝8×9，且(8，9)＝1
∴ 8|b 673
a ，且9|
b 673a
73 b＝6
∴ 8|b
且 9|a＋6＋7＋3＋6
即9|22＋a
∴ a＝5
3.设n为自然数，A＝3237n－632n－855n＋235n，
求证:1985|A.
证明：∵1985＝397×5
A＝(3237n－632n)－(855n－235n)
＝(3237－632)×u－(855－235)×v(u，v∈Z)
＝5×521×u－5×124×v
∴5|A
又A＝(3237n－855n)－(623n－235n)
＝(3237－855)×s－(623－235)×t(s，t∈Z)
＝397×6×s－397×t
∴ 397｜A
又∵(397,5)＝1
∴397×5｜A
即1985｜A
4.证明：没有x，y存在，使等式x2＋y2＝1995(x，y∈Z)成立.
证：假设有整数x，y存在，使x2＋y2＝1995成立。
∵x2，y2被４除余数为０或１.
∴x2＋y2被４除余数为０，１或２.
又∵1995被４除余数为３.
∴得出矛盾，假设不成立.
故没有整数x，y存在，使x2＋y2＝1995成立.
费马小定理：若p是素数，(m，p)＝1
则 p|m p－1－1
5.试证：999…9能被13整除.
12个
证明：∵10－1＝9,100－1＝99,…?1012－1＝999…9.
12个 又（10,13）=1
∴13｜(1013－1－1),即13｜(1012
－1) ∴13 ｜999…9.
12个
6.请确定最小的正整数A ，其末位数是6，若将未位的6移至首位，其余数字不变，其值变为原数的4倍.
解：设该数为A ＝12n 1n n a a a a --，其中a 1＝6
令x ＝22n 1n n a a a a --
则A ＝6x ＝x ·10＋6
于是4A ＝x 6＝6×10n －1＋x
即有4×10x ＋24＝6×10n －1＋x
x ＝13
)410(21n -- ∵ (2，13)＝1，x 是整数
∴ 13|(10n －1－4)
n ＝1，2时，10
n －1－4＜10显然不满足条件 n ＝3时，10
n －1－4＝96 不满足条件 n ＝4时，10
n －1－4＝996 不满足条件 n ＝5时，10
n －1－4＝9996不满足条件 n ＝6时，10
n －1－4＝99996 满足条件 ∴ x ＝13
999962?＝15384 即A ＝153846
7.一个正整数，如果用７进制表示为abc，如果用５进制表示为cba，请用10进制表示这个数. 解：由题意知：0＜a,c≤4,0≤b≤4,设这个正整数为n,则
n＝abc＝a×72＋b×7＋c, n=cba=c×52＋b×5＋a
∴49a＋7b＋c＝25c＋5b＋a
48a＋2b－24c＝0
b＝12(c－2a)
∴12｜b,
又∵0≤b≤4
∴b＝0,
∴c＝2a
∴当a＝1,c＝2时，n＝51
当a＝2,c＝4时，n＝102
练习：
1.证明：设N＝19881988－19861986，则1987∣N
2.设n是自然数，求证n5－n可被30整除.
3.请确定最小的正整数A，其末位数为2，若将末位数2移至首位，其余数字不变，则是原数的
2倍.
4.一个正整数，若用9进制表示为abc，若用7进制表示为cba，请用10进制表示此数.
5.五位数
67a
a4能被4整除，最末两位组成的数a7能被6整除，求此五位数.
知识框架 」、整除的定义： 当两个整数a和b （b工0, a被b除的余数为零时（商为整数），则称a被b整除或b整除a,也把a 叫做b的倍数，b叫a的约数，记作b|a，如果a被b除所得的余数不为零，则称a不能被b整除，或b不整除a,记作b a. 二、常见数字的整除判定方法 1. 一个数的末位能被2或5整除，这个数就能被2或5整除； 一个数的末两位能被4或25整除，这个数就能被4或25整除； 一个数的末三位能被8或125整除，这个数就能被8或125整除； 2. 一个位数数字和能被3整除，这个数就能被3整除； 一个数各位数数字和能被9整除，这个数就能被9整除； 3. 如果一个整数的奇数位上的数字之和与偶数位上的数字之和的差能被11整除，那么这个数能被11整 除； 4. 如果一个整数的末三位与末三位以前的数字组成的数之差能被7、11或13整除，那么这个数能被7、 11或13整除； 5. 如果一个数从数的任何一个位置随意切开所组成的所有数之和是9的倍数，那么这个数能被9整除； 6. 如果一个数能被99整除，这个数从后两位开始两位一截所得的所有数（如果有偶数位则拆出的数都有 两个数字，如果是奇数位则拆出的数中若干个有两个数字还有一个是一位数）的和是99的倍数，这个数一定是99的倍数。 7. 若一个整数的个位数字截去，再从余下的数中，减去个位数的2倍，如果差是7的倍数，则原数能被 7整除。如果差太大或心算不易看出是否7的倍数，就需要继续上述「截尾、倍大、相减、验差」的 过程，直到能清楚判断为止。例如，判断133是否7的倍数的过程如下：13-3X2 = 7,所以133是7 的倍数；又例如判断6139是否7的倍数的过程如下：613 —9>2= 595 , 59- 5X2= 49,所以6139是7的倍数，余类推。 8. 若一个整数的个位数字截去，再从余下的数中，加个位数的4倍，如果和是13的倍数，则原数能被 13整除。如果和太大或心算不易看出是否13的倍数，就需要继续上述「截尾、倍大、相加、验差」 的过程，直到能清楚判断为止。 MSDC模块化分级讲义体系六年级奥数.数论.整除问题（ABC级）.学生版Page 1 of 14
1.数论——数的整除和余数 2.1基本概念和基本性质 2.1.1定义 整数a除以整数b（b≠0），除得的商是整数而没有余数，我们就说a能被b 整除，或者说b能整除a。 2.1.2表达式和读法 b∣a，读着b能整除a;或a能被b整除；b a，不能整除； 2.1.3基本性质 ①传递性：如果a|b,b|c,那么a|c;即b是a的倍数，c是b的倍数，则c肯定是a的 倍数； ②加减性：如果a|b、a|c，那么a|(b c); ③因数性：如果ab|c，那么a|c，b|c;即如果ab的积能整除c,则a或b皆能整除 c; ④互质性，如果a|c，b|c，且（a,b）=1,那么ab|c,即如果a能整除c,b能整除c， 且ab互质，则ab的积能整除c; ⑤a个连续自然数中必恰有一个数能被a整除。
2.2数的整除的判别法 2.2.1末位判别法 2.2.2数字和判别法（用以判别能否被3或9整除） 各数位上数字的和是3或9的倍数，则能被3或9整除。 173652÷9:1+7+3+6+5+2的和除以3或9； 简便算法，利用整除的加减性，可以去掉1个或多个9，剩下数字的和x再除以3或9；如果x﹥9,则余数为x-9;如果x﹤9,则余数为x。 2.2.3奇偶数位判别法（用以判别能否被11整除） 从右往左编号，编号为奇数的为奇数位，编号为偶数的为偶数位，看奇数位上的数字的和与偶数位上的数字的和的两者之差是否能被11整除； 81729033÷11:奇数位和为6，偶数位和为27；如果奇数位和比偶数位和小，则奇数位和加1个或多个11，直到够减。余数的判断法与整数位的判断法一致。
2.2.4三位一截判别法（用以判别能否被7/11/13整除） 2.2.4.1基本用法 从右往左三位一截并编号，编号为奇数的为奇数段，编号为偶数的为偶数段，看奇数段的数字的和与偶数段的数字的和的两者之差是否能被7、11、13整除； 如，86372548，奇数段的和为（548+86），偶数段的和为372，求两者差看能否被7整除，同样，不够减前面加1个或多个7，直到够减，余数位的判断法与整数位的判断法一致。 2.2.4.2特殊用法 ①一般求空格数 如果中间有空格，则利用加减性加或减除数7的倍数，分别从右边和左边抵消缩减位数，到最后看7的哪个倍数与缩减后的末位数相同，并看7的哪个倍数与缩减后的首位数相同，则前一个倍数的十位数和后一个倍数的个位数的和即为空格中应填的数。注意，如果这个数加或减7后为1到9间的自然数，则加或减7后的这个数也为正确答案。 395864□82365，答案为5 463925□01234，答案为1和8 ②特殊求空格数 根据整除的因数性，如果1个数能被1001整除，则这个数能被7、11、13、77、91、143整除，因为： 7×11×13=1001; 77×13=1001; 99×11=1001;
小奥数论整除和余数知识 点总结及例题 Prepared on 21 November 2021
1.数论——数的整除和余数 2.1基本概念和基本性质 整数a除以整数b（b≠0），除得的商是整数而没有余数，我们就说a能被b 整除，或者说b能整除a。 b∣a，读着b能整除a;或a能被b整除；ba，不能整除； ①传递性：如果a|b,b|c,那么a|c;即b是a的倍数，c是b的倍数，则c肯 定是a的倍数； ②加减性：如果a|b、a|c，那么a|(b c); ③因数性：如果ab|c，那么a|c，b|c;即如果ab的积能整除c,则a或b皆能 整除c; ④互质性，如果a|c，b|c，且（a,b）=1,那么ab|c,即如果a能整除c,b能 整除c，且ab互质，则ab的积能整除c; ⑤a个连续自然数中必恰有一个数能被a整除。 各数位上数字的和是3或9的倍数，则能被3或9整除。 173652÷9:1+7+3+6+5+2的和除以3或9； 简便算法，利用整除的加减性，可以去掉1个或多个9，剩下数字的和x 再除以3或9；如果x﹥9,则余数为x-9;如果x﹤9,则余数为x。 从右往左编号，编号为奇数的为奇数位，编号为偶数的为偶数位，看奇数位上的数字的和与偶数位上的数字的和的两者之差是否能被11整除； 奇数位和为6，偶数位和为27；如果奇数位和比偶数位和小，则奇数位和加1个或多个11，直到够减。余数的判断法与整数位的判断法一致。 2.2.4三位一截判别法（用以判别能否被7/11/13整除）
从右往左三位一截并编号，编号为奇数的为奇数段，编号为偶数的为偶数段，看奇数段的数字的和与偶数段的数字的和的两者之差是否能被7、11、13整除； 两者差看能否被7整除，同样，不够减前面加1个或多个7，直到够减，余数位的判断法与整数位的判断法一致。 ① 一般求空格数 如果中间有空格，则利用加减性加或减除数7的倍数，分别从右边和左边抵消缩减位数，到最后看7的哪个倍数与缩减后的末位数相同，并看7的哪个倍数与缩减后的首位数相同，则前一个倍数的十位数和后一个倍数的个位数的和即为空格中应填的数。注意，如果这个数加或减7后为1到9间的自然数，则加或减7后的这个数也为正确答案。 395864□82365，答案为5 463925□01234，答案为1和8 ② 特殊求空格数 根据整除的因数性，如果1个数能被1001整除，则这个数能被7、11、13、77、91、143整除，因为： 7×11×13=1001; 77×13=1001; 99×11=1001; 7×143=1001; 根据abc → abc → =abc → ×1001; aaa → aaa → =aaa → ×1001;求能被7整除的空格数 系列截判法（用以判别能否被9/99/999整除） 除数是几位数就可以从右往左几位一截，将截取的段位数相加再截取，直至不能再截取，看相应的数能否被相应的除数9/99/999整除。 除数是11时，也可以用两位一截判别法，因为根据整数的因数性，能被99整除的数，肯定能被11整除。 例如： 2.3余数的判别法 ① 整除是余数为0的情况。a ÷b=c …..0； 此时，a=b ×c;b=a ÷c
《数论》第一章补充例题 整除性理论是初等数论的基础.本章要介绍带余数除法,辗转相除法,最大公约数,最小公倍数,算术基本定理以及它们的一些应用. 1整数的整除性 例1设A={d1,d2,···,dk}是n的所有约数的集合,则 }{nnn,,···,B=d1d2dk 也是n的所有约数的集合. 解由以下三点理由可以证得结论: (i)A和B的元素个数相同; (ii)若di∈A,即di|n,则(iii)若di=dj,则问: d(1)+d(2)+···+d(1997) 是否为偶数? n解对于n的每个约数d,有n=d·n,因此,n的正约数d与是成对地出现的.只有 n2当d=n,即d=n时,d和才是同一个数.故当且仅当n是完全平方数时,d(n)是奇数.nini|n,反之亦然;=nj.例2以d(n)表示n的正约数的个数,例 如:d(1)=1,d(2)=2,d(3)=2,d(4)=3,···. 因为442<1997<452,所以在d(1),d(2),···,d(1997)中恰有44个奇数,故 d(1)+d(2)+···+d(1997)是偶数. 问题d2(1)+d2(2)+···+d2(1997)被4除的余数是多少? 例3证明:存在无穷多个正整数a,使得 n4+a(n=1,2,3,···) 都是合数. ? ?例题中引用的定理或推论可以在教材相应处找到. 1 解取a=4k4,对任意的n∈N,有 n4+4k4=(n2+2k2)2?4n2k2=(n2+2k2+2nk)(n2+2k2?2nk). 由 n2+2k2?2nk=(n?k)2+k2??k2, 所以,对于任意的k=2,3,···以及任意的n∈N,n4+a是合数.
数的整除 知识框架 一、整除的定义： 当两个整数a和b（b≠0），a被b除的余数为零时（商为整数），则称a被b整除或b整除a，也把a 叫做b的倍数，b叫a的约数，记作b|a，如果a被b除所得的余数不为零，则称a不能被b整除，或b 不整除a，记作b a. 二、常见数字的整除判定方法 1.一个数的末位能被2或5整除，这个数就能被2或5整除； 一个数的末两位能被4或25整除，这个数就能被4或25整除； 一个数的末三位能被8或125整除，这个数就能被8或125整除； 2.一个位数数字和能被3整除，这个数就能被3整除； 一个数各位数数字和能被9整除，这个数就能被9整除； 3.如果一个整数的奇数位上的数字之和与偶数位上的数字之和的差能被11整除，那么这个数能被11整 除； 4.如果一个整数的末三位与末三位以前的数字组成的数之差能被7、11或13整除，那么这个数能被7、 11或13整除； 5.如果一个数从数的任何一个位置随意切开所组成的所有数之和是9的倍数，那么这个数能被9整除； 6.如果一个数能被99整除，这个数从后两位开始两位一截所得的所有数（如果有偶数位则拆出的数都有 两个数字，如果是奇数位则拆出的数中若干个有两个数字还有一个是一位数）的和是99的倍数，这个数一定是99的倍数。 7.若一个整数的个位数字截去，再从余下的数中，减去个位数的2倍，如果差是7的倍数，则原数能被 7整除。如果差太大或心算不易看出是否7的倍数，就需要继续上述「截尾、倍大、相减、验差」的过程，直到能清楚判断为止。例如，判断133是否7的倍数的过程如下：13－3×2＝7，所以133是7的倍数；又例如判断6139是否7的倍数的过程如下：613－9×2＝595 ，59－5×2＝49，所以6139是7的倍数，余类推。 8.若一个整数的个位数字截去，再从余下的数中，加个位数的4倍，如果和是13的倍数，则原数能被 13整除。如果和太大或心算不易看出是否13的倍数，就需要继续上述「截尾、倍大、相加、验差」
第一章整除理论 整除性理论是初等数论的基础。本章要介绍带余数除法，辗转相除法，最大公约数，最小公倍数，算术基本定理以及它们的一些应用。 第一节数的整除性 定义1设a，b是整数，b≠ 0，如果存在整数c，使得 a = bc 成立，则称a被b整除，a是b的倍数，b是a 的约数（因数或除数），并且使用记号b∣a；如果不存在整数c使得a = bc成立，则称a不被 b整除，记为b|/a。 显然每个非零整数a都有约数±1，±a，称这四个数为a的平凡约数，a的另外的约数称为非平凡约数。 被2整除的整数称为偶数，不被2整除的整数称为奇数。 定理1下面的结论成立： (ⅰ) a∣b?±a∣±b； (ⅱ) a∣b，b∣c?a∣c； (ⅲ) b∣a i，i = 1, 2, , k?b∣a1x1+ a2x2+ +a k x k，此处x i（i = 1, 2, , k）是
任意的整数； (ⅳ) b∣a ?bc∣ac，此处c是任意的非零整数； (ⅴ) b∣a，a≠ 0 ? |b| ≤ |a|；b∣a 且|a| < |b| ?a = 0。 证明留作习题。 定义2若整数a≠0，±1，并且只有约数±1和±a，则称a是素数（或质数）；否则称a为合数。 以后在本书中若无特别说明，素数总是指正素数。 定理2任何大于1的整数a都至少有一个素约数。 证明若a是素数，则定理是显然的。 若a不是素数，那么它有两个以上的正的非平凡约数，设它们是d1, d2, , d k 。不妨设d1是其中最小的。若d1不是素数，则存在e1 > 1，e2 > 1，使得d1 = e1e2，因此，e1和e2也是a的正的非平凡约数。这与d1的最小性矛盾。所以d1是素数。证毕。 推论任何大于1的合数a必有一个不超过 证明使用定理2中的记号，有a = d1d2，其中d1 > 1是最小的素约数，所以d12≤a。证毕。 例1设r是正奇数，证明：对任意的正整数n，有 n+ 2|/1r+ 2r+ +n r。
第五节 初等数论中的几个重要定理 基础知识 定义（欧拉(Euler)函数）一组数s x x x ,,,21 称为是模m 的既约剩余系，如果对任意的s j ≤≤1，1),(=m x j 且对于任意的Z a ∈，若),(m a ＝1，则有且仅有一个j x 是a 对模m 的剩余，即)(mod m x a j ≡。并定义},,2,1{)(m s m ==?中和m 互质的数的个数，)(m ?称为欧拉（Euler ）函数。 这是数论中的非常重要的一个函数，显然1)1(=?，而对于1>m ，)(m ?就是1,2，…，1-m 中与m 互素的数的个数，比如说p 是素数，则有1)(-=p p ?。 引理：∏? =为质数）－（P |P 11)(m P m m ?；可用容斥定理来证（证明略）。 定理1：（欧拉（Euler ）定理）设),(m a ＝1，则)(mod 1)(m a m ≡?。 证明：取模m 的一个既约剩余系))((,,,,21m s b b b s ?= ，考虑s ab ab ab ,,,21 ，由于a 与m 互质，故)1(s j ab j ≤≤仍与m 互质，且有i ab )1(s j i ab j ≤<≤?，于是对每个 s j ≤≤1都能找到唯一的一个s j ≤≤)(1σ， 使得)(mod )(m b ab j j σ≡，这种对应关系σ是一一的，从而)(mod )(mod )(11)(1m b m b ab s j j s j j s j j ∏∏∏===≡≡σ，∴))(mod ()(11m b b a s j j s j j s ∏∏==≡。 1),(1=∏=s j j b m ，)(mod 1m a s ≡∴，故)(mod 1)(m a m ≡?。证毕。 分析与解答：要证)(mod 1)(m a m ≡?，我们得设法找出)(m ?个n 相乘，由)(m ?个数我们想到m ,,2,1 中与m 互质的)(m ?的个数：)(21,,,m a a a ? ，由于),(m a ＝1，从而)(21,,,m aa aa aa ? 也是与m 互质的)(m ?个数，且两两余数不一样，故)(21m a a a ???? ≡)(21,,,m aa aa aa ? ≡)(m a ?)(21m a a a ???? （m mod ），而 （)(21m a a a ???? m ）＝1，故)(mod 1)(m a m ≡?。 这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。
九 进 制 乔治·兰伯特是美国加利福尼亚州一所中学的数学教师，他对数学特别敏感而且有极大的研究兴趣。他常年与数字、公式打交道，深感数学的神秘与魅力。他开始注意一些巧合的事件，力图用数学的方式来破解巧合。 他发现：法国皇帝拿破仑与纳粹元首希特勒相隔一个多世纪，但是他们之间有很多数字巧合。拿破仑1804年执政，希特勒1933年上台，相隔129年。拿破仑1816年战败，希 特勒1945年战败，相隔129年。拿破仑1809年占领维也纳，希特勒在1938 年攻人维也纳，也是相隔129年。拿破仑1812年进攻俄国，希特勒在相隔 129年后进攻苏联。美国第16届总统林肯于1861年任总统，美国第35届 总统肯尼迪于1961年任总统，时隔100年。两人同在星期五并在女人的参 与下被刺遇害。接任肯尼迪和林肯的总统的名字都叫约翰逊。更巧的是， 杀害林肯的凶手出生于1829年，杀害肯尼迪的凶手出生于1929年，相隔 又是100年。 兰伯特被这些数字迷住了，他经常将这些数字翻来覆去地分解组合。 他惊奇地发现，拿破仑和希特勒的巧合数129与林肯和肯尼迪的巧合数100，把它们颠倒过去分别是921和001，用921减去129，用100减去001，得数都能被9除尽：921-129=792，100-001=99；792+9=88，99÷9=11，结果都有一个十位和个位都相同的两位数的商。 兰伯特非常吃惊，他对9着了迷。他发现将l 、2、3、4、5、6、7、8、9加在一起是45，而4+5=9。他还发现，用9乘以任何一个数，将所得到的积的各位数字相加，所得到的和总是9。取任何一个数，比如说2004，将每位数加起来是2+0+0+4=6，用2004减去6结果得到1998，而1998÷9=222，能被9除尽。 他还总结出这样一个规律：把一个大数的各位数字相加得到一个和，再把这个和的各位数字相加又得到一个和。这样继续下去，直到最后的数字之和是一个一位数为止。最后这个数称为最初那个数的“数字根”，这个数字等于原数除；29的余数，这个计算过程被称作是“弃9法”。懂得了弃9法，蓝伯特醒悟了不少，他进而想到，人类不应该10个10个地数数，也不应该12个12个数数，而应该9个9个地数数，实行9进制。 课前预习 数论之整除性
1. 数论——数的整除和余数 2.1基本概念和基本性质 整数a 除以整数b （b≠0），除得的商是整数而没有余数，我们就说a 能被b 整除，或者说b 能整除a 。 b ∣a ，读着b 能整除a;或a 能被b 整除； ba ，不能整除； ① 传递性：如果a|b,b|c,那么a|c;即b 是a 的倍数，c 是b 的倍数，则c 肯定是a 的倍 数； ② 加减性：如果a|b 、a|c ，那么a|(b c); ③ 因数性：如果ab|c ，那么a|c ，b|c;即如果ab 的积能整除c,则a 或b 皆能整除c; ④ 互质性，如果a|c ，b|c ，且（a,b ）=1,那么ab|c,即如果a 能整除c,b 能整除c ，且 ab 互质，则ab 的积能整除c; ⑤ a 个连续自然数中必恰有一个数能被a 整除。 2.2数的整除的判别法
各数位上数字的和是3或9的倍数，则能被3或9整除。 173652÷9:1+7+3+6+5+2的和除以3或9； 简便算法，利用整除的加减性，可以去掉1个或多个9，剩下数字的和x 再除以3或9；如果x﹥9,则余数为x-9;如果x﹤9,则余数为x。 从右往左编号，编号为奇数的为奇数位，编号为偶数的为偶数位，看奇数位上的数字的和与偶数位上的数字的和的两者之差是否能被11整除； 奇数位和为6，偶数位和为27；如果奇数位和比偶数位和小，则奇数位和加1个或多个11，直到够减。余数的判断法与整数位的判断法一致。 2.2.4三位一截判别法（用以判别能否被7/11/13整除） 从右往左三位一截并编号，编号为奇数的为奇数段，编号为偶数的为偶数段，看奇数段的数字的和与偶数段的数字的和的两者之差是否能被7、11、13整除； 两者差看能否被7整除，同样，不够减前面加1个或多个7，直到够减，余数位的判断法与整数位的判断法一致。 ①一般求空格数 如果中间有空格，则利用加减性加或减除数7的倍数，分别从右边和左边抵消缩减位数，到最后看7的哪个倍数与缩减后的末位数相同，并看7的哪个倍数与缩减后的首位数相同，则前一个倍数的十位数和后一个倍数的个位数的和即为空格中应填的数。注意，如果这个数加或减7后为1到9间的自然数，则加或减7后的这个数也为正确答案。
第三次作业答案： 一、选择题 1、整数5874192能被( B )整除. A 3 B 3与9 C 9 D 3或9 2、整数637693能被(C )整除. A 3 B 5 C 7 D 9 3、模5的最小非负完全剩余系是( D ). A -2,-1,0,1,2 B -5,-4,-3,-2,-1 C 1,2,3,4,5 D 0,1,2,3,4 4、如果)(mod m b a ≡,c 是任意整数,则（A ） A )(mod m bc ac ≡ B b a = C ac T )(m od m bc D b a ≠ 二、解同余式（组） （1）)132(mod 2145≡x . 解 因为(45,132)=3|21,所以同余式有3个解. 将同余式化简为等价的同余方程 )44(mod 715≡x . 我们再解不定方程 74415=-y x , 得到一解(21,7). 于是定理4.1中的210=x . 因此同余式的3个解为 )132(mod 21≡x , )132(mod 65)132(mod 3 13221≡+ ≡x , )132(mod 109)132(mod 3132221≡?+≡x . （2）)45(mod 01512≡+x 解 因为(12,45)=3|15,所以同余式有解,而且解的个数为3. 又同余式等价于)15(mod 054≡+x ,即y x 1554=+. 我们利用解不定方程的方法得到它的一个解是(10,3), 即定理4.1中的100=x . 因此同余式的3个解为 )45(mod 10≡x ,
)45(mod 25)45(mod 3 4510≡+≡x , )45(mod 40)45(mod 3 45210≡?+≡x . （3）)321 (m od 75111≡x . 解 因为(111,321)=3|75,所以同余式有3个解. 将同余式化简为等价的同余方程 )107(mod 2537≡x . 我们再解不定方程 2510737=+y x , 得到一解(-8,3). 于是定理4.1中的80-=x . 因此同余式的3个解为 )321(mod 8-≡x , )321(mod 99)321(mod 3 3218≡+-≡x , )321(mod 206)321(mod 3 32128≡?+-≡x . （4）?? ???≡≡≡)9(mod 3)8(mod 2)7(mod 1x x x . 解 因为(7,8,9)=1,所以可以利用定理5.1.我们先解同余式 )7(mod 172≡x ,)8(mod 163≡x ,)9(mod 156≡x , 得到)9(mod 4),8(mod 1),7(mod 4321-=-==x x x .于是所求的解为 ). 494(mod 478)494(mod 510 )494(mod 3)4(562)1(631472=-=?-?+?-?+??≡x （5）???????≡≡≡≡) 9(mod 5)7(mod 3)5(mod 2)2(mod 1x x x x . (参考上题)
一、整除的定义： 当两个整数a 和b （b≠0），a 被b 除的余数为零时（商为整数），则称a 被b 整除或b 整除a ，也把a 叫做b 的倍数，b 叫a 的约数，记作b|a ，如果a 被b 除所得的余数不为零，则称a 不能被b 整除，或b 不整除a ，记作b a. 二、常见数字的整除判定方法 1. 一个数的末位能被2或5整除，这个数就能被2或5整除； 一个数的末两位能被4或25整除，这个数就能被4或25整除； 一个数的末三位能被8或125整除，这个数就能被8或125整除； 2. 一个位数数字和能被3整除，这个数就能被3整除； 一个数各位数数字和能被9整除，这个数就能被9整除； 3. 如果一个整数的奇数位上的数字之和与偶数位上的数字之和的差能被11整除，那么这个数能被11整 除； 4. 如果一个整数的末三位与末三位以前的数字组成的数之差能被7、11或13整除，那么这个数能被7、 11或13整除； 5. 如果一个数从数的任何一个位置随意切开所组成的所有数之和是9的倍数，那么这个数能被9整除； 6. 如果一个数能被99整除，这个数从后两位开始两位一截所得的所有数（如果有偶数位则拆出的数都有 两个数字，如果是奇数位则拆出的数中若干个有两个数字还有一个是一位数）的和是99的倍数，这个数一定是99的倍数。 7. 若一个整数的个位数字截去，再从余下的数中，减去个位数的2倍，如果差是7的倍数，则原数能被 7整除。如果差太大或心算不易看出是否7的倍数，就需要继续上述「截尾、倍大、相减、验差」的过程，直到能清楚判断为止。例如，判断133是否7的倍数的过程如下：13－3×2＝7，所以133是7的倍数；又例如判断6139是否7的倍数的过程如下：613－9×2＝595 ， 59－5×2＝49，所以6139是7的倍数，余类推。 8. 若一个整数的个位数字截去，再从余下的数中，加个位数的4倍，如果和是13的倍数，则原数能被 13整除。如果和太大或心算不易看出是否13的倍数，就需要继续上述「截尾、倍大、相加、验差」知识框架 数的整除
初等数论中的几个重要定理 基础知识 定义（欧拉(Euler)函数）一组数称为是模的既约剩余系，如果对任意的，且对于任意的，若＝1，则有且仅有一个是对模的剩余，即。并定义中和互质的数的个数， 称为欧拉（Euler）函数。 这是数论中的非常重要的一个函数，显然，而对于，就是1,2，…， 中与互素的数的个数，比如说是素数，则有。 引理：；可用容斥定理来证（证明略）。 定理1：（欧拉（Euler）定理）设＝1，则。 分析与解答：要证，我们得设法找出个相乘，由个数我们想到中与互质的的个数：，由于＝1，从而 也是与互质的个数，且两两余数不一样，故 （），而（）＝1，故。 证明：取模的一个既约剩余系，考虑，由 于与互质，故仍与互质，且有，于是对每
个都能找到唯一的一个，使得，这种对应关系 是一一的，从而，。 ，，故。证毕。 这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。 定理2：（费尔马（Fermat）小定理）对于质数及任意整数有。 设为质数，若是的倍数，则。若不是的倍数，则 由引理及欧拉定理得，，由此即得。 定理推论：设为质数，是与互质的任一整数，则。 定理3：（威尔逊（Wilson）定理）设为质数，则。 分析与解答：受欧拉定理的影响，我们也找个数，然后来对应乘法。 证明：对于，在中，必然有一个数除以余1，这是因为 则好是的一个剩余系去0。 从而对，使得； 若，，则，，故 对于，有。即对于不同的对应于不同的，即中数可两两配对，其积除以余1，然后有，使，即与它自
己配对，这时，，或， 或。 除外，别的数可两两配对，积除以余1。故。定义：设为整系数多项式（），我们把含有的一组同余式 （）称为同余方组程。特别地，，当均为的一次整系数多项式时，该同余方程组称为一次同余方程组.若整数同时满足： ，则剩余类（其中）称为同余方程组的一个解，写作 定理4：（中国剩余定理）设是两两互素的正整数，那么对于任意整数 ，一次同余方程组，必有解，且解可以写为： 这里，，以及满足， （即为对模的逆）。 中国定理的作用在于它能断言所说的同余式组当模两两互素时一定有解，而对于解的形式并不重要。 定理5： （拉格郎日定理）设是质数，是非负整数，多项式 是一个模为次的整系数多项式（即），则同余方程至多有个解（在模有意义的情况下）。
数论讲义 整除性问题 1 证明算术基本定理 证明：Z b a ∈,,0>b ，则r bq a +=，b r <≤0，r q ,是唯一确定的。 证明：若a|c,b|c,(a,b)=1,则ab|c 若a|bc,(a,b)=1,则a|c (a,b)=1 代表两数互质 2 整数的性质 整数n 与1+n 之间不再有其它整数，从而2 n 与2)1(+n 之间也不再有其它平方数，任一整数有限集必有最大数与最小数，整数b a >等价于1+≥b a 等，都体现了整数的离散性。 例1 求证：不存在正整数b a ,，使b a +2 及2b a +都是完全平方数 例2 求证：五个连续整数的平方和不是完全平方数. 例3 已知： (x+a)(x+b)+(x+b)(x+c)+(x+c)(x+a)是完全平方式. 求证： a=b=c. 例4求证：当k 为整数时，方程4x 2+8kx+(k 2+1)=0没有有理数根 4 数的整除特征 求证： 任何n 个连续整数之积一定能被n 整除. 求证：任何n 个连续整数之积一定能被n !整除. n n 321!??= 0111101010a a a a x n n n n +++=-- *∈N x n n n n n n n n n n n n b ab b a b a a b a C C C C ++++=+----11 222 11 )( n b a )(+被a 除的余数等于n b 被a 除的余数 n b a )(+被b 除的余数等于n a 被b 除的余数 ))((1221----+++-=-n n n n n n b ab b a a b a b a M b a )(-= n 为自然数 n n b a b a --|)( ))((1221----++-+=+n n n n n n b ab b a a b a b a =N b a )(+ n 为正奇数 n n b a b a ++|)( 例5 判断3546725能否被13整除？ 例6 设72679a b |，试求,a b 的值. 例7 求证：n 为正奇数时，1236---n n n 能被60整除
利用初等数论思想解决小学数学教学问题 08数学大专（1）班 30308127 丁令万 小学数学的教学过程中，往往教师上课不懂怎么教、学生听不懂，导致恶性循环，使学生数学基础差，解题思想单一等问题严重。为解决这一问题，关键在于授课老师要有良好的教学方法能使学生听懂，并且愿意听。而要达到这一目标，我建议教学过程中采用初等数论的解题思想。 初等数论意指使用不超过高中程度的初等代数处理的数论问题，最主要的工具包括整数的整除性与同余。重要的结论包括中国剩余定理、费马小定理、二次互逆律等等。 解析数论借助微积分及复分析的技术来研究关于整数的问题，主要又可以分为积性数论与加性数论两类。 积性数论藉由研究积性生成函数的性质来探讨质数分布的问题，其中质数定理与狄利克雷定理为这个领域中最著名的古典成果。 加性数论则是研究整数的加法分解之可能性与表示的问题，华林问题是该领域最著名的课题。此外例如筛法、圆法等等都是属于这个范畴的重要议题。我国数学家陈景润在解决“哥德巴赫猜想”问题中使用的是解析数论中的筛法。 数论在数学中的地位是独特的，高斯曾经说过“数学是科学的皇后，数论是数学中的皇冠”。因此，数学家都喜欢把数论中一些悬而未决的疑难问题，叫做“皇冠上的明珠”，以鼓励人们去“摘取”。 简要列出几颗“明珠”：费尔马大定理、孪生素数问题、歌德巴赫猜想、角谷猜想、圆内整点问题、完全数问题…… 下面列举初等数论中的整除性问题来说明数论思想对小学数学教学的作用。 整数的整除性问题，是数论中的最基本问题，也是国内外数学竞赛中最常出现的内容之一．由于整数性质的论证是具体、严格、富有技巧，它既容易使学生接受，又是培养学生逻辑思维和推理能力的一个有效课题，因此，了解一些整数的性质和整除性问题的解法是很有必要的． 1．整除的基本概念与性质 所谓整除，就是一个整数被另一个整数除尽，其数学定义如下． 定义设a，b是整数，b≠0．如果有一个整数q，使得a=bq，那么称a能被b整除，或称b整除a，并记作b｜a．如果不存在这样的整数q，使得a=bq，则称a不能被b整除，或称b不整除a，记作ba． 关于整数的整除，有如下一些基本性质： 性质1 若b｜a，c｜b，则c｜a． 性质2 若c｜a，c｜b，则c｜(a±b)． 性质3 若c｜a，cb，则c(a±b)． 性质4 若b｜a，d｜c，则bd｜ac． 性质5 若a=b＋c，且m｜a，m｜b，则m｜c． 性质6 若b｜a，c｜a，则[b，c]｜a(此处[b，c]为b，c的最小公倍数)．特别地，当(b，c)=1时，bc｜a(此处(b，c)为b，c的最大公约数)．性质7 若c｜ab，且(c，a)=1，则c｜b．特别地，若p是质数，且p｜ab，则p｜a或p｜b． 性质7 若c｜ab，且(c，a)=1，则c｜b．特别地，若p是质数，且p｜ab，则p｜a或p｜b．
第一讲整除问题初步 从这一讲开始,我们将会进人一个神奇而美妙的世界:数论. 什么是数论呢? 人类从学会数数开始,就一直和整数打交道.人们在对整效的应用村研究中,探索出很多奇妙的数学规律,正是这些富有魅力的规律,吸引了古往今来的许多学家,于是就出现了数论这门学科. 确切地说,数论就是一门研究整数性质的学科. 我们就从最基本的性质一一整除开始,一起在数论的海洋中邀游吧. 数论在数学中的地位是独特的,伟大的数学家高斯曾经说过:“数学是科学的皇后,数论是数学的皇冠.” 一、整除的定义 如果整数a除以整数b(b≠0),除得的商是整数且没有余数,找们就说a能被b整除,也可以说b能整除a,记作b|a. 如果除得的结果有余数,我们就说a不能被b整除,也可以说b不能整除a. 二、整除的一些基本性质 1.尾数判断法 (1)能被2、5整除的数的特性:个位数字能被2、5整除. (2)能被4、25整除的数的特性:末两位能被4、25整除. (3)能被8,125整除的数的特性:末三位能被8、125整除. 2.数字求和法 能被3、9整除的数的特性:各位数字之和能被3、9整除. 3.奇偶位求差法 能被11整除的数的特性:“奇位和”与“偶位和”的差能被11整除. 我们把一个数从右往左数的第1、3、5位,··,统称为奇数位,把一个数从右往左数的第2、4、6位,统称为偶数位.我们把“奇数位上的数字之和”简称为“奇位和”,把“偶数位上的数字之和”简称为“偶位和”. 下面我们来看一下如何运用这些性质. 例题1：判断下面11个数的整除性:23487、3568、8875、6765、5880、7538、198954、6512、93625、864、407. (1)这些数中,有哪些数能被4整除?哪些数能被8整除? (2)哪些数能被25整除?哪些数能被125整除? (3)哪些数能被3整除?哪些数能被9整除? (4)哪些数能被11整除? 练习1：在数列3124:、312、3823、45235、5289、5588、661、7314中哪些数能被4整除,哪些数能被3整除,哪些数能被11整除?
第四讲初等数论1——整除性 本讲概述 数论是数学中极其重要又非常迷人的一个分支，目前我们仅学习初等数论中较浅的内容. 初等数论是数学竞赛四大模块中较难以掌握的模块之一，在数学竞赛中占据极其重要的位置.特别是联赛改制以后，二试必考一道50分的数论大题，一试也会有一到两道数论方面的问题.数论与组合水平如何是大家能否获得联赛一等奖甚至更好成绩的关键. 初等数论这块的竞赛问题涉及到的知识点极少，甚至可以说绝大部分同学在小学初中的培训中基本都接触过.但是限于初中的知识面和同学的年龄，考试中一般不出现较为深入、难度较高的数论问题.到了高中，大家将复习小学初中阶段的数论知识，并将其中的很多知识更为理论化、系统化.高中的数论问题难度也会明显增高.但是在数论这一模块中，我们并不提倡大家过多地掌握很多高深的数论知识，而是提倡大家真正去灵活熟练地运用最基本、最重要的数论基础知识和重要定理来解决问题. 由于同学们在小学、初中都已经学过不少关于初等数论的初步知识，所以这里我们把大家比较熟悉的知识都罗列在下面，对其中大部分定理将不给出证明，直接给出结论. 如果不特别说明，本讲中所有字母均代表正整数. 一、整除 1．整除的定义 两个整数a和b(b≠0)，若存在整数k，使得a=bk，我们称a能被b整除，记作b|a．此时把a叫做b 的倍数，b叫做a的约数．如果a除以b的余数不为零，则称a不能被b整除，或b不整除a，记作b a． 2．数的整除特征 （1）1与0的特性： 1是任何整数的约数，即对于任何整数a，总有1|a． 0是任何非零整数的倍数，a≠0，a为整数，则a|0． （2）能被2，5；4，25；8，125；3，9；11，7，13整除的数的特征： 能被2整除的数的特征：个位为0，2，4，6，8的整数能被2整除，我们记为2k(k为整数)． 能被5整除的数的特征：个位数为0或5的整数必被5整除，我们记为5k(k为整数)． 能被4、25整除的数的特征：末两位数字组成的两位数能被4（25）整除的整数必能被4（25）整除．能被8，125整除的数的特征：末三位数字组成的三位数能被8（125）整除的整数必能被8（125）整除． 能被3，9整除的数的特征：各个数位上数字之和能被3或9整除的整数必能被3或9整除． 能被11整除的数的特征：一个整数的奇数位数字之和与偶数位数字之和的差如果是11的倍数，则这个数就能被11整除． 能被7，11，13整除的数的特征：一个三位以上的整数能否被7（11或13）整除，只须看这个数的末三位数字表示的三位数与末三位以前的数字组成的数的差（以大减小）能否被7（11或13）整除． 3．整除的几条性质 （1）自反性：a|a(a≠0) （2）对称性：若a|b, b|a，则a=b （3）传递性：若a|b, b|c，则a|c （4）若a|b, a|c，则a|(b, c) （5）若a|b, m≠0，则am|bm （6）若am|bm, m≠0，则a|b （7）若a|b, c|b, (a, c)=1，则ac|b
小学奥数数论问题知识总结：数的整除性规律 数的整除性规律 【能被2或5整除的数的特征】一个数的末位能被2或5整除，这个数就能被2或5整除 【能被3或9整除的数的特征】一个数，当且仅当它的各个数位上的数字之和能被3和9整除时，这个数便能被3或9整除。 例如，1248621各位上的数字之和是1+2+4+8+6+2+1=24 3｜24，则3｜1248621。 又如，372681各位上的数字之和是3+7+2+6+8+1=27 9｜27，则9｜372681。 【能被4或25整除的数的特征】一个数，当且仅当它的末两位数能被4或25整除时，这个数便能被4或25整除。 例如， 173824的末两位数为24，4｜24，则4｜173824。 43586775的末两位数为75，25｜75，则25｜43586775。 【能被8或125整除的数的特征】一个数，当且仅当它的末三位数字为0，或者末三位数能被8或125整除时，这个数便能被8或125整除。 例如， 32178000的末三位数字为0，则这个数能被8整除，也能够被125整除。 3569824的末三位数为824，8｜824，则8｜3569824。
214813750的末三位数为750，125｜750，则125｜214813750。 【能被7、11、13整除的数的特征】一个数，当且仅当它的末三位数字所表示的数，与末三位以前的数字所表示的数的差（大减小的差）能被7、11、13整除时，这个数就能被7、11、13整除。 例如，75523的末三位数为523，末三位以前的数字所表示的数是75，523-75=448，448÷7=64，即7｜448，则7｜75523。 又如，1095874的末三位数为874，末三位以前的数字所表示的数是1095，1095-874=221，221÷13=17，即13｜221，则13｜1095874。 再如，868967的末三位数为967，末三位以前的数字所表示的数是868，967-868=99，99÷11=9，即11｜99，则11｜868967。 此外，能被11整除的数的特征，还能够这样叙述：一个数，当且仅当它的奇数位上数字之和，与偶数位上数字之和的差（大减小）能被11整除时，则这个数便能被11整除。 例如，4239235的奇数位上的数字之和为4+3+2+5=14，偶数位上数字之和为2+9+3=14，二者之差为14-14=0，0÷11=0，即11｜0，则11｜4239235。
初中数学竞赛专题复习第三篇初等数论第19章 整数的整除性下半部分试题新人教版-精品 2020-12-12 【关键字】方法、条件、问题、矛盾、能力、方式、满足、解决、出发点 综上可知，命题成立． 评注如果两个互质的正整数之积是一个完全平方数，则这两个正整数都是完全平方数．这一命题是我们证明此题的出发点． 19．4．27★★★如果正整数a 、b 、c 满足222c a b =+． 证明：数2c ab +和2c ab -都可以表示为两个正整数的平方和． 解析 巧妙运用下述命题：如果正整数x 可表示为两个正整数的平方和，则2x 也可表示为两个整数的平方和．事实上，设22x u v =+，这里x 、u 、v 都是正整数．则()()22 22222x u v u v u v =+=++-．于是，2x 可表示为两个整数u v +和u v -的平方和，命题获证． 注意到，由条件有 ()()2 2222222c ab c a ab b c a b ±=+±+=+±． 利用已证命题，可知 ()()()22 24c ab c a b c a b ±=+±+-． 记c a b x +±=，c a b y -=，由222c a b =+可知x 、y 都是正整数，并且 ()2224c ab x y ±=+．若x 、y 不同为偶数，则由平方数0≡或()1mod 4，可知221x y +≡或 ()2mod 4，这是一个矛盾．所以，x 、y 都是偶数，从而22 222x y c ab ????±=+ ? ?????，这就是 要证的结论． 评注 这里本质上只是恒等式()()()22 222u v u v u v +=++-的应用，在处理竞赛问题时，代数式变形能力显得十分重要． 19．4．28是否存在正整数m 、n 使得331m n a =++是完全平方数？ 解析 分如下三种情形讨论： （1）若m m 、n 都是偶数，则()31mod 4m ≡，()31mod 4n ≡，所以()3313mod 4m n a =++≡， 故此时a 不是完全平方数． （2）若m 、n 都是奇数，则()33mod 4m ≡，()33mod 4n =，所以()3313mod 4m n a =++≡， 故此时a 不是完全平方数． （3）若m 、n 是一奇一偶，不妨设m 是奇数，n 是偶数，则()33mod8m ≡，()31mod8n ≡，