初等数论竞赛训练
1.（2006一试6）数码1232006,,,,a a a a 中有奇数个9的2007位十进制数12320062a a a a 的
个数为 ．
2.(2008一试5) 方程组0,
0,
0x y z xyz z xy yz xz y ++=??+=??+++=?
的有理数解(,,)x y z 的个数为 ．
3.（2011一试8）
已知
200200
(1,2,,95)n
n
n
n a C n -=??=，则数列}{n a 中整数项的个
数为 ．
4.（2009二试3）设k ，l 是给定的两个正整数．证明：有无穷多个正整数m k ≥，使得C k m 与
l 互素．
5.（2010二试）设m 和n 是大于1的整数，求证：
11111112(1)().1m m n m
m
m
k k j
j m m k j i n n C n C i m -+===??+++=+-??+??
∑∑∑
6.（2011二试2）证明：对任意整数4≥n ，存在一个n 次多项式
0111)(a x a x a x x f n n n ++++=--
具有如下性质：（1）110,,,-n a a a 均为正整数；（2）对任意正整数m ，及任意)2(≥k k 个互不相同的正整数k r r r ,,,21 ，均有)()()()(21k r f r f r f m f ≠．
7.（2012二试2）试证明：集合{
}2
2,2,
,2,
n A =满足
（1）对每个a A ∈，及b N *
∈，若21b a <-，则(1)b b +一定不是2a 的倍数；
（2） 对每个a A ∈（其中A 表示A 在Ｎ 中的补集），且1a ≠，必存在b N *
∈，
21b a <-，使(1)b b +是2a 的倍数．
8.（2013二试2）给定正整数,u v .数列{}n a 定义如下：1a u v =+，对整数1m ≥， 221,
.
m m m m a a u a a v +=+??
=+?
记12m m S a a a =+++（1,2,
m =）.证明：数列{}n S 中有无穷多项是完全平方数.
初等数论参考答案
4.【解析】证法一：对任意正整数t ，令(!)m k t l k =+??．我们证明()
C 1k m l =，
． 设p 是l 的任一素因子，只要证明：p ／∣C k m ．
若p ／∣k !，则由1
!C ()k
k m i k m k i ==-+∏1
[((!)]k
i i tl k =≡+∏1
k
i i =≡∏ ()
1
!mod k p
α+≡． 及|!p k α，且p
α+1
／∣k !，知|!C k m p k α且1
α+p ／∣!C k m k ．从而p ／∣C k m ．
证法二：对任意正整数t ，令2(!)m k t l k =+??，我们证明()
C 1k m l =，
． 设p 是l 的任一素因子，只要证明：p ／∣C k m ． 若p ／∣k !，则由 1
!C ()==-+∏k
k
m
i k m k i 2
1
[((!)]k
i i tl k =≡+∏ 1
k
i i =≡∏ ()!mod k p ≡．
即p 不整除上式，故p ／∣C k m ．
若|!p k ，设1α≥使|!p k α，但1!p k α+?
．12|(!)p k α+．故由 1
1
!C ()k k
m
i k m k i -==-+∏ 2
1
[((!)]k
i i tl k =≡+∏ 1
k
i i =≡∏()
1!mod k p α+≡,及|!p k α，且p
α+1
／∣
k !，知|!C k m p k α且1
α+p ／∣!C k m k ．从而p ／∣C k m
5. 证明：1
1
1
1)
m m j
j m j q C
q +++=+=∑由（得到1
1
1
(1)
,m
m m j j
m j q q
C q +++=+-=∑ 1,2,
,q n =分别将代入上式得：
1
10
21,m
m j
m j C ++=-=∑
1
1
1
03
2
2,
m
m m j
j
m j C
+++=-=∑1
1
10
(1)
(1),m
m m j j
m j n
n C n +++=--=-∑ 1
1
10
(1)
.m
m m j j
m j n n
C n +++=+-=∑ n 将上面个等式两边分别相加得到：1
1
01
(1)
1(),m
n
m j
j m j i n C
i ++==+-=∑∑
11
1
1
1
(1)(1)1(1),m n
n
m
j j m
m j i i n n n C
i m i -+===++-=+++∑
∑∑（）
11111112(1)().1m m n
m m
m
k k j j m m k j i n n C n C i m -+===??++
+=+-??+??∑∑∑
7.【解析】证明:对任意的a A ∈,设2,,k a k N *=∈则122,k a +=如果b 是任意一个小于
21a -的正整数,则121b a +≤-
由于b 与1b +中,一个为奇数,它不含素因子2,另一个是偶数,它含素因子2的幂的次数最多为k ,因此(1)b b +一定不是2a 的倍数；
若a A ∈,且1,a ≠设2,k a m =?其中k 为非负整数,m 为大于1的奇数,
则1
22k a m +=?
下面给出(2)的三种证明方法:
证法一:令1,12,k b mx b y +=+=消去b 得12 1.k y mx +-=
由于1
(2,)1,k m +=这方程必有整数解;1
002k x x t y y mt +?=+??=+??
其中00,(,)t z x y ∈为方程的特解.
把最小的正整数解记为(,),x y **则12k x *+<,故21,b mx a *
=<-使(1)b b +是2a 的倍数．
证法二:由于1
(2
,)1,k m +=由中国剩余定理知,同余方程组
10(mod 2)1(mod )
k x x m m +?=?
=-?在区间1
(0,2)k m +上有解,x b =即存在21,b a <-使(1)b b +是2a 的倍数．
不定方程 不定方程是指未知数的个数多于方程的个数，且未知数的取值范围是受某些限制（如整数、正整数或有理数）的方程.不定方程是数论的一个重要课题，也是一个非常困难和复杂的课题. 1．几类不定方程 （1）一次不定方程 在不定方程和不定方程组中，最简单的不定方程是整系数方程 )0,0(,0≠>=++b a c by ax 通常称之为二元一次不定方程.一次不定方程解的情况有如下 定理. 定理一：二元一次不定方程c b a c by ax ,,,=+为整数.有整数解的充分必要条件是c b a |),(. 定理二：若00,,1),(y x b a 且=为①之一解，则方程①全部解为at y y bt x x -=+=00,. （t 为整数）。 （2）沛尔)(pell 方程 形如12 2 =-dy x （*d N ∈，d 不是完全平方数）的方程称为沛尔方程. 能够证明它一定有无穷多组正整数解；又设),(11y x 为该方程的正整数解),(y x 中使d y x +最小的 解，则其的全部正整数解由111111111[()()]2)()] n n n n n n x x x y x x ?=+-?? ??=-?? （1,2,3, n =）给 出. ①只要有解),(11y x ，就可以由通解公式给出方程的无穷多组解. ②n n y x , 满足的关系：1(n n x y x y +=+；112 11222n n n n n n x x x x y x y y ----=-?? =-? ， （3）勾股方程2 2 2 z y x =+ 这里只讨论勾股方程的正整数解，只需讨论满足1),(=y x 的解，此时易知z y x ,,实际上两两互素. 这种z y x ,,两两互素的正整数解),,(z y x 称为方程的本原解，也称为本原的勾股数。容易看出y x ,一奇一偶，无妨设y 为偶数，下面的结果勾股方程的全部本原解通解公式。 定理三：方程2 2 2 z y x =+满足1),(=y x ，2|y 的全部正整数解),,(z y x 可表为 2222,2,b a z ab y b a x +==-=，其中，b a ,是满足b a b a ,,0>>一奇一偶，且
《竞赛数学中的初等数论》 贾广素编著 2006-8-21
序 言 数论是竞赛数学中最重要的一部分，特别是在1991年，IMO 在中国举行，国际上戏称那一年为数论年，因为6道IMO 试题中有5道与数论有关。 数论的魅力在于它可以适合小孩到老头，只要有算术基础的人均可以研究数论――在前几年还盛传广东的一位农民数学爱好者证明了哥德巴赫猜想，当然，这一谣言最终被澄清了。可是这也说明了最难的数论问题，适合于任何人去研究。 初等数论最基础的理论在于整除，由它可以演化出许多数论定理。做数论题，其实只要整除理论即可，然而要很快地解决数论问题，则要我们多见识，以及学习大量的解题技巧。这里我们介绍一下数论中必需的一个内容：对于N r q N b a ∈?∈?,,,，满足r bq a +=，其中b r <≤0。 除了在题目上选择我们努力做到精挑细选，在内容的安排上我们也尽量做到讲解详尽，明白。相信通过对本书学习，您可以对数论有一个大致的了解。希望我们共同学习，相互交流，在学习交流中，共同提高。 编者：贾广素 2006-8-21于山东济宁
第一节 整数的p 进位制及其应用 正整数有无穷多个，为了用有限个数字符号表示出无限多个正整数，人们发明了进位制， 这是一种位值记数法。进位制的创立体现了有限与无限的对立统一关系，近几年来，国内与 国际竞赛中关于“整数的进位制”有较多的体现，比如处理数字问题、处理整除问题及处理 数列问题等等。在本节，我们着重介绍进位制及其广泛的应用。 基础知识 给定一个m 位的正整数A ，其各位上的数字分别记为021,,,a a a m m --，则此数可以简记为：021a a a A m m --=（其中01≠-m a ）。 由于我们所研究的整数通常是十进制的，因此A 可以表示成10的1-m 次多项式，即 012211101010a 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 --=，以后我们 所讲述的数字，若没有指明记数式的基，我们都认为它是十进制的数字。但是随着计算机的 普及，整数的表示除了用十进制外，还常常用二进制、八进制甚至十六进制来表示。特别是 现代社会人们越来越显示出对二进制的兴趣，究其原因，主要是二进制只使用0与1这两种 数学符号，可以分别表示两种对立状态、或对立的性质、或对立的判断，所以二进制除了是 一种记数方法以外，它还是一种十分有效的数学工具，可以用来解决许多数学问题。 为了具备一般性，我们给出正整数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．将一个十进制数字2004（若没有指明，我们也认为是十进制的数字）转化成二进制与 八进制，并将其表示成多项式形式。 分析与解答 分析：用2作为除数（若化为p 进位制就以p 作为除数），除2004商1002，余数为0；再 用2作为除数，除1002商501余数为0；如此继续下去，起到商为0为止。所得的各次余 数按从左到右的顺序排列出来，便得到所化出的二进位制的数。 解：
1 4 7 10 13 … 4 9 14 19 24 … 7 14 21 28 35 … 10 19 28 37 46 … … … … … … … 定理2：不定方程x 2+y 2=z 2满足（x ，y ）=1，x ，y ，z ＞0，2|x 的全部整数解可表示为 x=2ab ，y=a 2－b 2，z=a 2+b 2。其中a ＞b ＞0，a 、b 一奇一偶，（a ，b ）=1为任意整数。 四、例题与练习 1、右表的结构为：第一行是以1为首项，3为 公差的无穷等差数列；第一列中的数与第一行 中的数对应相等；第n （n ≥2）行是公差为2n+1 的无穷等差数列。证明：⑴若N 在表中，则2N+7 不是素数；⑵若N 不在表中，则2N+7是素数。 2、证明：若正整数x 、y 使得2xy | x 2+y 2－x ，则x 是完全平方数。 3、证明：存在一个1997的整倍数，它不超过11位，且各位数字不含2，3，4，5，6，7。 4、设c 为奇自然数，且存在自然数a ≤ 13-c ，使（2a －1）2+8c 为平方数，求证：c 为合数。 5、求最大的正整数x ，使得对任意y ∈N ，有x|（1127-+y y ） 6、证明：方程3 25y x =+无整数解。 7、求方程235=-y x 的全部整数解。 8、给数集M={1，2，…，n －1}（n ≥3）中的数染色，满足⑴i 与n －i 同色；⑵有一个k ∈M ，（k ，n ）=1，使得当i ≠k 时i 与|k －i|同色，求证：M 中有一色。
9、在一个圆周上标记了4个整数，规定一个方向，使每个整数都有相邻的下一个数，每一步操作是指对每一个数，同时用该数与下一个数之差来替换，即对于a 、b 、c 、d 依次用a －b 、b －c 、c －d 、d －a 来替换。问经过1996步这样的替换之后，是否可以得到4个数a 、b 、c 、d ，使得|bc －ad|、|ac －bd|、|ab －cd|都是素数。（IMO －37预选题） 10、求所有大于3的自然数n ，使得1+321n n n C C C ++整除20002（CMO － 1998） 11、有多少个正整数对x 、y ，x ≤y ，使得（x ，y ）=5！和[x ，y]=50！成立？（1997年加拿大） 12、设w （n ）表示自然数n 的素因数的个数，n ＞1。证明：存在无穷多个n ，使得w （n ）＜w （n+1）＜w （n+2）。 13、求最小的整数n （n ≥4），满足从任意n 个不同的整数中能选出四个不同的数a 、b 、c 、d ，使a+b －c －d 可以被20整数。 14、求所有实数对（a ，b ），使对所有的正整数n 满足a[bn]=b[an]，其中[x]表示不超过x 的最大整数。（IMO －39预选题）
初等数论中的几个重要定理 基础知识 定义（欧拉(Euler)函数）一组数称为是模的既约剩余系，如果对任意的，且对于任意的，若＝1，则有且仅有一个是对模 的剩余，即。并定义中和互质的数的个数， 称为欧拉（Euler）函数。 这是数论中的非常重要的一个函数，显然，而对于，就是1,2，…，中与互素的数的个数，比如说是素数，则有。 引理：；可用容斥定理来证（证明略）。 定理1：（欧拉（Euler）定理）设＝1，则。 分析与解答：要证，我们得设法找出个相乘，由个数我们想到中与互质的的个数：，由于＝1，从而 也是与互质的个数，且两两余数不一样，故 （），而（）＝1，故。 证明：取模的一个既约剩余系，考虑，由于与互质，故仍与互质，且有，于是对每个都能找到唯一的一个，使得，这种对应关系 是一一的，从而，。
，，故。证毕。 这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。 定理2：（费尔马（Fermat）小定理）对于质数及任意整数有。 设为质数，若是的倍数，则。若不是的倍数，则 由引理及欧拉定理得，，由此即得。 定理推论：设为质数，是与互质的任一整数，则。 定理3：（威尔逊（Wilson）定理）设为质数，则。 分析与解答：受欧拉定理的影响，我们也找个数，然后来对应乘法。 证明：对于，在中，必然有一个数除以余1，这是因为则好是的一个剩余系去0。 从而对，使得； 若，，则，，故对于，有。即对于不同的对应于不同的，即中数可两两配对，其积除以余1，然后有，使，即与它自己配对，这时，，或，或。 除外，别的数可两两配对，积除以余1。故。
定义：设为整系数多项式（），我们把含有的一组同余式 （）称为同余方组程。特别地，，当均为的一次整系数多项式时，该同余方程组称为一次同余方程组.若整数同时满足： ，则剩余类（其中）称为同余方程组的一个解，写作 定理4：（中国剩余定理）设是两两互素的正整数，那么对于任意整数，一次同余方程组，必有解，且解可以写为： 这里，，以及满足，（即为对模的逆）。 中国定理的作用在于它能断言所说的同余式组当模两两互素时一定有解，而对于解的形式并不重要。 定理5：（拉格郎日定理）设是质数，是非负整数，多项式 是一个模为次的整系数多项式（即），则同余方程至多有个解（在模有意义的情况下）。 定理6：若为对模的阶，为某一正整数，满足，则必为的倍数。 以上介绍的只是一些系统的知识、方法，经常在解决数论问题中起着突破难点的作用。另外还有一些小的技巧则是在解决、思考问题中起着排除情况、辅助分析等作用，有时也会起到
第20章 同 余 20.1.1★(1)证明：任意平方数除以4，余数为0或1； (2)证明：任意平方数除以8，余数为0、1或4． 解析 (1)因为 奇数()2 22214411(mod 4)k k k =+=++≡， 偶数()222240(mod4)k k ==≡， 所以，正整数21(mod 4),;0(mod 4),.n n n ?≡??奇偶为数为数 (2)奇数可以表示为21k +，从而 奇数()22441411k k k k =++=++． 因为两个连续整数k 、1k +中必有一个是偶数，所以()41k k +是8的倍数，从而 奇数()2811mod8i =+≡． 又，偶数()2 2224k k ==(k 为整数)． 若k =偶数2t =，则()224160mod 8k t ==． 若k =奇数21t =+，则 ()()2 2244211644(mod8)k t t t =+=++≡． 所以，平方数()()()0mod8,1mod8,4mod8. ??≡??? 评注 事实上，我们也可以这样来证：因为对任意整数a ，有0a ≡，±1，2(mod4)，所以，0a ≡，1(mod4)；又a ≡0，±1，±2，±3，4(mod8)，所以，2a ≡0，1，()4mod8． 20.1.2★求证：一个十进制数被9除所得的余数，等于它的各位数字被9除所得的余数． 解析 设这个十进制数1210n n A a a a a a -=． 因10≡1(mod9)，故对任何整数k ≥1，有 ()1011mod9k k ≡=． 因此 1210n n A a a a a a -= 1110101010n n n n a a a a --=?+?++?+ ()110mod9n n a a a a -≡++ ++．
第21章 不定方程 §21.1 二元一次不定方程 21.1.1★求不定方程2x y -=的正整数解． 解析 因为312-=，422-=，532-=，…，所以这个方程的正整数解有无数组，它们是 2, ,x n y n =+?? =? 其中n 可以取一切正整数． 21.1.2★求11157x y +=的整数解． 解析1 将方程变形得 71511 y x -= ． 因为x 是整数，所以715y -应是11的倍数．由观察得02x =，01y =-是这个方程的一组整数解， 所以方程的解为 215, 111,x t y t =-?? =-+? t 为整数． 解析2 先考察11151x y +=，通过观察易得 ()()1141531?-+?=， 所以 ()()114715377?-?+??=， 可取028x =-，0 21y =．从而 2815, 2111,x t y t =--?? =+? t 为整数． 评注 如果a 、b 是互质的整数，c 是整数，且方程 ax by c += ① 有一组整数解0x 、0y ．则此方程的一切整数解可以表示为 00, ,x x bt y y at =-?? =+? 其中0t =，±1，±2，±3，…． 21.1.3★求方程62290x y +=的非负整数解． 解析 因为(6，22)=2，所以方程两边同除以2得 31145x y +=． ① 由观察知，14x =，11y =-是方程 3111x y += ② 的一组整数解，从而方程①的一组整数解为
()00 454180, 45145,x y =?=??? =?-=-?? 所以方程①的一切整数解为 18011, 453.x t y t =-?? =-+? 因为要求的原方程的非负整数解，所以必有 180110,4530.t t -?? -+? ≥③ ≥④ 由于t 是整数，由③、④得15≤t ≤16，所以只有t =15，t =16两种可能． 当t =15时，x =15，0y =；当t =16时，x =4，y = 3．所以原方程的非负整数解是 15,0, x y =?? =?4, 3.x y =??=? 21.1.4★求方程719213x y +=的所有正整数解． 解析 这个方程的系数较大，用观察法去求其特殊解比较困难，碰到这种情况我们可用逐步缩小系数 的方法使系数变小，最后再用观察法求解． 用方程 719213x y +=① 的最小系数7除方程①的各项，并移项得 213193530277 y y x y --= =-+ ．② 因为x 、y 是整数，故 357 y u -=也是整数，于是有573y u +=．再用5除此式的两边得 373255 u u y u --= =-+ ．③ 令 325 u v -= (整数)，由此得 253u v +=．④ 由观察知1u =-，1v =是方程④的一组解．将1u =-代入③得2y =．2y =代入②得x =25．于 是方程①有一组解025x =，02y =，所以它的一切解为 2519, 27.x t y t =-?? =+? 0,1,2,t =±± 由于要求方程的正整数解，所以 25190, 270.t t ->?? +>? 解不等式，得t 只能取0，1．因此得原方程的正整数解为 25,2, x y =?? =?6, 9.x y =??=?
第22章[]x与{}x 求1-的值． 解析因为 1200712006 +， 又 =<， 所以200612007 <． 故12006 =． 若n是正整数，求的值． 解析因为3321 n n n n <+++ ()3 32 3311 n n n n <+++=+， 所以1 n n <=+， 所以n =． 数1232008 A=????的末尾有多少个连续的零? 解析A的质因数分解式中，5的最高次方幂为 40080163499 =+++=， 所以1232008 A=????的末尾有499个零． 评注在() !12 n n =???中，质数p的最高次幂是 () 2 ! m n n n p n p p p ?????? =+++ ?????? ?????? ， 其中m p n ≤，且1m p n +>． 设 222 111 1 232007 S=++++，求[]S． 解析要求[]S，只需证明S介于两个连续的整数之间．所以需要对S进行适当的变形，通过放大、缩小 的手段求出S的范围，从而确定[]S的取值． 由题设知，1 S>．考虑到 () 2 1111 11 k k k k k <=- -- ，k=2，3，4，…，2007，可以得到
1222007 =-<， 所以[]1S =． 评注 上述解题过程中，首先对S 进行了“放缩”，又通过“拆项”的方法使和式中前后两项能够相互抵消一部分，使和式化简，从而得到了S 的范围． 在对和式取整时，利用和式本身的性质进行“缩放”的方法非常重要，需要在平时的学习中多积累一 些和式的性质以及变形技巧． 计算和式 的值． 解析 因为（23，101）=1，所以，当1,2,,100n =时，23101n 都不是整数，即23101n ?????? 都不为零．又因为 ()2310123101101 n n -+ =23， 而()231012302101101n n -????<+
数学竞赛筑阶系列讲座——初等数论之二 讲解人：凌 彬 姓名__________ 专题二：奇数与偶数 一、基本知识 奇数的特征：它被2除得的余数是1；即任何奇数都是21n +的形式，其中n Z ∈． 偶数的特征：它被2除得的余数是0；即任何偶数都是2n 的形式，其中n Z ∈． 奇数与偶数的一个最明显的性质是：任何奇数决不会与一个偶数相等． 奇数与偶数还有几条运算性质： 1．奇数与奇数的和是偶数；2．奇数与偶数的和是奇数；3．偶数与偶数的和是偶数； 4．奇数与奇数的积是奇数；5．奇数与偶数的积是偶数；6．偶数与偶数的积是偶数． 几个常用的结论： 1．两个连续整数的积(1)n n +是偶数； 2．整数a 的幂n a 与a 奇偶性相同； 3．整数a 和b 有“a b ±”与“n n a b ±”的奇偶性相同． 这些性质都是很平凡的，但灵活地应用它们却能解决许多问题，包括看上去“无从下手”的问题；下面给出的一些例子，解答除了应用奇偶性之外，还包含了一些非常有用的解题思想；利用奇偶性解题的方法叫奇偶性分析法．这个方法是数学竞赛中特别活跃的方法之一． 二、例题选讲 例1．证明：不存在整数x 、y 满足：221990y x =+． 例22 例3．证明：不存在这样的整数a 、b 、c 、d ，使得abcd a -、abcd b -、abcd c -、abcd d - 都是奇数．
例4．证明：改变一个自然数各位数码的顺序后得到的数，与原数之和不能等于1989 99 9． 例5．设129, , , a a a 是正整数，任意改变这九个数顺序后记为129, , , b b b ； 证明：112299()()()A a b a b a b =---是偶数． 例6．平面上有15个点，任意三点都不在一条直线上，试问：能不能从每个点都引三条线段， 且仅引三条线段和其余的某三点相连？证明你的结论． 例7．已知一奇数β，使得整系数二次三项式2ax bx c ++的值2a b c ββ++也是奇数，其中c 是 奇数；求证：方程20ax bx c ++=没有奇数根． 例8．圆周上有1989个点，给每一个点染两次颜色：或红、蓝，或全红，或全蓝；最后统计知； 染红色1989次，染蓝色1989次．试证：至少有一点被染上红、蓝两种颜色． 例9．黑板上写着三个整数，任意擦去其中的一个，将它改写成为其它两数的和减去1；这样继 续下去，最后得到19，2007，2009，问原来的三个数能否是2，2，2．
初等数论中的几个重要定理(竞赛必备)
初等数论中的几个重要定理 基础知识 定义（欧拉(Euler)函数）一组数称为是模的既约剩余系，如果对任意的，且对于任意的，若＝1，则有且仅有一个是对模的剩余，即。并定义 中和互质的数的个数，称为欧拉（Euler）函数。 这是数论中的非常重要的一个函数，显然 ，而对于，就是1,2，…，中与互素的数的个数，比如说是素数，则有。 引理：；可用容斥定理来证（证明略）。 定理1：（欧拉（Euler）定理）设＝1，则。
分析与解答：要证，我们得设法找出个相乘，由个数我们想到中与互质的的个数：，由于＝1，从而也是与互质的个数，且两两余数不一样，故 （），而（）＝1，故。 证明：取模的一个既约剩余系 ，考虑，由于与互质，故仍与互质，且有，于是对每个都能找到唯一的一个，使得，这种对应关系是一一的，从而 ，。 ，，故。证毕。 这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。
定理2：（费尔马（Fermat）小定理）对于质数及任意整数有。 设为质数，若是的倍数，则。若不是的倍数，则由引理及欧拉定理得 ，，由此即得。 定理推论：设为质数，是与互质的任一整数，则。 定理3：（威尔逊（Wilson）定理）设为质数，则。 分析与解答：受欧拉定理的影响，我们也找个数，然后来对应乘法。 证明：对于，在中，必然有一个数除以余1，这是因为则好是的一个剩余系去0。 从而对，使得 ；
若，，则， ，故对于，有。即对于不同的对应于不同的，即中数可两两配对，其积除以余1，然后有，使，即与它自己配对，这时， ，或，或。 除外，别的数可两两配对，积除以余1。故。 定义：设为整系数多项式（），我们把含有的一组同余式（）称为同余方组程。特别地，，当均为的一次整系数多项式时，该同余方程组称为一次同余方程组.若整数同时满足： ，则剩余类（其中 ）称为同余方程组的一个解，写作 定理4：（中国剩余定理）设是两两互素的正整数，那么对于任意整数，一次
初等数论简介 绪言：在各种数学竞赛中大量出现数论题，题目的内容几乎涉及到初等数论的所有专题。 1． 请看下面的例子： （1） 证明：对于同样的整数x 和y ，表达式2x+3y 和9x+5y 能同时被整除。(1894年首届匈牙利 数学竞赛第一题) （2） ①设n Z ∈，证明213 1n -是168的倍数。 ②具有什么性质的自然数n ，能使123n ++++能整除123n ???？（1956年上海首届数学竞赛第一题） （3） 证明：3 231 122 n n n ++-对于任何正整数n 都是整数，且用3除时余2。（1956年北京、天津市首届数学竞赛第一题） （4） 证明：对任何自然数n ，分数214 143 n n ++不可约简。（1956年首届国际数学奥林匹克竞赛第一题） （5） 令(,, ,)a b g 和[,, ,]a b g 分别表示正整数,, ,a b g 的最大公因数和最小公倍数，试证： [][][][]()()()() 2 2 ,,,,,,,,,,a b c a b c a b b c c a a b b c c a =??（1972年美国首届奥林匹克数学竞赛第一题） 这些例子说明历来数论题在命题者心目中首当其冲。 2.再看以下统计数字： （1）世界上历史最悠久的匈牙利数学竞赛，从1894~1974年的222个试题中，数论题有41题，占18.5%。 （2）世界上规模最大、规格最高的IMO （国际数学奥林匹克竞赛）的前20届120道试题中有数论13题，占10.8% 。 这说明：数论题在命题者心目中总是占有一定的分量。如果将有一定“数论味”的计数型题目统计在内，那么比例还会高很多。 3.请看近年来国内外重大竞赛中出现的数论题： (1)方程3 2 3 652x x x y y ++=-+的整数解(,)x y 的个数是（ ） A 、 0 B 、1 C 、3 D 、无穷多 （2007全国初中联赛5） （2）已知,a b 都是正整数，试问关于x 的方程()2 1 02 x abx a b -+ +=是否有两个整数解？ 如果有，请把它们求出来；如果没有，请给出证明。 （2007全国初中联赛12） （3）①是否存在正整数,m n ，使得(2)(1)m m n n +=+？ ②设(3)k k ≥是给定的正整数，是否存在正整数,m n ，使得()(1)m m k n n +=+？ （2007全国初中联赛14）
第一节 整数的p 进位制及其应用 正整数有无穷多个，为了用有限个数字符号表示出无限多个正整数，人们发明了进位制，这是一种位值记数法。进位制的创立体现了有限与无限的对立统一关系，近几年来，国内与国际竞赛中关于“整数的进位制”有较多的体现，比如处理数字问题、处理整除问题及处理数列问题等等。在本节，我们着重介绍进位制及其广泛的应用。 基础知识 给定一个m 位的正整数A ，其各位上的数字分别记为 021,,,a a a m m --，则此数可以简记为：021a a a A m m --=（其中01≠-m a ）。 由于我们所研究的整数通常是十进制的，因此A 可以表示成10的1-m 次多项式，即012211101010a 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 --=，以后我们所讲述的数字，若没有指明记数式的基，我们都认为它是十进制的数字。但是随着计算机的普及，整数的表示除了用十进制外，还常常用二进制、八进制甚至十六进制来表示。特别是现代社会人们越来越显示出对二进制的兴趣，究其原因，主要是二进制只使用0与1这两种数学符号，可以分别表示两种对立状态、或对立的性质、或对立的判断，所以二进制除了是一种记数方法以外，它还是一种十分有效的数学工具，可以用来解决许多数学问题。 为了具备一般性，我们给出正整数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） 基础知识 整数的性质有很多，这里我们着重讨论整数的整除性、整数的奇偶性，质数与合数、完全平方数及整数的尾数等几个方面的应用。 1．整除的概念及其性质 在高中数学竞赛中如果不加特殊说明，我们所涉及的数都是整数，所采用的字母也表示整数。 定义：设b a ,是给定的数，0≠b ，若存在整数c ，使得bc a =则称b 整除a ，记作a b |，并称b 是a 的一个约数(因子)，称a 是b 的一个倍数，如果不存在上述c ，则称b 不能整除a 记作b a 。 由整除的定义，容易推出以下性质： (1)若c b |且a c |，则a b |(传递性质)； (2)若a b |且c b |，则)(|c a b ±即为某一整数倍数的整数之集关于加、减运算封闭。若反复运用这一性质，易知a b |及c b |，则对于任意的整数v u ,有)(|cv au b ±。更一般，若n a a a ,,,21 都是 b 的倍数，则)(|21n a a a b +++ 。或着i b a |，则∑=n i i i b c a 1|其中n i Z c i ,,2,1, =∈； (3)若a b |，则或者0=a ，或者||||b a ≥，因此若a b |且b a |，则b a ±=； (4)b a ,互质，若c b c a |,|，则c ab |；
利用数学实验提高竞赛数学的趣味性 1.问题的提出 竞赛数学，俗称奥数，是我国数学教育的传统强项，无论是普及程度还是竞赛水平都位居世界前列，我国选在历届参赛的国际数学奥林匹克竞赛（IMO）中，都有优异的表现。但是，近年来受功利主义的驱动，“奥数”出现了泛化的趋势，连小学数学竞赛都被冠以“奥数”的头衔，出现了“全民奥数”的不正常现象，引起许多人对奥数的批判和反思。批评者认为：奥数并不教给学生科学研究的方法，而只是一味追求偏、难、怪的解题技巧，舍弃了数学最核心，也是最有用的数学思想方法；还有人对我国获得IMO奖牌的选手进行了追踪调查，发现“这些公认的数学尖子基本上没有在数学研究上做出突出成就的，甚至鲜有喜欢数学的”，由此认为奥数一无是处，更有甚者宣称“奥数已成公害，对学生危害堪比黄、赌、毒”。 与我国相比，国外的奥数则显得非常冷清。比如日本，虽然奥数教育也很成功，但日本只有6%作用的中小学生有过奥数学习的经历，或者正在学习奥数。美国也类似，中小学生对数学感兴趣的不多，但对数学感兴趣的人，则会非常投入。这些学生由于兴趣支撑，发展后劲很大。对于这一点，我国奥数教育家熊斌老师在谈对国内外IMO选手的对比时也感慨的说：“相对国内的IMO选手而言，国外选手尽管也有相当强的竞争意识，但在日常积累的过程中操练的成分更少一些。而且，相对而言，他们将数学抽象思维与生活场景结合的能力更强。” 其实奥数的教育价值早已经被世界各国教育界肯定，所谓IMO奖牌获得者后来的成就普遍不大，在世界范围内根本就不成立。之所以出现前面所述的种种弊端，主要是因为我们大多用一种急功近利的心态去对待奥数，教师都大多采用“超前学习知识，枯燥题海训练”的应试教育模式进行教学，使学生对奥数甚至数学产生了恐惧和厌烦，即使少数同学能坚持学下去，也多数是为了获得升学加分或保送的奖励。这也正是国内的IMO获奖选手一旦升入大学就很少选择数学专业的主要原因。丘成桐先生一针见血的指出：“国外奥数考得好的学生，往往能够成才，而我们的学生不一定能成才，因为国内是机械性的学数学，不是出于兴趣。” 基于以上分析，我们非常有必要探讨如何提高奥数学习的趣味性，使其真正
第19章 整数的整除性 综上可知，命题成立． 评注如果两个互质的正整数之积是一个完全平方数，则这两个正整数都是完全平方数．这一命题是我们证明此题的出发点． 19．4．27★★★如果正整数a 、b 、c 满足222c a b =+． 证明：数2c ab +和2c ab -都可以表示为两个正整数的平方和． 解析 巧妙运用下述命题：如果正整数x 可表示为两个正整数的平方和，则2x 也可表示为两个整数的平方和．事实上，设22x u v =+，这里x 、u 、v 都是正整数．则 ()()2 2 22222x u v u v u v =+=++-．于是，2x 可表示为两个整数u v +和u v -的平方和，命 题获证． 注意到，由条件有 ()()2 2222222c ab c a ab b c a b ±=+±+=+±． 利用已证命题，可知 ()()()2 2 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 都是偶数，从而2 2 2 22x 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 ≡，所以()3315mod8m n a =++≡，故此时a 不是完全平方数． 综上所述，对于任意正整数m 、n ，正整数331m n a =++都不是完全平方数． 评注 判断一个数不是完全平方数，我们也可以用“模”的方法，例如，我们知道，偶数的平方是4的倍数，奇数的平方除以4余1，所以，若一个整数同余2或者3模4，则它一
初等数论考试试卷1 一、单项选择题(每题3分，共18分) 1、如果a b ，b a ，则( ). A b a = B b a -= C b a ≤ D b a ±= 2、如果n 3，n 5，则15（ ）n . A 整除 B 不整除 C 等于 D 不一定 3、在整数中正素数的个数（ ）. A 有1个 B 有限多 C 无限多 D 不一定 4、如果)(mod m b a ≡,c 是任意整数,则 A )(mod m bc ac ≡ B b a = C ac T )(mod m bc D b a ≠ 5、如果( ),则不定方程c by ax =+有解. A c b a ),( B ),(b a c C c a D a b a ),( 6、整数5874192能被( )整除. A 3 B 3与9 C 9 D 3或9 二、填空题(每题3分，共18分) 7、素数写成两个平方数和的方法是（ ）. 8、同余式)(mod 0m b ax ≡+有解的充分必要条件是( ). 9、如果b a ,是两个正整数,则不大于a 而为b 的倍数的正整数的个数为( ). 10、如果p 是素数,a 是任意一个整数,则a 被p 整除或者( ). 11、b a ,的公倍数是它们最小公倍数的( ). 12、如果b a ,是两个正整数,则存在( )整数r q ,,使r bq a +=,b r ≤0. 三、计算题(每题8分，共32分) 13、求[136,221,391]=? 14、求解不定方程144219=+y x . 15、解同余式)45(mod 01512≡+x . 16、求? ?? ??563429,其中563是素数. （8分） 四、证明题(第1小题10分，第2小题11分，第3小题11分，共32分)
数学奥赛辅导 第四讲 不定方程 不定方程是指未知数的个数多于方程的个数，且未知数的取值范围是受某些限制（如整数、正整数或有理数）的方程.不定方程是数论的一个重要课题，也是一个非常困难和复杂的课题. 1．几类不定方程 （1）一次不定方程 在不定方程和不定方程组中，最简单的不定方程是整系数方程 )0,0(,0≠>=++b a c by ax ①通常称之为二元一次不定方程.一次不定方程解的情况有 如下定理. 定理一：二元一次不定方程c b a c by ax ,,,=+为整数.有整数解的充分必要条件是c b a |),(. 定理二：若00,,1),(y x b a 且=为①之一解，则方程①全部解为at y y bt x x -=+=00,. （t 为整数）。 （2）沛尔)(pell 方程 形如122=-dy x （*d N ∈，d 不是完全平方数）的方程称为沛尔方程. 能够证明它一定有无穷多组正整数解；又设),(11y x 为该方程的正整数解),(y x 中使d y x +最小的 解，则其的全部正整数解由111111111[()()]2)()] n n n n n n x x x y x x ?=+?? ??=--?? （1,2,3,n = ）给 出. ①只要有解),(11y x ，就可以由通解公式给出方程的无穷多组解. ②n n y x , 满足的关系：1(n n x y x y +=+；112 11222n n n n n n x x x x y x y y ----=-?? =-? ， （3）勾股方程2 2 2 z y x =+ 这里只讨论勾股方程的正整数解，只需讨论满足1),(=y x 的解，此时易知z y x ,,实际上两两互素. 这种z y x ,,两两互素的正整数解),,(z y x 称为方程的本原解，也称为本原的勾股数。容易看出y x ,一奇一偶，无妨设y 为偶数，下面的结果勾股方程的全部本原解通解公式。 定理三：方程2 22z y x =+满足1),(=y x ，2|y 的全部正整数解),,(z y x 可表为 2222,2,b a z ab y b a x +==-=，其中，b a ,是满足b a b a ,,0>>一奇一偶，且
初等数论竞赛训练 1.（2006一试6）数码1232006,,,,a a a a 中有奇数个9的2007位十进制数12320062a a a a 的 个数为 ． 2.(2008一试5) 方程组0, 0, 0x y z xyz z xy yz xz y ++=??+=??+++=? 的有理数解(,,)x y z 的个数为 ． 3.（2011一试8） 已知 200200 (1,2,,95)n n n n a C n -=??=，则数列}{n a 中整数项的个 数为 ． 4.（2009二试3）设k ，l 是给定的两个正整数．证明：有无穷多个正整数m k ≥，使得C k m 与 l 互素． 5.（2010二试）设m 和n 是大于1的整数，求证： 11111112(1)().1m m n m m m k k j j m m k j i n n C n C i m -+===??+++=+-??+?? ∑∑∑
6.（2011二试2）证明：对任意整数4≥n ，存在一个n 次多项式 0111)(a x a x a x x f n n n ++++=-- 具有如下性质：（1）110,,,-n a a a 均为正整数；（2）对任意正整数m ，及任意)2(≥k k 个互不相同的正整数k r r r ,,,21 ，均有)()()()(21k r f r f r f m f ≠． 7.（2012二试2）试证明：集合{ }2 2,2, ,2, n A =满足 （1）对每个a A ∈，及b N * ∈，若21b a <-，则(1)b b +一定不是2a 的倍数； （2） 对每个a A ∈（其中A 表示A 在Ｎ 中的补集），且1a ≠，必存在b N * ∈， 21b a <-，使(1)b b +是2a 的倍数． 8.（2013二试2）给定正整数,u v .数列{}n a 定义如下：1a u v =+，对整数1m ≥， 221, . m m m m a a u a a v +=+?? =+? 记12m m S a a a =+++（1,2, m =）.证明：数列{}n S 中有无穷多项是完全平方数.
《数学竞赛辅导》 ——初等数论部分 上犹中学刘道生 编辑 数论是竞赛数学中最重要的一部分，特别是在1991年，IMO 在 中国举行，国际上戏称那一年为数论年，因为6道IMO 试题中有5 道与数论有关。 数论的魅力在于它可以适合小孩到老头，只要有算术基础的人均 可以研究数论――在前几年还盛传广东的一位农民数学爱好者证明 了哥德巴赫猜想，当然，这一谣言最终被澄清了。可是这也说明了最 难的数论问题，适合于任何人去研究。 初等数论最基础的理论在于整除，由它可以演化出许多数论定 理。做数论题，其实只要整除理论即可，然而要很快地解决数论问题， 则要我们多见识，以及学习大量的解题技巧。这里我们介绍一下数论 中必需的一个内容：对于N r q N b a ∈?∈?,,,，满足r bq a +=，其中b r <≤0。 除了在题目上选择我们努力做到精挑细选，在内容的安排上我们 也尽量做到讲解详尽，明白。相信通过对本书学习，您可以对数论有 一个大致的了解。希望我们共同学习，相互交流，在学习交流中，共 同提高。 编者：刘道生
2007-8-21于江西赣州 第一节 整数的p 进位制及其应用 正整数有无穷多个，为了用有限个数字符号表示出无限多个正整数，人们发明了进位制， 这是一种位值记数法。进位制的创立体现了有限与无限的对立统一关系，近几年来，国内与 国际竞赛中关于“整数的进位制”有较多的体现，比如处理数字问题、处理整除问题及处理 数列问题等等。在本节，我们着重介绍进位制及其广泛的应用。 基础知识 给定一个m 位的正整数A ，其各位上的数字分别记为021,,,a a a m m --，则此数可以简记为：021a a a A m m --=（其中01≠-m a ）。 由于我们所研究的整数通常是十进制的，因此A 可以表示成10的1-m 次多项式，即 012211101010a 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 --=，以后我们 所讲述的数字，若没有指明记数式的基，我们都认为它是十进制的数字。但是随着计算机的 普及，整数的表示除了用十进制外，还常常用二进制、八进制甚至十六进制来表示。特别是 现代社会人们越来越显示出对二进制的兴趣，究其原因，主要是二进制只使用0与1这两种 数学符号，可以分别表示两种对立状态、或对立的性质、或对立的判断，所以二进制除了是 一种记数方法以外，它还是一种十分有效的数学工具，可以用来解决许多数学问题。 为了具备一般性，我们给出正整数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．将一个十进制数字2004（若没有指明，我们也认为是十进制的数字）转化成二进制与 八进制，并将其表示成多项式形式。 分析与解答 分析：用2作为除数（若化为p 进位制就以p 作为除数），除2004商1002，余数为0；再 用2作为除数，除1002商501余数为0；如此继续下去，起到商为0为止。所得的各次余 数按从左到右的顺序排列出来，便得到所化出的二进位制的数。 解：