初等数论第三章同余
第三章 同 余
§1 同余的概念及其基本性质
。，所有奇数；所有偶数，例如，。
不同余，记作：对模则称；若所得的余数不同，同余，记作：对模则称所得的余数相同，与去除两个整数，称之为模。若用设)2(mod 1)2(mod 0)7(mod 18)(mod ,)(mod ,≡≡≡≡/≡∈+a a m b a m b a m b a m b a b a m m Z 定义1。
故同余关系是等价关系；（传递性），则，、若；（对称性）
，则、若；（反身性）
、：关系，它具有下列性质同余是整数之间的一种)(mod )(mod )(mod 3)(mod )(mod 2)(mod 1m c a m c b m b a m a b m b a m a a ≡≡≡≡≡≡
。
则，，，设。
，，即同余的充分必要条件是对模整数)(|)()(mod ,0)(|,2121212211b a m q q m b a r r m b a m r r r mq b r mq a t mt b a b a m m b a -?-=-?=?≡<≤+=+=∈+=-证明定理1Z
。
，则若；
，则，若)(mod )(mod )2()(mod )(mod )(mod )1(21212211m b c a m c b a m b b a a m b a m b a -≡≡++≡+≡≡性质1
。
，则特别地，若；
，则，若)(mod )(mod )(mod )(mod )(mod 21212211m kb ka m b a m b b a a m b a m b a ≡≡≡≡≡性质2
。
，则，
；特别地，若则
，，，若)(mod ,,2,1,0)(mod )(mod ,,2,1)(mod )(mod 0110111111
111
111m b x b x b a x a x a n i m b a m y y B
x x A
k i m y x m B A n n n n n n n n i i k k i i k
k k
k
k k
k k +++≡+++=≡≡
=≡≡----∑∑ αααααααααααααααα定理2。，则，，，若)(mod )(mod 1),(1111m b a m b a m d d b b d a a ≡≡===性质3
。
的任一公因数，则及是，若；
，则，若)(mod ,)(mod (2))(mod 0)(mod )1(d m d b d a m b a d m b a mk bk ak k m b a ≡≡≡>≡性质4
反之亦然。
。
，则，若]),,,[(mod ,,2,1)(mod 21k i m m m b a k i m b a ≡=≡性质5
。
，则，，若)(mod 0|)(mod d b a d m d m b a ≡>≡性质6 中的另一数。
必能整除之一，则两数及能整除，因而若，则若b a d m b a d m b m a m b a ,,),(),()(mod =≡性质7
。
即个位数码是，
，所以因为。的数，事实上，只需求满足数码。
写成十进位数时的个位求9)10(mod 91)
1()
3(3)10(mod 19390)10(mod 33203
203
2406
2406406≡-≡-≡≡-≡≡≤≤≡a a a 解例1 。
，故为偶数时，当，，故为奇数时，当，
所以，因为
。为偶数时，，当为奇数时，证明：当12|3)3(mod 2111)1(1212|3)3(mod 0111)1(12)3(mod 1)1(12)3(mod 1212|312|3+/≡+≡+-≡++≡+-≡+-≡++-≡+-≡+/+n n n n
n
n
n n n n n n n n 证明例2
同余性质在算术中的一些应用。 一、检查因数的方法
1、一整数能被3（或9）整除的充分必要条件是它的十进位数码之和能被3（或9）整除。
证明 只需讨论正整数即可。任取+∈Z a ，则a 可以写成十进位的形式：
同理可证。
对于。，从而可知，于是，由，9|3|3)3(mod )3(mod 11010010100101011a a a a a a a a a a a a a n n n n i n n n n +++?+++≡≡<≤+++=----
2、设正整数1000010001000011<≤+++=--i n n n n a a a a a ， ，则7（或11或13）|a 的充分必要条件是7（或11或13）|。)()(3120 ++-++a a a a
证明 因为7×11×13=1001。 例3 a =5874192能被3和9整除。
例4 a =435693能被3整除，但不能被9整除。 例5 a =637693能被7整除；a =能被13整除。 二、弃九法（验算整数计算结果的方法）
例6 设a =28997，b =39495，P =ab =15，检查计算是否正确。 解 令 1001010011<≤+++=--i n n n n a a a a a ，
1001010011<≤+++=--j m m m m b b b b b ，
1001010011<≤+++=--k l l l l c c c c P ，
则 )9(mod ))((0
∑∑∑===≡l
k k m j j n i i c b a （*）
若（*）不成立，则P ≠ab ，故在本题中，计算不正确。
注 (1) 若（*）不成立，则计算不正确；但否命题不成立。 (2) 利用同样的方法可以用来验证整数的加、减运算的正确性。
§2 剩余类及完全剩余系
中。
必处于同一，则反之，若。，故，，则设整数中。
只能在的唯一性可知，由的存在性可知于是由，，是任一整数，则必有设同余。的充分必要条件是对模两个整数同在一个集合；仅在上述的一个集合中每个整数必包含在而且质：
，这些集合具有下列性，中，其个集合，记作：，则全体整数可分成设r r r a r a a a r m K b a m b a m b a r mq b r mq a K b a K a r K a r m r r mq a a m m r q r qm K K K K m m a a ,)(mod )(mod ,)2(0)1()2()1(1,,1,0}|{,,,021110≡≡+=+=∈∈<≤+=-=∈+=>-证定理1 Z
的一个完全剩余系。
称为模一剩余类，则中任何两个数都不在同个整数若。
数称为它同类数的剩余中的任一的剩余类，一个剩余类称为模中的定理m a a a a a a m m K K K m m m 1
10110110,,,,,,,,,1--- 定义1 推论 m 个整数作成模m 的一个完全剩余系的充分必要条件是它们对模m 两两不同余。
例如，下列序列都是模m 的完全剩余系： 系）。（绝对最小完全剩余为奇数时，当；；为偶数时，当；；）（最小非负完全剩余系；2
1,,1,0,1,,212
,12,,1,0,1,,12212,,1,0,1,,12,21)4()1()1(,,)1(,,1,0)3()1()1(,,,,1,0)2(1,,2,1,0)1(1----
--+-
--+--
-+-+-+--+-++--m m m m m m m
m m m m m a m m m m m a am m m m a
的完全剩余系。
也是模故，与已知矛盾，，于是又，，则设反证法。两两不同余即可，采用只需证明的完全剩余系。
也是模则的完全剩余系，是模若的一个完全剩余系，即也通过模的一个完全剩余系，则通过模，若，，设m b aa b aa b aa j i m a a m a m aa aa j i m b aa b aa b aa b aa b aa m b aa b aa b aa m a a a m b ax m x b m a m m j i j i j i m m m +++≠≡=≡≠+≡++++++++∈=∈----+110110110110,,,)()(mod 1),()(mod )()(mod ,,,,,,,,,1),( 证定理2Z Z 的完全剩余系。
也通过模，因此，所通过的数两两不同余，这说明，，故又，，数，则通过的完全剩余系中的所分别是，其中设两两不同余。
个整数对模下证这个整数，通过个整数，所以分别通过因为的完全剩余系。
也通过模余系，则的完全剩分别通过模，而，设212112211222211121221211121221221121211221122121212112212121211221212121)(mod ''')(mod '''1),()(mod ''')(mod ''','',','',')(mod '''''',,,,1),(,m m x m x m x m x m m x x m x x m m m x m x m m x m x m x x x x x x m m x m x m x m x m m m m m m m x m x m m m x x m m x m x m m m x x m m m m ++≡≡=≡≡+≡+++=∈+证定理3Z 的完全剩余系。
不是模因此，，矛盾。的完全剩余系，则是模若，从而，
，同理所以的完全剩余系，
都是模及：因为的完全剩余系。
不是模的完全剩余系，则都是模及，设m b a b a m m
b a m b a b a m m
m b a b a m m
b m m m m i a m b b a a m b a b a m b b a a m m m m
i i i m m m
i i m i i m i i i m
i i m
i m
i i m m m m m m ++≡
+++≡+≡
+≡+≡≡+=≡++≡∑∑∑∑∑∑∑=======,,)(mod 2
)(,,)(mod 02
2)()(mod 2)(mod 22)1(,,,,,,,,,,)2(mod 0111
111
1
1
1
11111111 证例1
。，则，，，设类中，至少有两个在同一同余，它们对模个数：考察。，使得组成的数，存在着仅有数字证明：对任何正整数个个个个个a c b n n c b c b c b n n a n a n s s k s k n ==-≡==>+-+
1
1
1
1
1000111)(|)(mod 111111111,,11,11|0,1证：例2 。故
，通过从而剩余系，的一个完全通过模以的一个完全剩余系，所通过模因为。则
的一个完全剩余系，通过模，，，设)1(2
111
01,
,1,0)1(2
1
1),(-=-+
++=????
?
?+-???
???++-=????
??+∈=∈∑∑+m m m m m m b ax m m m m m b ax m b ax m x m m b ax m x b m a m x
x
证
例3Z Z
§3 简化剩余系与欧拉函数
。
是合数，则；若是质数，则若互质的数的个数。
中与函数，它的值等于序列是定义在正整数集上的欧拉函数1)(1)(1,,2,1,0)(-<-=-a a a a a a a a a ???注定义1
的一个简化剩余系。
模成的数的集合称为从每一类各取一数所作互质的全部剩余类中，在与模的剩余类。
互质模互质，则称它为一个与的剩余类中的数与如果一个模m m m m m 定义2
互质。
与模即，，有中任一数，则对于，反之，若有；互质，则与模的全部剩余类，若是模设不同余的整数组成的。
个对模的互质与的每一简化剩余系是由，模互质的剩余类的个数为因此，与模互质。此类中有一数与互质的充分必要条件是的剩余类与模模m K m k k qm k K m k K k m r m K m K K K m m m m m m m m m r r r r r r r r r m 1),'('1),(1),(,,,)()(110=+==∈=- 证定理1??的一个简化剩余系。
是模则不同余，对模互质的整数，并且两两个与是若m a a a m m m a a a m m )(21)(21,,,)(,,,??? 定理2的简化剩余系。
通过模故，与已知矛盾，，则若，可知，个整数，而且由通过余系。
的简化剩也通过模的简化剩余系，则通过模，若m ax j i m x x j i m ax ax m ax m x m a m ax m ax m x m a j i j i )()(mod )()(mod 1),(1),(1),()(1),(≠≡≠≡====?证定理3
的简化剩余系。
也通过模余系，则的简化剩分别通过模，而，设21211221212121,,1),(,m m x m x m m m x x m m m m +=∈+Z 定理4
。
，从而于是，可知另一方面，由，，从而，于是，，可知一方面，由整数。
互质的切与的一个完全剩余系中一通过模化剩余系时，的简模分别通过的完全剩余系。下证当也通过模的完全剩余系，则分别通过模可知，若由上一节定理1),(),(1),(),(1),(),(1),(1),(1),(1),(1),(1),(1),(),(),(,,,,32211221112212211211221211221211221221121122211122122112121211221212121122121=====+=+=+=+=+=+=====++m x m x m x m m x m m x m x m m x m x m m m x m x m m m x m x m m x m x m m x m x m m x m m x m m m m x m x m m m m x m x m m m x x m m x m x m m m x x 证。
个整数。故通过个整数，因此，通过个整数，通过另一方面，由于个整数。
通过的简化剩余系，即通过模的简化剩余系，则分别通过模可知，若由定理。
，则，设)()()()()()()()(,,4)()()(1),(,21212121122211212112212
112212*********m m m m m m x m x m m x m x m m x m x m m m x m x m m m x x m m m m m m m m ???????????=+++==∈+证推论Z 。因此，。
个，故，共有的数为不互质中，与的完全剩余系。在模先证。，则设???
?
??-???? ??-???? ??-=---==-=-=???? ??-???? ??-???? ??-==-------k k k k k k p p p a p p p p p p p p p a p p p p p p p p p p p p p p p p p a a p p p a k k k k 111111)
())(()()()()()(,,2,,,2,1)(111111)(2111
2211121111121212111212
1 ααααααααααααααααααααααα???????证定理5
§4 欧拉定理·费马定理
。
，从而
故，
，又即，
化剩余系，于是
的简
也是模的简化剩余系，则
是模
设
。
，则
，
，
设
)
(mod
1
1
)
,
(
1
)
,
(
)
,
(
)
,
(
)
(mod
)
(
)
(mod
)
(
)
)(
(
,
,
,
,
,
,
)
(mod
1
1
)
,
(
1
)
Euler
(
)
(
)
(
2
1
)
(
2
1
)
(
2
1
)
(
2
1
)
(
)
(
2
1
)
(
2
1
)
(
2
1
)
(
2
1
)
(
m
a
m
r
r r
m
r
m
r
m
r
m
r
r r
r
r r
a
m
r
r r
ar
ar
ar
m
ar
ar
ar
m
r
r
r
m
a
m
a
m
Z
m
m
m
m
m
m
m
m
m
m
m
m
≡
=
=
=
=
≡
≡
≡
=
>
∈
?
?
?
?
?
?
?
?
?
?
?
证
定理1
。
，故
，则
若
。
，从而
可知
，则由定理
若
。
是质数，则
若
定理
)
(mod
|
1
)
,
(
)
(mod
)
(mod
1
1
1
)
,
(
)
(mod
)
Fermat
(
1
p
a
a
a
p
p
a
p
a
a
p
a
p
a
p
a
a
p
p
p
p
p
≡
≠
≡
≡
=
≡
-
证
推论
。
，故
又，
剩余系，于是
的简化
也是模
的简化剩余系，所以
是模
因为。
故
，
，
由费马定理可知
。
故
，
，
由费马定理可知
。
，则
若
；
；
是奇质数，证明：
设
)
(mod
)1
(
2
1
)
(mod
1
2
)
(mod
]
)1
(
2
1[
2
)1
(
2
2
2
2
)1
(
2
1
)1
(2,
,4,2
1
,
,2,1
)3(
)
(mod
2
)1
(
)1
(
2
1
)1
(
2
1
1
,
,2,1
)
(mod
)2(
)
(mod
1
1
1
1
1
)1
(
2
1
1
,
,2,1
)
(mod
1
)1(
)
(mod
)1
(
2
1
)
(mod
1
2
)3(
)
(mod
)1
(
2
1
)2(
)
(mod
1
)1
(
2
1
)1(
1
1
1
1
1
1
1
p
p
p
p
p
p
p
p
p
p
p
p
p
p
p
p
p
i
p
i
i
p
p
p
p
i
p
i
p
p
p
p
p
p
p
p
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
m
p
p
p
p
p
p
p
p
m
m
m
m
p
p
p
p
p
p
≡
-
+
+
+
≡/
-
+
+
+
≡
-
+
+
+
≡
-
+
+
+
-
-
≡
-
≡
-
+
+
+
≡
-
+
+
+
-
=
≡
-
≡
-
≡
+
+
+
≡
-
+
+
+
-
=
≡
≡
-
+
+
+
≡/
≡
-
+
+
+
-
≡
-
+
+
+
-
-
-
-
-
-
-
证
例1
。，故
由费马定理可知，，所以因为。，证明：外的任一质数，与是除设个
个
)1(11)1(9991)10(|)(mod 1)10(1),10(5,2999|52----+=-≡=≠∈p k p k p k k p k p p p p p k p 证例2Z
初等数论 第三章 同余
第三章 同 余 §1 同余的概念及其基本性质 。，所有奇数；所有偶数，例如，。 不同余，记作：对模则称；若所得的余数不同，同余，记作：对模则称所得的余数相同，与去除两个整数，称之为模。若用设)2(mod 1)2(mod 0)7(mod 18)(mod ,)(mod ,≡≡≡≡/≡∈+a a m b a m b a m b a m b a b a m m Z 定义1。 故同余关系是等价关系；（传递性），则，、若；（对称性） ，则、若；（反身性） 、：关系，它具有下列性质同余是整数之间的一种)(mod )(mod )(mod 3)(mod )(mod 2)(mod 1m c a m c b m b a m a b m b a m a a ≡≡≡≡≡≡ 。 则，，，设。 ，，即同余的充分必要条件是对模整数)(|)()(mod ,0)(|,2121212211b a m q q m b a r r m b a m r r r mq b r mq a t mt b a b a m m b a -?-=-?=?≡<≤+=+=∈+=-证明定理1Z 。 ，则若； ，则，若)(mod )(mod )2()(mod )(mod )(mod )1(21212211m b c a m c b a m b b a a m b a m b a -≡≡++≡+≡≡性质1 。 ，则特别地，若； ，则，若)(mod )(mod )(mod )(mod )(mod 21212211m kb ka m b a m b b a a m b a m b a ≡≡≡≡≡性质2 。 ，则， ；特别地，若则 ，，，若)(mod ,,2,1,0)(mod )(mod ,,2,1)(mod )(mod 0110111111 111 111m b x b x b a x a x a n i m b a m y y B x x A k i m y x m B A n n n n n n n n i i k k i i k k k k k k k k +++≡+++=≡≡ =≡≡----∑∑ΛΛΛΛΛΛΛΛΛΛΛΛαααααααααααααααα定理2。，则，，，若)(mod )(mod 1),(1111m b a m b a m d d b b d a a ≡≡===性质3
初等数论 第一章 整除理论
第一章整除理论 整除性理论是初等数论的基础。本章要介绍带余数除法，辗转相除法，最大公约数，最小公倍数，算术基本定理以及它们的一些应用。 第一节数的整除性 定义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 ≡?。 这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。
初等数论
初等数论学习总结 第一章 整除 例题选讲 例1.请写出10个连续正整数都是合数. 解: 11!+2，11!+3，……，11！+11。 例2. 证明连续三个整数中，必有一个被3整除。 证：设三个连续正数为a ，a +1，a +2，而a 只有3k ，3k +1，3k +2三种情况，令a =3k ，显 然成立，a =3k +1时，a +2=3(k+1)，a =3k +2时，a +1=3(k +1)。 例3. 证明lg2是无理数。 证：假设lg2是有理数，则存在二个正整数p ，q ，使得lg2= q p ，由对数定义可得10p =2q ，则有2p ·5p =2q ,则同一个数左边含因子5，右边不含因子5，与算术基本定理矛盾。∴lg2为无理数。 例4. 求(21n+4，14n+3) 解：原式=(21n+4,14n+3)=(7n+1,14n+3)=(7n+1,7n+2)=(7n+1,1)=1 例5. 求2004!末尾零的个数。 解：因为10=2×5，而2比5多， 所以只要考虑2004！中5的幂指数，即 5（2004！）=4995 20045 200412520042520045200454=?? ? ??+?? ? ??+?? ? ??+?? ? ??+?? ? ?? 例6.证明（n !）(n-1)!|(n !)! 证：对任意素数p ,设（n !）(n -1)!中素数p 的指数为α， （n !）!中p 的指数β，则 ∑???? ??-=∞=11k k p n n )!(α，∑??? ? ??-=∞=11k k p n n !)!(β,)()(x n nx ≥ α=∑??? ? ??-=∑???? ?? -≥∑???? ??-=∑???? ??∴∞=∞=∞=∞=1111111k k k k k k k k p n n p n n p n n p n ! )!(!)!()!(! 即α β≥，即左边整除右边。
初等数论作业(3)答案
第三次作业答案： 一、选择题 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 . (参考上题)
初等数论c++
备注：纯手写代码，注释。 数论 1、素数 （1）暴力求解法 根据素数的概念，没有1和其本身没有其他正因数的数。所以只需枚举比这个数小的数，看能整除即可； C++代码： #include
//去掉了偶数的判断，效率提高一倍 /*如果number整除以i，那么会得到两个的因数， 而较小的那个因数不会超过number的二分之一次方； 所以只需判断到number的平方根向上取整即可；*/ if(number%i); else return false; return true; } int main() { int sum; cin>>sum; if(determine(sum)) cout<<"YES!"; else cout<<"NO!"; return 0; } 时间复杂度：o(sqrt(n)/2); 空间复杂度：几乎没有； （2）一般线性筛法： 因为任何一个合数都能分解成几个素数相乘的形式； 所以可以做一个表，首先把2设为质数，然后将2的倍数设为合数，剩下的数就是新得到的质数，然后重复这个过程，直到筛到合
适的范围即可； 但是这个算法有缺陷： 1、同一个数可能被筛多次，这就产生了多余的步骤。 2、占用空间很大，如果使用bool数组的话，只能筛到1e9； 3、从1-n筛，不能从m-n开始筛； C++代码： #include
初等数论中的几个重要定理 高中数学竞赛
初等数论中的几个重要定理 基础知识 定义（欧拉(Euler)函数）一组数称为是模的既约剩余系，如果对任意的，且对于任意的，若＝1，则有且仅有一个是对模的剩余，即。并定义中和互质的数的个数， 称为欧拉（Euler）函数。 这是数论中的非常重要的一个函数，显然，而对于，就是1,2，…， 中与互素的数的个数，比如说是素数，则有。 引理：；可用容斥定理来证（证明略）。 定理1：（欧拉（Euler）定理）设＝1，则。 分析与解答：要证，我们得设法找出个相乘，由个数我们想到中与互质的的个数：，由于＝1，从而 也是与互质的个数，且两两余数不一样，故 （），而（）＝1，故。 证明：取模的一个既约剩余系，考虑，由 于与互质，故仍与互质，且有，于是对每
个都能找到唯一的一个，使得，这种对应关系 是一一的，从而，。 ，，故。证毕。 这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。 定理2：（费尔马（Fermat）小定理）对于质数及任意整数有。 设为质数，若是的倍数，则。若不是的倍数，则 由引理及欧拉定理得，，由此即得。 定理推论：设为质数，是与互质的任一整数，则。 定理3：（威尔逊（Wilson）定理）设为质数，则。 分析与解答：受欧拉定理的影响，我们也找个数，然后来对应乘法。 证明：对于，在中，必然有一个数除以余1，这是因为 则好是的一个剩余系去0。 从而对，使得； 若，，则，，故 对于，有。即对于不同的对应于不同的，即中数可两两配对，其积除以余1，然后有，使，即与它自
己配对，这时，，或， 或。 除外，别的数可两两配对，积除以余1。故。定义：设为整系数多项式（），我们把含有的一组同余式 （）称为同余方组程。特别地，，当均为的一次整系数多项式时，该同余方程组称为一次同余方程组.若整数同时满足： ，则剩余类（其中）称为同余方程组的一个解，写作 定理4：（中国剩余定理）设是两两互素的正整数，那么对于任意整数 ，一次同余方程组，必有解，且解可以写为： 这里，，以及满足， （即为对模的逆）。 中国定理的作用在于它能断言所说的同余式组当模两两互素时一定有解，而对于解的形式并不重要。 定理5： （拉格郎日定理）设是质数，是非负整数，多项式 是一个模为次的整系数多项式（即），则同余方程至多有个解（在模有意义的情况下）。
利用初等数论思想解决小学数学问题
利用初等数论思想解决小学数学教学问题 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．
初等数论1——整除性
第四讲初等数论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
初等数论 论文
突出师范特色改革初等数论教学 [摘要]本文介绍了初等数论课程教学中，不断进行教学内容和教学方法的改革，加强对高师生师德、授课能力、创新精神和实践能力培养的一些做法和体会。 [关键词]初等数论教学创新精神和实践能力高师生授课能力作为培养未来中小学教师的高等师范院校，在课堂教学中突出师范特色，加强对高师生进行师德教育，培养学生的授课能力，加强学生创新精神和实践能力的培养显得尤为重要。 一、改革初等数论教学内容，加强高师生的教师素养培养 1．结合初等数论教学，对高师生进行师德教育我国数学家对数论这门学科的发展有过重大的贡献，结合初等数论课程的有关内容，介绍我国数学家在数论领域的伟大成就，能增强民族自豪感，激发学生的爱国主义思想感情。同时，结合初等数论的教学对学生进行辩证唯物主义教育、科学求实精神的教育。如在讲不定方程这一节时，介绍世界上最早提出不定方程的是我国的《九章算术》，比欧洲早200多年。在讲同余方程这一节时，介绍世界上最早提出同余方程组的是我国的《孙子算经》中的孙子定理(即中国剩余定理)。在讲数论与中学教学的联系时，介绍我国中学生在国际数学奥林匹克竞赛(IMO)上屡获佳绩，多次获得团体总分第一名的优异成绩。还介绍华罗庚在数论中的伟大成就，如“华氏定理”、“华氏不等式”。在介绍华罗庚、闵嗣鹤等数论学者甘为人梯，举办数论讨论班，指导年轻数学家(如王元、陈景润、潘承洞等)摘取“数学王冠上的宝石”的高贵品质，对学生进行师德教育。在讲到高次不定方程时，介绍费马大定理，1637年前后由法国数学家费马提出，一代又一代数学家历经350多年的不懈努力，到1993年由英国数学家怀尔斯最后证明，来激发学生勇于探索，科学求实的学习风气。 2．结合中学数学教学，改革初等数论的教学内客。作为一个高等师范院校，数学与应用数学专业的培养目标是德、智、体、美等全面发展的合格中学数学师资及其他数学专门人才，我们数学系的大多数毕业生要从事中学数学教学，因此，我们的教学要注重与中学数学教学结合起来。如整除、素数和合数、约数和倍数、奇数和偶数、平方数、同余、不定方程、[x]、数的非十进制、欧拉函数等内容与中学联系比较紧密，而且是中学数学奥林匹克竞赛的常客。据统计，被誉为“世界青年智能大赛”的国际数学奥林匹克竞赛(IMO)的试题中主要用于数论知识来解的约占30％，因此也有人把数论称为是锻炼人思维的体操。对这些知识我们要重点进行讲解，并补充一些中学数学竞赛的题目给他们分析讲解，提高学生的解题能力。同时我们开设了选修课《竞赛数学》，为提高学生以后从事辅导中学生数学奥林匹克创造了一定条件。原根与指标也是初等数论中的重要内容，但与中学内容联系比较少，我们采取简单介绍的方法进行讲解。 二、改革初等数论教学方法，加强学生创新精神和实践能力培养 1．加强实践环节，提高数学系高师生的授课能力。初等数论课中的部分内容，如整除、素数与合数、奇数与偶数、同余等概念，在其他课程中已有涉及，只是没有初等数论中讲得详细、系统，因而学生已有了一定的了解。对于这部分内容我们采取让学生讲、分组讨论，由学生对这节课教学内容、教学方法进行评论，提出自己的建议，并对如何上这节课进行阐述，最后由老师进行总结、点
初等数论试卷和答案解析
初等数论考试试卷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分) 1、素数写成两个平方数和的方法是（ ）. 2、同余式)(mod 0m b ax ≡+有解的充分必要条件是( ). 3、如果b a ,是两个正整数,则不大于a 而为b 的倍数的正整数的个数为( ). 4、如果p 是素数,a 是任意一个整数,则a 被p 整除或者( ). 5、b a ,的公倍数是它们最小公倍数的( ).
6、如果b a ,是两个正整数,则存在( )整数r q ,,使r bq a +=,b r ≤0. 三、计算题(每题8分，共32分) 1、求[136,221,391]=? 2、求解不定方程144219=+y x . 3、解同余式)45(mod 01512≡+x . 4、求??? ? ?563429,其中563是素数. （8分） 四、证明题(第1小题10分，第2小题11分，第3小题11分，共32分) 1、证明对于任意整数n ,数 6233 2n n n + +是整数. 2、证明相邻两个整数的立方之差不能被5整除. 3、证明形如14-n 的整数不能写成两个平方数的和.
初等数论__论文
突出师范特色改革初等数论 [摘要]本文介绍了初等数论课程教学中，不断进行教学内容和教学方法的改革，加强对高师生师德、授课能力、创新精神和实践能力培养的一些做法和体会。 [关键词]初等数论教学创新精神和实践能力高师生授课能力作为培养未来中小学教师的高等师范院校，在课堂教学中突出师范特色，加强对高师生进行师德教育，培养学生的授课能力，加强学生创新精神和实践能力的培养显得尤为重要。 一、改革初等数论教学内容，加强高师生的教师素养培养 1．结合初等数论教学，对高师生进行师德教育我国数学家对数论这门学科的发展有过重大的贡献，结合初等数论课程的有关内容，介绍我国数学家在数论领域的伟大成就，能增强民族自豪感，激发学生的爱国主义思想感情。同时，结合初等数论的教学对学生进行辩证唯物主义教育、科学求实精神的教育。如在讲不定方程这一节时，介绍世界上最早提出不定方程的是我国的《九章算术》，比欧洲早200多年。在讲同余方程这一节时，介绍世界上最早提出同余方程组的是我国的《孙子算经》中的孙子定理(即中国剩余定理)。在讲数论与中学教学的联系时，介绍我国中学生在国际数学奥林匹克竞赛(IMO)上屡获佳绩，多次获得团体总分第一名的优异成绩。还介绍华罗庚在数论中的伟大成就，如“华氏定理”、“华氏不等式”。在介绍华罗庚、闵嗣鹤等数论学者甘为人梯，举办数论讨论班，指导年轻数学家(如王元、陈景润、潘承洞等)摘取“数学王冠上的宝石”的高贵品质，对学生进行师德教育。在讲到高次不定方程时，介绍费马大定理，1637 年前后由法国数学家费马提出，一代又一代数学家历经350多年的不懈努力，到1993年由英国数学家怀尔斯最后证明，来激发学生勇于探索，科学求实的学习风气。 2．结合中学数学教学，改革初等数论的教学内客。作为一个高等师范院校，数学与应用数学专业的培养目标是德、智、体、美等全面发展的合格中学数学师资及其他数学专门人才，我们数学系的大多数毕业生要从事中学数学教学，因此，我们的教学要注重与中学数学教学结合起来。如整除、素数和合数、约数和倍数、奇数和偶数、平方数、同余、不定方程、[x]、数的非十进制、欧拉函数等内容与中学联系比较紧密，而且是中学数学奥林匹克竞赛的常客。据统计，被誉为“世界青年智能大赛”的国际数学奥林匹克竞赛(IMO)的试题中主要用于数论知识来解的约占30％，因此也有人把数论称为是锻炼人思维的体操。对这些知识我们要重点进行讲解，并补充一些中学数学竞赛的题目给他们分析讲解，提高学生的解题能力。同时我们开设了选修课《竞赛数学》，为提高学生以后从事辅导中学生数学奥林匹克创造了一定条件。原根与指标也是初等数论中的重要内容，但与中学内容联系比较少，我们采取简单介绍的方法进行讲解。 二、改革初等数论教学方法，加强学生创新精神和实践能力培养 1．加强实践环节，提高数学系高师生的授课能力。初等数论课中的部分内容，如整除、素数与合数、奇数与偶数、同余等概念，在其他课程中已有涉及，只是没有初等数论中讲得详细、系统，因而学生已有了一定的了解。对于这部分内容我们采取让学生讲、分组讨论，由学生对这节课教学内容、教学方法进行 评论，提出自己的建议，并对如何上这节课进行阐述，最后由老师进行总结、点拨。这样突出了学生的主导性，提高了学生学习的积极性，加强了学生实践能力
福师期末考试《初等数论》复习题及参考答案
福师期末考试《初等数论》复习题及参考答案 本复习题页码标注所用教材为： 教材名称 单价 作者 版本 出版社 初等数论 14.20 闵嗣鹤，严士健 第三版 高等教育出版社 复习题及参考答案一 一、填空(40%) 1 、求所有正约数的和等于15的最小正数为 考核知识点：约数，参见P14-19 2、若1211,, ,b b b 是模11的一个完全剩余系，则 121181,81, ,81b b b +++也是模11的 剩余系. 考核知识点：完全剩余系，参见P54-57 3．模13的互素剩余系为 考核知识点：互素剩余系，参见P58 4.自176到545的整数中是13倍数的整数个数为 考核知识点：倍数，参见P11-13 5、如果 p 是素数,a 是任意一个整数,则a 被p 整除或者 考核知识点：整除，参见P1-4 6、b a ,的公倍数是它们最小公倍数的 .
考核知识点：最小公倍数，参见P11-13 7、如果b a ,是两个正整数,则存在 整数r q ,,使r bq a +=,b r ≤0. 考核知识点：整除，参见P1-4 8、如果n 3，n 5，则15（ ）n . 考核知识点：整除，参见P1-4 二、(10%)试证：6|n(n+1)(2n+1)，这里n 是任意整数。 考核知识点：整除的性质，参见P9-12 提示： i)若 则 ii)若 则 iii)若 则 又 三、(10%)假定a 是任意整数，求证a a (mod )++≡2 103或 a a (mod )+≡203 考核知识点：二次同余式，参见P88 提示:要证明原式成立，只须证明231a a ++，或者23a a +成立即可。 四、（10％）设p 是不小于5的素数，试证明2 1(mod 24)p ≡ 考核知识点：同余的性质，参见P48-52 提示： 且是不小于5的素数． 又 且 是不小于5的素数．
闵嗣鹤、严士健,初等数论第三章习题解答
第三章 同余 §1习题（P53） 1． 证明定理2及性质庚、壬 01定理2 若11(mod )k k A B m αααα≡ (mod )i i x y m ≡ ，1,2,,i k = 则 1111k k k k A x x αααααα≡ ∑ 1111(mod )k k k k B y y m αααααα∑ 证：由(mod ) i i x y m ≡ ?戊 (mod )i i i i x y m αα≡ 11k k x x αα?≡ 戊 11(mod )k k y y m αα 1 11k k k A x x αααα?≡ 戊 1 1 1(mod )k k k B y y m αααα 1111k k k k A x x αααααα? ∑ ≡ 丁 111 1(mod )k k k k B y y m αααααα ∑ 02庚证：（i ）(mod )a b m ≡∵ 由P48定理1m a b km ka kb ????， 0(mod )km ak bk mk >?≡ （ii ）设1a a d =，1b b d =，1m m d = 0m >∵，100d m >?> (mod )a b m ≡∵ 111()m a b dm d a b ???? 111111(mod )(mod a b m m a b a b m d d d ???≡?≡ 2． 设正整数101010n n a a a a =+++ 010i a <-，试证11/a 的充要条件是0 11(1)n i i i a =?∑。 证：由101(mod 11)10(1)(mod 11)i i ≡??≡? 10(1)(mod 11)10(1)(mod 11)n n i i i i i i i i i i a a a a ==?≡??≡?∑∑ 01110(1)n n i i i i i i a a ==???∑∑ 于是11a 0 11(1)n i i i a =??∑
初等数论第三版习题解答
第一章 整数的可除性 §1 整除的概念·带余除法 1．证明定理3 定理3 若12n a a a L ，， ，都是m 得倍数，12n q q q L ，，，是任意n 个整数，则1122n n q a q a q a +++L 是m 得倍数． 证明：Q 12,,n a a a L 都是m 的倍数。 ∴ 存在n 个整数12,,n p p p L 使 1122,,,n n a p m a p m a p m ===L 又12,,,n q q q L 是任意n 个整数 即1122n n q a q a q a +++L 是m 的整数 2．证明 3|(1)(21)n n n ++ 证明 (1)(21)(1)(21)n n n n n n n ++=+++-Q 又(1)(2)n n n ++Q ，(1)(2)n n n -+是连续的三个整数 故3|(1)(2),3|(1)(1)n n n n n n ++-+ 从而可知 3|(1)(21)n n n ++ 3．若00ax by +是形如ax by +（x ，y 是任意整数，a ，b 是两不全为零的整数）的数中最小整数，则00()|()ax by ax by ++． 证： ,a b Q 不全为0 ∴在整数集合{}|,S ax by x y Z =+∈中存在正整数，因而有形如ax by +的最小整数00ax by + ,x y Z ?∈，由带余除法有0000(),0ax by ax by q r r ax by +=++≤<+ 则00()()r x x q a y y q b S =-+-∈，由00ax by +是S 中的最小整数知0r =
初中数学竞赛专题复习第三篇初等数论第19章整数的整除性下半部分试题新人教版-精品
初中数学竞赛专题复习第三篇初等数论第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 ≡，
初等数论
初等数论 初等数论从表面意义来讲，就是作为一门研究数的相关性质的数学学科。准确地按照潘承洞、潘承彪两位数论大师的说法：初等数论是研究整数最基本的性质，是一门十分重要的数学基础课。它不仅是中、高等师范院校数学专业，大学数学各专业的必修课，而且也是计算机科学等相关专业所需的课程。纵观数论发展过程，我国出现了许许多多的数论大师，如：华罗庚的早期研究方向、陈景润、潘 承洞等。 第一部分：整除 初接触初等数论，经过《初等数论》课本知整除理论是初等数论的基础。整 除理论首先涉及整除。现向上延伸则想到整除的对象，即自然数、整数。从小学、中学再到大学，我们从接触最初的1、2、3再到后来的有理数、无理数、实数再 到复数，可谓种类繁多。但数论中的整除运算仅仅局限于自然数及其整数等相关 范围内。首先大学数学中绝大多数数学定义中的自然数不包括0 ，这似乎与中学有一点差别，当然整数的定义改变就相对少得多。另外，自然数、整数的相关 基本性质需懂得及灵活利用，如分配律、交换律、反对称性等。在初等代数中曾 系统地介绍了自然数的起源问题：自然数源于经验，自然数的本质属性是由归纳原理刻画的，它是自然数公理化定义的核心。自然数集合严格的抽象定义是由Peano定理给出的，他刻画了自然数的本质属性，并导出有关自然数的有关性质。 Peano定理：设N是一个非空集合，满足以下条件： （ⅰ）对每一个n∈N，一定有唯一的一个N中的元素与之对应，这个元素 记作n+,称为是n的后继元素（或后继）； （ⅱ）有元素e∈N，他不是N中任意元素的后继； （ⅲ）N中的任意一个元素至多是一个元素的后继，即从a+=b+ 一定可以推出a=b; (ⅳ)(归纳原理)设S是N的一个子集合，e∈S, 如果n∈Ｓ则必有n+ ∈S,那么，S=N. 这样的集合N称为自然数集合，它的元素叫做自然数。 其中的归纳原理是我们常用的数学归纳法的基础。数学归纳法在中学已属重点内容，此处就不作介绍。主要描述一下推广状态下的第二种数学归纳法： （第二种数学归纳法）设P(n)是关于自然数n的一种性质或命题。如果 （1）当n=1时，P(1)不成立； （2）设n>1,若对所有的自然数m 《初等数论》课程教学标准 第一部分：课程性质、课程目标与教学要求 《初等数论》是数学与应用数学本科专业的一门专业选修课，该课程是综合应用近现代数学的工具，来处理与整数相关的问题。在计算方法、代数编码、组合论、信息安全与密码学等方面有着广泛的应用。同时由于数论问题的丰富性、多样性及解题所具有的高度技巧，对培养灵活创新的思维品质，逻辑思维、发散思维能力，系统地掌握各种数学思维方法都是不可缺少的。本课程对培养中学数学教师和从事数学研究都具有特殊重要的作用。 通过对《初等数论》的学习，使学生了解数论中的一些著名问题，比如哥德巴赫猜想、费尔马大定理等；了解数论在计算方法、代数编码、组合论、信息安全与密码学等方面的广泛应用；熟练掌握初等数论的基本内容、基本思想与基本方法；加深对整数的理解，更深入地理解某些相邻学科；培养学生的数学思维，从而提高分析问题解、决问题的能力。 第二部分：关于教材与学习参考书的建议 本课程拟采用高等教育出版社2003年7月第三版、由闵嗣鹤,严士健主编的《初等数论》一书，作为本课程的主教材。 为了更好地理解和学习课程内容，建议学习者可以进一步阅读以下几本重要的参考书： 1、《初等数论》潘承洞，潘承彪，北京大学出版社1992。 2、《初等数论》周显，华东师大出版社1984。 3、《初等数论》冯克勤，余红兵，合肥、中国科学技术出版社 4、《数论基础》王杰官，福建科学技术出版社。 第三部分：课程教学内容纲要 《初等数论》主要内容有：整数整除性理论、不定方程、同余、同余式、平方剩余与二次同余式等内容。其中整除性理论、同余式理论是初等数论课程的基本内容，解不定方程、解同余式是这些理论的最基本的应用。其各章 初等数论作业(第三章) 1. 证明: 若n 为正整数, α为实数, 则 (1) ] [][αα=?? ????n n , (2) [][]ααααn n n n =?? ???? -+++?? ? ?? ? + +1...1. 证明: (1) 设n α = nq + r + {n α}, 0 ≤ r < n , 则[n α] = nq + r , 左边 = q n r q n r nq n n =?? ???? +=??????+=???? ??][α, 右边 = []q n n r q n n r nq n n =?? ???? ++=??????++=??? ???=}{}{αααα 所以[]αα=?? ? ? ??n n ][. (2) 设n α = nq + r + {n α}, 0 ≤ r < n , 则[n α] = nq + r , α = q +( r + {n α})/n . r = 0时, α = q +{n α}/n , 左边 = q + q + … + q = nq . 右边 = nq . r ≥ 1时, 左边 = ?? ???? -+++++?? ????++++?????? ++ n n n r q n n r q n n r q 1}{...1}{}{ααα = nq + ∑ ∑ --=--=?? ? ???+++?? ? ???++1 1 }{}{r n k n r n k n k n r n k n r αα = nq + 0 + n - 1 - (n - r ) + 1 = nq + r =[n α] = 右边. # 2. 证明不等式 [2α] + [2β] ≥ [α] + [α + β] + [β] 证明: 设α = m + a , β = n + b , m , n ∈Z , 0 ≤ a , b < 1. 不妨设a ≥ b , 则 [2α] + [2β] = [2m +2a ] + [2n + 2b ] = 2m + 2n + [2a ] + [2b ]《初等数论》课程教学标准
初等数论习题(第三章)
- (6) 初等数论ppt第三章 简化剩余类、欧拉函数、RSA
- 初等数论§3同余
- 初等数论第一章第3节 带余数除法
- 精品-优秀PPT课件--初等数论[1]
- 《初等数论(闵嗣鹤、严士健)》第三版课件
- 初等数论第三章同余
- 初等数论(闵嗣鹤版)课件解析
- 初等数论(闵嗣鹤版)课件
- 初等数论第二章不定方程PPT课件
- 初等数论课件
- x初等数论第三章课件
- 初等数论第三章完整ppt课件
- 《初等数论(闵嗣鹤、严士健)》第三版课件3-5
- 闵嗣鹤、严士健,初等数论第三章习题解答
- 大学数学---初等数论
- 初等数论(闵嗣鹤版课件
- 初等数论简介 ppt课件
- 初等数论作业5-第三章2
- 初等数论 第三章 同余
- 初等数论 第三章 同余