整数的p 进位制及其应用
基础知识
给定一个m 位的正整数A ，其各位上的数字分别记为021,,,a a a m m --，则此数可以简记为：021a a a A m m --=（其中01≠-m a ）。
由于我们所研究的整数通常是十进制的，因此A 可以表示成10的1-m 次多项
式
，
即
12211101010a a a a A m m m m +?++?+?=---- ，其中
1,,2,1},9,,2,1,0{-=∈m i a i 且01≠-m a ，像这种10的多项式表示的数常常简
记为10021)(a a a A m m --=。在我们的日常生活中，通常将下标10省略不写，并且连括号也不用，记作021a a a A m m --=，以后我们所讲述的数字，若没有指明记数式的基，我们都认为它是十进制的数字。为了具备一般性，我们给出正整数A 的p 进制表示：
012211a p a p a p a A m m m m +?++?+?=---- ，其中1,,2,1},1,,2,1,0{-=-∈m i p a i 且
01≠-m a 。而m 仍然为十进制数字，简记为p m m a a a A )(021 --=。
典例分析
例1．(2007年中国数学奥林匹克协作体竞赛试题)假定正整数N 的8进制表示为
8)43211234567765(=N ，那么下面四个判断中，正确的是（ ）
A 、N 能被7整除而不能被9整除
B 、N 能被9整除而不能被7整除
C 、N 不能被7整除也不能被9整除
D 、N 既能被7整除也能被9整除 答 D
由于)7(mod 18≡，所以)7(mod 18≡i
()∑∑==-≡==k
i k
i i i
i k k a a a a a a N 0
8011)7(mod 8
即N 能被7整除?N 的8进制表示下各位数字之和能被7整除。
类似的，N 能被9整除?N 的8进制表示下奇数位数字之和与偶数位数字之和的差能被9整除
例2． 一个正整数，如果用7进制表示为abc ，如果用5进制表示为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
例3．（第4届美国数学邀请赛试题）
递增数列1,3，4,9，10,12,13，……是由一些正整数组成，它们或是3的幂，或是若个不同的3的幂之和，求该数列的第100项。 解：将已知数列写成3的方幂形式：
,333,33,33,3,33,3,30127126025240131201++=+=+==+===a a a a a a a
易发现其项数恰好是自然数列对应形式的二进制表示：
即 ,2227,226,225,24,223,22,2101220220110++=+=+==+=== 由于100＝2562222)1100100(++= 所以原数列的第100项为981333256=++。
例4．（1987年加拿大数学竞赛试题）
1987可以在b 进制中写成三位数xyz ，如果7891+++=++z y x ，试确定所有可能的z y x ,,,和b 。 解：易知25,19872=++=z y x xb ，从而162)1()1(2=-+-b y b x ， 即109321962])1)[(1(2??==++-y x b b ，
由10>b 知91>-b 。由119622-≥b 知451963<≤b 故4519<-
例5．（第3届加拿大数学竞赛试题）
设n 是五位数（第一个数码不是零），m 是由n 取消它的中间一个数码后所成的四位数，试确定一切n 使得
m
n
是整数。 解：设v u z y x xyzuv n +?+?+?+?==10101010234，其中}9,,2,1,0{,,,, ∈v u z y x 且1≥x ；v u y x xyuv m +?+?+?==10101023； 而m
n
k =
是整数，可证n m <9，即<+?+?+?)101010(923v u y x v u z y x +?+?+?+?10101010234 即z y x v u 223101010880++<+，这显然是成立的；
又可证m n 11<，即v u z y x +?+?+?+?10101010234＜)101010(1123v u y x +?+?+? 即v u y x z 10101010102232+++<，这显然也是正确的。
于是m n m 119<<，即119< 9910≤≤N 。 例6. (1999年，保加利亚数学奥林匹克试题)． 求所有的自然数n 的个救，4≤n≤ 1023．使得n 在二进制表示下，没有连续的三个数码相同． 例7. （l995年．南斯拉夫数学奥林匹克试题） 设n是正整数，n的二进制表示中恰有1995个l，求证：2n-1995整除n! 例8. (1982年英国数学奥林匹克试题) 设自然数n为17的倍数，且在二进制写法中恰有三个数码为1.证明n的二进制写法中至少有六个数码为0，且若恰有7个数码为0，则n是偶数。 例9. （第12届IM O 试题） 设a ，b ，n 均大于1．在a 进制中， .,010211x x x A x x x A n n n n n n ----== 在b 进制中， .,010211x x x B x x x B n n n n n n ----== 其中 .0,01=/=/-n n x x 证明：当且仅当a>b 时， n n n n B B A A 1 1--< 例10．已知利用的砝码可以使重量是连续自然数的63个重物平衡，求这组砝码． 例11.（2005年中国奥林匹克协作体夏令营试题）如果一个正整数n 在三进制下表示的各数字之和可以被3整除，那么我们称n 为“好的”，则前2005个“好的”正整数之和是多少？ 解：首先考虑“好的”非负整数，考察如下两个引理： 引理1.在3个连续非负整数23,13,3++n n n （n 是非负整数）中，有且仅有1个是“好的”。 证明：在这三个非负整数的三进制表示中，0,1，2各在最后一位出现一次，其作各位数字相同，于是三个数各位数字之和是三个连续的正整数，其中有且仅有一个能被3整除（即“好的”），引理1得证。 引理2.在9个连续非负整数89,19,9++n n n （n 是非负整数）中，有且仅有3个是“好的”。把这3个“好的”非负整数化成三进制，0,1，2恰好在这三个三进制数的最后一位各出现一次。 证明：由引理1不难得知在9个连续非负整数89,19,9++n n n （n 是非负整数）中，有且仅有3个是“好的”。 另一方面，在这三个“好的”非负整数的三进制表示中，最高位与倒数第三位完全相同，倒数第二位分别取0,1，2。若它使它们成为“好的”非负整数，则最后一位不相同，引理2得证。 将所有“好的”非负整数按从小到大的顺序排成一列，设第2004个“好的”非负整数为m ，根据引理1，得3200432003?<≤?m ，即60126009<≤m 。 设前m 个“好的”正整数之和为m S ，由于前2003个“好的”正整数之和等于前2004个“好的”非负整数之和。因此602302220043)2003210(2003=+?+++= S ； 又因为310)22020201()6013(=和310)22020210()6015(=都是“好的”正整数。因此前2005年“好的”正整数之和是： 60350601560132003 2005=++=S S 。 例12. 把所有3的方幂及互不相等的3的方幂的和排列成一个递增数列：10,12，13，… 求这个数列的第100项． 例13. （第12届IM O 试题）设a ，b ，n 均大于1．在a 进制中， .,010211x x x A x x x A n n n n n n ----== 在b 进制中， .,010211x x x B x x x B n n n n n n ----== 其中 .0,01=/=/-n n x x 证明：当且仅当a>b 时，n n n n B B A A 1 1--< 课外练习题 1.（2005年全国高中数学联赛试题） 记集合}6,5,4,3,2,1,0{=T ，? ?????=∈+++=4,3,2,1,777744 33221i T a a a a a M i ，将M 中的元素按从大到小顺序排列，则第2005个数是 A. 43273 767575+++ B. 43272767575+++ C. 43274 707171+++ D. 4327 3707171+++ 2. 证明：对任何k k z k ,6,≥∈进制数k )123454321(是完全平方数． 3. 设V ，W ，X ，Y ，Z 为5个五进制数码．五进制下的三个三位(VYZ)5，(VYX)5，（VVW ）5以公差为1依次递增．问在十进制中,三位数(XYZ)5等于多少？ 4. 设,222199721n a a a +++= 其中n a a a ,,,21 是互不相等的非负整数，求 n a a a +++ 21的值． 5. 设1987可以写在b 进制三位数,)(b xyz 且+=++1z y x ,789++试确定所有可能的x,y,z 及b 值． 6. 求使12-n 能被7整除的所有正整数n ． 7. 若二进制数2011)(a a a a n m m -=满足=-2011)(a a a a m m ,)(2110m m a a a a - 则称n 为“二进制回文数”，问在不超过1988的正整数中有多少个“二进制回文数”？ 8. 对每个正整数,,n k 令)(n s k 为n 在k 进制中的数字和，求证：对于小于20000的素数p ，)(31P s 中至多有两个值为合数． 9. 设00,b a 是正整数，定义数列 ,,,210a a a 和 ,,,210b b b 如下： .,2,1,0,2],2 [11 ===++k b b a a k k k k 若p 是使得1=P a 的数，求证：对所有使得j a 是奇数的j b 的和等于?00b a 10. 设集合,2,1},8,,2,1,0{|9 9 9 9{ 4 43 32 21=∈+ + +=i a a a a a A i ),4,3 把A 中各数按照从大到小的顺序排列，求第1997个数． m为正整数，定义f(m)为m! 中因数2的个数（即满足2k|m!的最大整数k）。证明有无穷多个正整数m，满足m-f(m)=1989 初等数论练习题一 一、填空题 1、τ(2420)=27；?(2420)=_880_ 2、设a ，n 是大于1的整数，若a n -1是质数，则a=_2. 3、模9的绝对最小完全剩余系是_{-4，-3，-2，-1，0，1，2，3，4}. 4、同余方程9x+12≡0(mod 37)的解是x ≡11(mod 37)。 5、不定方程18x-23y=100的通解是x=900+23t ，y=700+18t t ∈Z 。. 6、分母是正整数m 的既约真分数的个数为_?(m )_。 7 8、??? ??10365 =-1。 9、若p 是素数，则同余方程x p - 1 ≡1(mod p )的解数为二、计算题 1、解同余方程：3x 2+11x -20≡0 (mod 105)。 解：因105 = 3?5?7， 同余方程3x 2+11x -20≡0 (mod 3)的解为x ≡1 (mod 3)， 同余方程3x 2+11x -38 ≡0 (mod 5)的解为x ≡0，3 (mod 5)， 同余方程3x 2+11x -20≡0 (mod 7)的解为x ≡2，6 (mod 7)， 故原同余方程有4解。 作同余方程组：x ≡b 1 (mod 3)，x ≡b 2 (mod 5)，x ≡b 3 (mod 7)， 其中b 1 = 1，b 2 = 0，3，b 3 = 2，6， 由孙子定理得原同余方程的解为x ≡13，55，58，100 (mod 105)。 2、判断同余方程x 2≡42(mod 107)是否有解？ 11074217 271071107713231071107311072107 710731072107732107422110721721107213)(=∴-=-=-==-=-=-==??≡-?--?-）（）（）（）（），（）（）（）（），（）（））（）（（ ）（解： 故同余方程x 2≡42(mod 107)有解。 3、求（127156+34）28除以111的最小非负余数。 高中数学竞赛中数论问题的常用方法 数论是研究数的性质的一门科学,它与中学数学教育有密切的联系.数论问题解法灵活,题型丰富,它是中学数学竞赛试题的源泉之一.下面介绍数论试题的常用方法. 1.基本原理 为了使用方便,我们将数论中的一些概念和结论摘录如下: 我们用),...,,(21n a a a 表示整数1a ,2a ,…,n a 的最大公约数.用[1a ,2a ,…,n a ]表示1a ,2a ,…,n a 的 最小公倍数.对于实数x ,用[x ]表示不超过x 的最大整数,用{x }=x -[x ]表示x 的小数部分.对于整数 b a ,,若)(|b a m -,,1≥m 则称b a ,关于模m 同余,记为)(mod m b a ≡.对于正整数m ,用)(m ?表示 {1,2,…,m }中与m 互质的整数的个数,并称)(m ?为欧拉函数.对于正整数m ,若整数m r r r ,...,,21中任何两个数对模m 均不同余,则称{m r r r ,...,,21}为模m 的一个完全剩余系；若整数)(21,...,,m r r r ?中每一个数都与m 互质,且其中任何两个数关于模m 不同余,则称{)(21,...,,m r r r ?}为模m 的简化剩余系. 定理1 设b a ,的最大公约数为d ,则存在整数y x ,,使得yb xa d +=. 定理2(1)若)(mod m b a i i ≡,1=i ,2,…,n ,)(m od 21m x x =,则 1 1n i i i a x =∑≡2 1 n i i i b x =∑； (2)若)(mod m b a ≡,),(b a d =,m d |,则 )(mod d m d b d a ≡； (3)若b a ≡,),(b a d =,且1),(=m d ,则)(mod m d b d a ≡； (4)若b a ≡(i m mod ),n i ,...,2,1=,M=[n m m m ,...,,21],则b a ≡(M mod ). 定理3(1)1][][1+<≤<-x x x x ； (2)][][][y x y x +≥+； (3)设p 为素数,则在!n 质因数分解中,p 的指数为 ∑≥1 k k p n . 定理4 (1)若{m r r r ,...,,21}是模m 的完全剩余系,1),(=m a ,则{b ar b ar b ar m +++,...,,21}也是模 m 的完全剩余系； (2)若{)(21,...,,m r r r ?}是模m 的简化剩余系,1),(=m a ,则{)(21...,,m ar ar ar ?}是模m 的简化剩余系. 定理5(1)若1),(=n m ,则)()()(n m mn ???=. (2)若n 的标准分解式为k k p p p n ααα (2) 121=,其中k ααα,...,21为正整数,k p p p ,...,21为互不相 初中数学竞赛讲座之数论初步(一) 整数的整除性 定义：设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 ∴ 8|b 73 ? b ＝6 且 9|a ＋6＋7＋3＋6 即9|22＋a ∴ a ＝5 3.设n 为自然数，A ＝3237n －632n －855n ＋235n ， 1 浙江省2018年4月高等教育自学考试 初等数论试题 课程代码：10021 一、单项选择题(本大题共5小题，每小题2分，共10分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．20被-30除的余数是（ ） A ．-20 B ．-10 C ．10 D ．20 2．176至545的正整数中，13的倍数的个数是（ ） A ．27 B ．28 C ．29 D ．30 3．200!中末尾相继的0的个数是（ ） A ．49 B ．50 C ．51 D ．52 4．从以下满足规定要求的整数中，能选取出模20的简化剩余系的是（ ） A ．2的倍数 B ．3的倍数 C ．4的倍数 D ．5的倍数 5．设n 是正整数，下列选项为既约分数的是（ ） A ． 3144 21++n n B ． 121 -+n n C ．2 512+-n n D ．1 31++n n 二、填空题(本大题共10小题，每小题3分，共30分) 请在每小题的空格中填上正确答案。错填、不填均无分。 1．d(120)=___________。 2．314162被163除的余数是___________。 3．欧拉定理是___________。 4．同余方程3x ≡5(mod13)的解是___________。 5．不定方程10x-8y=12的通解是___________。 2 6．ο ___________)1847 365 ( = 7．［-π］＝___________。 8．为使n-1与3n 的最大公因数达到最大的可能值，则整数n 应满足条件___________。 9．如果一个正整数具有21个正因数，问这个正整数最小是___________。 10．同余方程x 3+x 2-x-1≡0(mod 3)的解是___________。 三、计算题(本大题共4小题，每小题10分，共40分) 1．解同余方程组 ???? ?? ?≡≡≡≡) 9(mod 4)7(mod 32)4(mod 23) 25(mod 1x x x x 2．解不定方程15x+10y+6z=19。 3．试求出所有正整数n ，使得2n -1能被7整除。 4．判断同余方程 x 2≡-1457(mod 2389) 是否有解？ 四、证明题(本大题共2小题，每小题10分，共20分) 1．证明形如4n+3的素数有无穷多个。 2．证明不定方程 x 2+y 2+z 2=x 2y 2 没有正整数解。 穷举用技巧 【例1】 N是一个各位数字互不相等的自然数，它能被它的每个数字整除。N的最大值是。 【例2】 如果连续N个自然数，每个自然数的数字和都不是11的倍数，则称这连续的N个自然数为一条“龙”，n为这条龙的长度。比如1，2，3，…，28就是一条龙，它的长度是28。问：龙的长度最长可以为多少？写出一条最长的龙。 【例3】 黑板上写有1、2、3、……、100这100个自然数，甲、乙二人轮流每次每人划去一个数，直到剩下两个数为止。如剩下的两数互质则判甲胜，否则判乙胜。 ⑴乙先划甲后划，谁有必胜策略？必胜策略是怎样的？ ⑵甲先划乙后划，谁有必胜策略？必胜策略是怎样的？ 【例4】 如果一个自然数的2004倍恰有2004个约数，这个自然数自己最少有多少个约数？ 测试题 【例1】求所有能被30整除，且恰有30个不同约数的自然数。 【例2】在1到100中，恰好有6个约数的数有多少个？ 答案： 【例1】【分析】 由于30235=??，从质数的观点看整除，如果自然数N 能被30整除，那么自然数N 至少含有三个质因数2，3，5。设：312235r r r N =???。自然数N 恰有30个不同的因数，根据约数的个数公式：12311130235r r r +?+?+?==??（）（）（）。注意 到235??是三个约数之积，由此可知自然数N 中质因数的个数恰好有3个。因此 123111235r r r +?+?+=??（）（）（），由此可知123r r r （，，）必是 124（， ， ）的一个排列。 综上所述，所求的自然数有：24235??，42235??，24235??，42235??，42235??，24235??。 【例2】【分析】 6只能表示为()51+或()()1121++，所以恰好有6个约数的数要么能表示成某个质数的5次方，要么表示为某个质数的平方再乘以另一个质数，100以内符合前者的只有32，符合后者的数枚举如下： 222222222222222232527211213217219223 8323537311 45253 2721???????????????种种种种 所以符合条件的自然数一共有1842116++++=(种)。 全国2018年4月高等教育自学考试 数论初步试题 课程代码：00418 一、单项选择题（本大题共30小题，每小题1分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.m,n为整数，下列式子一定不成立的是（） A.4m-1=4n+1 B.2m+1=4n+3 C.2m+3=4n-1 D.2m=4n 2.下列关于自然数m,n的说法，错误的是（） A.若m|n，则[m,n]=n B.若[m,n]=(m,n)，则m=n C.若m|n,则(m,n)=m D.若(m,n)=1,则[m,n]=1 3.若2|8a-4b+3c，则下列不一定成立的是（） A.2|3a+2c B.2|2a+c C.2|3c-2b D.2|6a-2b+c 4.m,n为整数，若m-n为奇数，则m与n（） A.同奇 B.同偶 C.同奇或同偶 D.一奇一偶 5.若b|a,c|b,则一定有（） A.a|c B.a|b C.b|a+c D.c|a+b 6.若m为完全数，则m的全部正约数之和为（） A.m B.m2 C.2m D.m-1 7.已知a 3689218既能被3整除，又能被5整除，则a的值是（） A.0 B.2 C.5 D.6 8.p为质数，正整数a,b满足a2=pb2，则（） A.a,b必为质数 B.a为合数，b为质数 C.a,b均为合数 D.a,b均不存在 9.设m为大于1的正整数，则]2 [2+ +的值是（） 9 m 5 m A.3m-1 B.3m C.3m+1 D.3m+2 10.下列数中标准分解式为a b b a 的数是（ ） A.512 B.72 C.81 D.30 11.2018年2月8日是星期日，则500天后的那一天是（ ） A.星期三 B.星期二 C.星期四 D.星期五 12.若2p -1是质数，则2p-1(2p -1)是（ ） A.梅森数 B.费马数 C.完全数 D.亲和数 13.满足10n ≡1(mod17)的最小正整数n 是（ ） A.17 B.7 C.16 D.8 14.分母为10的所有既约真分数的个数是（ ） A.4 B.5 C.8 D.9 15.下列命题不一定成立的是（ ） A.若a ≡b(modm),c 为整数，则ac=bc(modm) B.若a ≡b(modm),c ≡d(modm)，则ac ≡bd(modm) C.若a ≡b(modm),c ≡d(modm)，则ab=cd(modm) D.若a ≡b(modm),n 为自然数，则a n ≡b n (modm) 16.同余式组???≡≡)6(mod 3x ) 5(mod 1x 的解是（ ） A.x ≡21（mod5） B.x ≡21（mod6） C.x ≡21（mod30） D.x ≡1（mod30） 17.不大于15且与15互素的所有正整数之和为（ ） A.52 B.59 C.46 D.60 18.已知n 为自然数，m 为正实数，且n ≤m ，下列结论不一定正确的是（ ） A.[n+m]=n+[m] B.n ≤[m] C.[-(n+m)]=-[n+m] D.[nm]≥n[m] 19.30！的标准分解式中，3的最高幂指数是（ ） A.13 B.14 C.15 D.16 初等数论试卷一 一、 单项选择题：（1分/题×20题=20分） １．设x 为实数，[]x 为x 的整数部分，则( ) Ａ．[][]1x x x ≤<+； Ｂ．[][]1x x x <≤+； Ｃ．[][]1x x x ≤≤+； Ｄ．[][]1x x x <<+． ２．下列命题中不正确的是( ) Ａ．整数12,,,n a a a 的公因数中最大的称为最大公因数； Ｂ．整数12,, ,n a a a 的公倍数中最小的称为最小公倍数 Ｃ．整数a 与它的绝对值有相同的倍数 Ｄ．整数a 与它的绝对值有相同的约数 ３．设二元一次不定方程ax by c +=（其中,,a b c 是整数，且,a b 不全为零）有一整数解 ()00,,,x y d a b =，则此方程的一切解可表为( ) Ａ．00,,0,1,2,;a b x x t y y t t d d =- =+ =±± Ｂ．00,,0,1,2, ;a b x x t y y t t d d =+= -=±± Ｃ．00,,0,1,2, ;b a x x t y y t t d d =+= -=±± Ｄ．00,,0,1,2, ;b a x x t y y t t d d =-= -=±± ４．下列各组数中不构成勾股数的是( ) Ａ．５，１２，１３； Ｂ．７，２４，２５； Ｃ．３，４，５； Ｄ．８，１６，１７ ５．下列推导中不正确的是( ) Ａ．()()()11221212mod ,mod mod ;a b m a b m a a b b m ≡≡?+≡+ Ｂ．()()()11221212mod ,mod mod ;a b m a b m a a bb m ≡≡?≡ Ｃ．()()111212mod mod ;a b m a a b a m ≡?≡ Ｄ．()()112 2 11mod mod .a b m a b m ≡?≡ ６．模１０的一个简化剩余系是( ) Ａ．0,1,2, ,9; Ｂ．1,2,3,,10; 初中奥数：数论问题位值原理的解题技巧 1、一个两位数，其十位与个位上的数字交换以后，所得的两位数 比原来小27，则满足条件的两位数共有______个. 【解析】：11+12+13+14+15+16+17=98.若中心圈内的数用a表示，因三条线的总和中每个数字出现一次，只有a多用3两次，所以98+2a 应是3的倍数，a=11，12，…，17代到98+2a中去试，得到a=11，14，17时，98+2a是3的倍数. (1)当a=11时98+2a=120，120÷3=40 (2)当a=14时98+2a=126，126÷3=42 (3)当a=17时98+2a=132，132÷3=44 相对应的解见上图. 2、一个三位数，它等于抹去它的首位数字之后剩下的两位数的4倍于25之差，求这个数。 解答：设它百位数字为a,十位数字为b,个位数字为c 则100a+10b+c=4(10b+c) 化简得5(20a-6b+5)=3c 因为c为正整数,所以20a-6b+5是3的倍数 又因为0≤c≤9 所以0≤3c/5≤5.4 所以0≤20a-6b+5=3c/5≤5.4 所以3c/5=3 即c=5 所以20-6b+5=3 化简得3b-1=10a 按照同样的分析方法,3b-1是10的倍数,解得b=7 最后再算出10a=3*7-1=20 则a=2 所以答案为275。 3、a、b、c是1——9中的三个不同数码，用它们组成的六个没有重复数字的三位数之和是(a+b+c)的多少倍? 解答：组成六个数之和为： 10a+b+10a+c+10b+a+10b+c+10c+a+10c+b =22a+22b+22c =22(a+b+c) 很显然，是22倍 4、有2个3位数，它们的和是999，如果把较大的数放在较小数的左边，所成的数正好等于把较小数放在较大数左边所成数的6倍，那么这2数相差多少呢? 解答：abc+def=999，abcdef=6defabc，根据位值原 理,1000abc+def=6000def+6abc 化简得994abc=5999def，两边同时除以7得142abc=857def，所以abc=857，def=142 所以857-142=715 5、将一个三位数的数字重新排列，在所得到的三位数中，用的减去最小的，正好等于原来的三位数，求原来的三位数。 《数论》第一章补充例题 整除性理论是初等数论的基础.本章要介绍带余数除法,辗转相除法,最大公约数,最小公倍数,算术基本定理以及它们的一些应用. 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是合数. 《初等数论》期末练习二 一、单项选择题 1、=),0(b （ ）. A b B b - C b D 0 2、如果1),(=b a ，则),(b a ab +=（ ）. A a B b C 1 D b a + 3、小于30的素数的个数（ ）. A 10 B 9 C 8 D 7 4、如果)(mod m b a ≡,c 是任意整数,则 A )(mod m bc ac ≡ B b a = C (mod )ac bc m ≡/ D b a ≠ 5、不定方程210231525=+y x （ ）. A 有解 B 无解 C 有正数解 D 有负数解 6、整数5874192能被( )整除. A 3 B 3与9 C 9 D 3或9 7、如果a b ，b a ，则( ). A b a = B b a -= C b a ≥ D b a ±= 8、公因数是最大公因数的（ ）. A 因数 B 倍数 C 相等 D 不确定 9、大于20且小于40的素数有（ ）. A 4个 B 5个 C 2个 D 3个 10、模7的最小非负完全剩余系是( ). A -3，-2,-1,0,1,2，3 B -6，-5,-4,-3,-2,-1 C 1,2,3,4,5，6 D 0,1,2,3,4，5，6 11、因为( ),所以不定方程71512=+y x 没有解. A [12，15]不整除7 B （12，15）不整除7 C 7不整除（12，15） D 7不整除[12，15] 12、同余式)593(mod 4382≡x （ ）. A 有解 B 无解 C 无法确定 D 有无限个解 二、填空题 1、有理数 b a ，0,(,)1a b a b <<=，能写成循环小数的条件是（ ）. 2、同余式)45(mod 01512≡+x 有解，而且解的个数为( ). 3、不大于545而为13的倍数的正整数的个数为( ). 4、设n 是一正整数，Euler 函数)(n ?表示所有( )n ，而且与n （ ）的正整数的个数. 5、设b a ,整数，则),(b a （ ）=ab . 6、一个整数能被3整除的充分必要条件是它的（ ）数码的和能被3整除. 7、+=][x x （ ）. 8、同余式)321(mod 75111≡x 有解,而且解的个数( ). 9、在176与545之间有( )是17的倍数. 数学竞赛讲座 数论的方法技巧(上) 数论是研究整数性质的一个数学分支,它历史悠久,而且有着强大的生命力。数论问题叙述简明,“很多数论问题可以从经验中归纳出来,并且仅用三言两语就能向一个行外人解释清楚,但要证明它却远非易事”。因而有人说:“用以发现天才,在初等数学中再也没有比数论更好的课程了。任何学生,如能把当今任何一本数论教材中的习题做出,就应当受到鼓励,并劝他将来从事数学方面的工作。”所以在国内外各级各类的数学竞赛中,数论问题总是占有相当大的比重。 小学数学竞赛中的数论问题,常常涉及整数的整除性、带余除法、奇数与偶数、质数与合数、约数与倍数、整数的分解与分拆。主要的结论有: 1.带余除法:若a,b是两个整数,b>0,则存在两个整数q,r,使得abq+r(0≤r 4.约数个数定理:设n的标准分解式为(1),则它的正约数个数为: d(n)(a1+1)(a2+1)…(ak+1)。 5.整数集的离散性:n与n+1之间不再有其他整数。因此,不等式x 小学数学《数论初步》练习题 1.计算：（1）[24，315]=________；(1188，726)=________； （2）[364，198，429]=________；(3213，6732)=________； 2.64的约数共有_________个；所有约数的总和是________； 3.七个连续自然数的和能分别被1、2、3、4、5、6、7整除，求出满足此条件的最小的一组数，其中最 小的那个数为________； 4.工厂里的某道工序由甲、乙、丙三人负责，已知甲每5分钟生产18个零件，乙每7分钟生产12个零 件，丙每11分钟生产30个零件，今天早上8:00它们同时开始做第一个零件，那么到________点________分________秒时三个人又一次同时开始做下一个零件；（假设他们做零件的速度均匀，且中途不休息） 5.一个数能被42整除，且恰好有42个约数，那么符合条件的情况共有________种； 6.两个数的最大公约数是12，最小公倍数是2520，且两数之差为12，那么两数之和是________； 7.“1949?2007”的计算结果除以13的余数为________； 8.“20082008+20072007”计算结果的个位数字是________，除以3的余数是________； 9.已知1×2×3×…×n＋4等于两个相邻自然数的乘积，则n ________； 10.小于2000又与2000互质的数有800个，这800个数相加的和是________； 11.某自然数除以9余7，除以13余1，除以19余17，那么此数最小值是________； 12.（1）83、167、377被某个正整数M除时，余数相同，那么M的最大值是________； （2）83、167、377被某个正整数N除时，余数相加和为57，那么N的最大值是_______； 第一章整除理论 整除性理论是初等数论的基础。本章要介绍带余数除法，辗转相除法，最大公约数，最小公倍数，算术基本定理以及它们的一些应用。 第一节数的整除性 定义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。 初等数论考试试卷 一、 单项选择题：（1分/题×20题=20分） 1．设x 为实数，[]x 为x 的整数部分，则( A ) Ａ．[][]1x x x ≤<+； Ｂ．[][]1x x x <≤+； Ｃ．[][]1x x x ≤≤+； Ｄ．[][]1x x x <<+． 2．下列命题中不正确的是( B ) Ａ．整数12,, ,n a a a 的公因数中最大的称为最大公因数； < Ｂ．整数12,,,n a a a 的公倍数中最小的称为最小公倍数 【有最小的吗】 Ｃ．整数a 与它的绝对值有相同的倍数 Ｄ．整数a 与它的绝对值有相同的约数 3．设二元一次不定方程ax by c +=（其中,,a b c 是整数，且,a b 不全为零）有一整数解 ()00,,,x y d a b =，则此方程的一切解可表为( C ) Ａ．00,,0,1,2,;a b x x t y y t t d d =- =+=±± Ｂ．00,,0,1,2, ;a b x x t y y t t d d =+=-=±± Ｃ．00,,0,1,2, ;b a x x t y y t t d d =+=-=±± Ｄ．00,,0,1,2, ;b a x x t y y t t d d =-=-=±± （ 4．下列各组数中不构成勾股数的是( D ) Ａ．5，12，13； Ｂ．7，24，25； Ｃ．3，4，5； Ｄ．8，16，17 5．下列推导中不正确的是( D ) Ａ．()()()11221212mod ,mod mod ;a b m a b m a a b b m ≡≡?+≡+ Ｂ．()()()11221212mod ,mod mod ;a b m a b m a a bb m ≡≡?≡ Ｃ．()()111212mod mod ;a b m a a b a m ≡?≡ 整数的p 进位制及其应用 基础知识 给定一个m 位的正整数A ，其各位上的数字分别记为021,,,a a a m m ，则此数可以简记为：021a a a A m m （其中01 m a ）。 由于我们所研究的整数通常是十进制的，因此A 可以表示成10的1 m 次多项 式 ， 即 12211101010a a a a A m m m m ，其中 1,,2,1},9,,2,1,0{ m i a i 且01 m a ，像这种10的多项式表示的数常常简 记为10021)(a a a A m m 。在我们的日常生活中，通常将下标10省略不写，并且连括号也不用，记作021a a a A m m ，以后我们所讲述的数字，若没有指明记数式的基，我们都认为它是十进制的数字。为了具备一般性，我们给出正整数A 的p 进制表示： 012211a p a p a p a A m m m m ，其中1,,2,1},1,,2,1,0{ m i p a i 且 01 m a 。而m 仍然为十进制数字，简记为p m m a a a A )(021 。 典例分析 例1．(2007年中国数学奥林匹克协作体竞赛试题)假定正整数N 的8进制表示为 8)43211234567765( N ，那么下面四个判断中，正确的是（ ） A 、N 能被7整除而不能被9整除 B 、N 能被9整除而不能被7整除 C 、N 不能被7整除也不能被9整除 D 、N 既能被7整除也能被9整除 答 D 由于)7(mod 18 ，所以)7(m od 18 i k i k i i i i k k a a a a a a N 0 8011)7(mod 8 即N 能被7整除 N 的8进制表示下各位数字之和能被7整除。 类似的，N 能被9整除 N 的8进制表示下奇数位数字之和与偶数位数字之和的差能被9整除 第一章 §1 1 证明：n a a a ,,21 都是m 的倍数。 ∴存在n 个整数n p p p ,,21使 n n n m p a m p a m p a ===,,,222111 又n q q q ,,,21 是任意n 个整数 m p q p q q p a q a q a q n n n n )(22112211+++=+++∴ 即n n a q a q a q +++ 2211是m 的整数 2 证： )12)(1()12)(1(-+++=++n n n n n n n )1()1()2)(1(+-+++=n n n n n n )1()1/(6),2)(1(/6+-++n n n n n n )1()1()2)(1(/6+-+++∴n n n n n n 从而可知 )12)(1(/6++n n n 3 证： b a , 不全为0 ∴在整数集合{}Z y x by ax S ∈+=,|中存在正整数，因而 有形如by ax +的最小整数00by ax + Z y x ∈?,，由带余除法有00000,)(by ax r r q by ax by ax +<≤++=+ 则 S b q y y a q x x r ∈-+-=)()(00，由00by ax +是S 中的最小整数知0=r by ax by ax ++∴/00 下证8P 第二题 by ax by ax ++/00 （y x ,为任意整数） b by ax a by ax /,/0000++∴ ).,/(00b a by ax +∴ 又有b b a a b a /),(,/),( 00/),(by ax b a +∴ 故),(00b a by ax =+ 4 证：作序列 ,2 3, ,2 , 0,2 ,,2 3,b b b b b b - -- 则a 必在此序列的某两项之间 初一数学竞赛培训讲座数论的方法技巧（上） 数论是研究整数性质的一个数学分支，它历史悠久，而且有着强大的生命力.数论问题叙述简明，“很多数论问题可以从经验中归纳出来，并且仅用三言两语就能向一个行外人解释清楚，但要证明它却远非易事”.因而有人说：“用以发现天才，在初等数学中再也没有比数论更好的课程了.任何学生，如能把当今任何一本数论教材中的习题做出，就应当受到鼓励，并劝他将来从事数学方面的工作.”所以在国内外各级各类的数学竞赛中，数论问题总是占有相当大的 比重. 小学数学竞赛中的数论问题，常常涉及整数的整除性、带余除法、奇数与偶数、质数与合数、约数与倍数、整数的分解与分拆.主要的结论有： 1．带余除法：若a，b是两个整数，b＞0，则存在两个整数q，r，使得a=bq+r（0≤r＜b），且q，r 是唯一的.特别地，如果r=0，那么a=bq.这时，a被b整除，记作b|a，也称b是a的约数，a是b的倍数. 2．若a|c，b|c，且a，b互质，则ab|c. 3．唯一分解定理：每一个大于1的自然数N都可以写成质数的连乘积， 即 (1，其中p1＜p2＜…＜p k为质数，a1，a2，…，a k为自然数，并且这种表示是唯一的.（1）式称为N的质因数分解或标准分解. 4．约数个数定理：设n的标准分解式为（1），则它的正约数个数为： d（n）=（a1+1）（a2+1）…（a k+1）. 5．整数集的离散性：n与n+1之间不再有其他整数.因此，不等式x＜y与x≤y-1是等价的. 下面，我们将按解数论题的方法技巧来分类讲解. 一、利用整数的各种表示法 对于某些研究整数本身的特性的问题，若能合理地选择整数的表示形式，则常常有助于问题的解决.这些常用的形式有： 1．十进制表示形式：n=a n10n +a n-110 n-1 +…+a0； 2019年自考公共课数论初步章节讲义 【同余】 一、主要内容 同余的定义、性质、剩余类和完全剩余系、欧拉函数、简化剩余系、欧拉定理、费尔马小定理、循环小数、特殊数2，3，4，5，6，7，8，9，11，13的整除规律 二、基本要求 通过本章的学习，能够掌握同余的定义和性质，区别符号：三和 =之间的差异。能利用同余的一些基本性质实行一些计算，深刻理解完 全剩余系，简化剩余系的定义、性质及构造。能判断一组数是否构成 模m的一个完全剩余系或一个简化剩余系。能计算欧拉函数的值，掌 握欧拉定理、费尔马小定理的内容以及证明方法。能应用这二个定理 证明相关的整除问题和求余数问题。能实行循环小数与分数的互化。 三、难点和重点 (1)同余的概念及基本性质 (2)完全剩余系和简化剩余系的构造、判别 (3)欧拉函数计算、欧拉定理、费尔马小定理的证明及应用 (4)循环小数与分数的互化 (5)特殊数的整除规律。 四、自学指导 同余理论是初等数论中最核心的内容之一，由同余定义可知，若 a≡b(mod m)，则a和b被m除后有相同的余数。这里m为正整数，一 般要求m大于1，称为模，同余这个思想本质上是将整数按模m分类，然后讨论每一个类中整数所具有的共性及不同类之间的差异。第一章 中用带余除法定理将整数分类解决一些问题的方法只不过是同余理论 中的一个特殊例子。从同余的定理上看，同余和整除实际上是同一回事，故同余还有二个等价的定义：①用整除来定义即m∣a-b 。②用 等号来定义a=b+mt 。值得注意a和b关于m同余是个相对概念。即它是相对于模m来讲，二个整数a和b关于一个整数模m同余。则对于 另一个整数模m ，a和b未必会同余。 从定义上看，同余和整除是同一个事情，但引进了新的符号三后，无论从问题的叙述上，还是解决问题的方法上都有了显著的变化，同 时也带来了一些新的知识和方法。在引进了同余的代数性质和自身性 质后，同余符号三和等号=相比，在形式上有几乎一致的性质，这便于 我们记忆。事实上在所有等号成立的运算中，只有除法运算是个例外，即除法的消去律不成立。为此对于同余的除法运算我们有二种除法： (i)模不改变的除法，若ak≡bk(mod m) ，(k,m)=1，则 a≡b(mod m) (ii)模改变的除法, 若ak≡bk(mod m) (k,m)=d,则a≡b 这个点读者要特别注意。 完全剩余系和简化剩余系是二个全新的概念，读者只要搞清引成 这些概念的过程。因为同余关系是一个等价关系，利用等价关系能够 实行将全体整数实行分类，弄清来胧去脉，对于更深刻理解其本质是 很有好处的。完全剩余系或简化剩余系是一个以整数为元素的集合， 在每个剩余类各取一个数组成的m个不同数的集合，故一组完全剩余 系包含m个整数，因为二个不同的剩余类中的数关于m两两不同余， 故可得判别一组数是否为模m的一个完全剩余系的条件有二条为 (1) 个数=m (2) 关于m两两不同余 数论问题的常用方法 数论是研究数的性质的一门科学，它与中学数学教育有密切的联系。数论问题解法灵活，题型丰富，它是中学数学竞赛试题的源泉之一。下面介绍数论试题的常用方法. 1.基本原理 为了使用方便，我们将数论中的一些概念和结论摘录如下： 我们用),...,,(21n a a a 表示n 个整数1a ,2a ,…,n a 的最大公约数。用[1a ,2a ,…,n a ]表示 1a ,2a ,…,n a 的最小公倍数。对于实数x ，用[x ]表示不超过x 的最大整数，用{x }=x -[x ] 表示x 的小数部分。对于整数b a ,,若)(|b a m -，,1≥m 则称b a ,关于模m 同余，记为 )(mod m b a ≡。对于正整数m ，用)(m ?表示{1，2，…，m }中与m 互质的整数的个数， 并称)(m ?为欧拉函数。对于正整数m ，若整数m r r r ,...,,21中任何两个数对模m 均不同余，则称{m r r r ,...,,21}为模m 的一个完全剩余系；若整数)(21,...,,m r r r ?中每一个数都与m 互质，且其中任何两个数关于模m 不同余，则称{)(21,...,,m r r r ?}为模m 的简化剩余系。 定理1 设b a ,的最大公约数为d ，则存在整数y x ,，使得 yb xa d +=. 定理2 （1）若)(mod m b a i i ≡，1=i ，2，…，n ，)(mod 21m x x =，则 1 1n i i i a x =∑≡2 1 n i i i b x =∑； （2）若)(mod m b a ≡，),(b a d =，m d |，则 )(mod d m d b d a ≡； （3）若)(mod m b a ≡，),(b a d =，且1),(=m d ，则)(mod m d b d a ≡； （4）若b a ≡（i m mod ），n i ,...,2,1=，M=[n m m m ,...,,21]，则b a ≡（M mod ）. 定理3 （1）1][][1+<≤<-x x x x ； （2）][][][y x y x +≥+； （3）设p 为素数，则在!n 质因数分解中，p 的指数为 ∑ ≥1 k k p n .初等数论练习题及答案
高中数学竞赛中数论问题的常用方法
初中数学竞赛讲座之数论初步(一)
4月浙江自考初等数论试题及答案解析试卷及答案解析真题
超难奥数题之数论专题：穷举用技巧
4月全国高等教育自学考试数论初步试题及答案解析
初等数论试卷模拟试题和答案
初中奥数：数论问题位值原理的解题技巧
《数论》第一章补充例题
(完整word版)初等数论练习题一(含答案)
七年级数学竞赛讲座数论的方法与技巧(含答案详解)
小学数学《数论初步》练习题
初等数论 第一章 整除理论
0初等数论试卷及答案
数论的方法和技巧05整数的p进位制及其应用
初等数论第2版习题答案
初一数学竞赛培训讲座 数论的方法技巧(上)
2019年自考公共课数论初步章节讲义
10数论问题的常用方法(教师版)
相关主题
文本预览