第二章--同余---第七节--简化剩余系(2)
初 等 数 论 （16）
（第二章 同余 第七节 简化剩余系（2））
一、复习
二、例题
例2 什么样的正整数满足
ϕ (2x ) = ϕ (3x )
解 设x =2a 3b y ，其中ab 为非负整数，y |6/
。 若b > 0，（a 、b 大于或等于0）则
ϕ (2x ) =ϕ (2a +1) ϕ (3b ) ϕ (y ) =2a ×3b -1×(3-1)ϕ (y )
ϕ (3x ) =ϕ (2a ) ϕ (3b +1) ϕ (y ) =2a -1×3b ×(3-1)ϕ (y )
这时ϕ (2x )和ϕ (3x )不会相等。
所以在ϕ (2x ) =ϕ (3x )时，b = 0，x =2a y 。这时，
ϕ (2x ) =2a ×ϕ (y )，ϕ (3x ) =2×ϕ (2a )×ϕ (y )
由ϕ (2x ) = ϕ (3x )得
ϕ (2a ) =2a -1， (a > 0)
故 x =2a y ，a 为正整数，y |6/
。 例如 x = 215×35，则
ϕ (2×215×35) =215×ϕ (35)
ϕ (3×215×35) =（3 - 1）×214×ϕ (35)
例3 证明：n n 41)(=
ϕ不可能成立。 证明 若n n 4
1)(=ϕ，则n 4。设 k p p p n αααα 21212=，其中p i 为奇质数，a ≥ 2，则
k k p p p n αααα 2121224
1-=
)1()1(2)(111211121--=----k k p p p p p n k ααααϕ，于是 )1()1)(1(22121---=k k p p p p p p
上式右边为偶数，左边为奇数，矛盾。
故不存在n ，使得n n 4
1)(=ϕ。 例4 设m 与n 是正整数，证明：
ϕ (mn )ϕ ((m ，n )) = (m ，n )ϕ (m )ϕ (n )。
证明 设
，，111111n p p n m p p m k k k k ββαα ==
1)(1
111||=//n m n p m p i i ，，，，则 )()(11111n m p p mn k k k
βαβαϕϕ++= ，∏=++-=k i i
k n m p p p k k 1111)()(11)(11ϕϕβαβα )())((},{},{111k k n m i k n m i p p n m βαβαϕϕ =，
，，∏=-
=k i i
p n m 1)(11)( 由此得
)
())(()(n m n m mn ，，=ϕϕ)()11(1111m p p p k i i
k k ϕαα∏=-
⨯ )()11(1111n p p p k i i
k k ϕββ∏=-
⨯ )()()(n m n m ϕϕ，=
例5 设n ∈N ，证明：
（ⅰ） 若n 是奇数，则ϕ（4n ） = 2ϕ（n ）；
证明 我们有（4，n ）=1
ϕ (4n ) = ϕ (22n ) = ϕ (22)ϕ (n ) = 2ϕ (n )；
例如 n = 5，则有
ϕ (4n ) =ϕ (22)ϕ (5) =2×4 = 8，
模20的简化剩余系中有8个元素1，3，7，9，11，13，17，19 （ⅱ） n n 2
1)(=ϕ的充要条件是n = 2k ，k ∈N ； 证明 若n = 2k ，则
n k k k 2
122112)2(1)(==-=-ϕ， 若n n 21)(=ϕ，设n = 2k n 1，2|
/n 1，则由 )()2()2()(2
111n n n n k k ϕϕϕϕ=== 1
111111)(21)(221)(2n n n n n n n k k ϕϕϕ===- 推出ϕ (n 1) = n 1，所以n 1 = 1，即n = 2k ；
（ⅲ） n n 3
1)(=ϕ的充要条件是 n = 2k 3l ，k ，l ∈N ；
证明 若n = 2k 3l ，则
)3()2()(l k n ϕϕϕ=n l k 3131132112)()(=--
=。 若n n 3
1)(=ϕ， 设n = 2k 3l n 1，6|
/n 1，则由
)32()(311n n n l k ϕϕ== )()3()2(1n l k ϕϕϕ=
)()311(3)211(21n l k ϕ-⨯-=
111)(3231n n n l k ϕ=1
1)(31n n n ϕ= 推出ϕ (n 1) = n 1，所以n 1 = 1，
即n = 2k3l。（若ϕ(n1) =1，则n1 = 1或n1 = 2。）
初等数论（17）
（第二章同余第八节Euler定理（1））
本节中所介绍的Euler定理，在理论和应用两个方面都是很重要的。
定理1 （Euler定理）设m是正整数，
（a，m）= 1，则
aϕ(m)≡ 1 （mod m）。
证明由第三节定理2，
设｛x1，x2， ，xϕ(m)｝是模m的一个简化剩余系，则｛ax1，ax2， ，axϕ(m)｝也是模m的简化剩余系，因此
ax1ax2 axϕ(m)≡x1x2 xϕ(m) （mod m），
aϕ(m)x1x2 xϕ(m)≡x1x2 xϕ(m)（mod m）（1）
由于（x1x2 xϕ(m)，m）= 1，所以m∣（aϕ(m)-1）得出
aϕ(m)≡ 1 （mod m）。
例如（5，12）= 1，ϕ（12）= 4，
54 = 252 ≡ 12 = 1 （mod12）。
例如，（7，12）= 1，ϕ（12）= 4，
74 ≡（-5）4 =（5）4 ≡ 252 ≡ 12 = 1 （mod12）。
再如（5，17）= 1，ϕ（17）= 16，
516 =258 ≡ 88 ≡ 644 ≡ 134 ≡（- 4）4 ≡（16）2≡（-1）2 ≡1 （mod 17）。
由Euler定理我们可以得到对于模m的一个简化剩余系中的任何一个整数x，都有
xϕ(m)≡ 1 （mod m）
例如m = 16，m的简化剩余系为
｛1，3，5，7，9，11，13，15｝，ϕ（m）= 8
18 ≡ 1 （mod16）
38 ≡ 94 ≡ 812 ≡1 （mod16）
58 ≡ 254 ≡ 94 ≡ 1 （mod16）
78 ≡ 49 4 ≡1 （mod16）
定理2 （Fermat）设p是质数，则对于任意的整数a，有
a p≡a （mod p）。
证明若（a，p）= 1，则由定理1得到
a p- 1≡ 1 （mod p）⇒a p≡a（mod p）。
若（a，p）> 1，则p∣a，所以
a p≡ 0 ≡a（mod p）。
例如取p = 3，a = 6，则，63 ≡ 6 （mod3）
取p = 3，a = 5，则，53 ≡ 23≡ 8 ≡ 5 （mod3）
取p = 7，a = 5，则
57 ≡（-2）7≡-2×82≡-2×1 ≡ 5 （mod 7）
公元前50年左右，我国已经知道p∣2p - 2。
这是费马小定理的特殊情形。
例如5∣25-2=30
11∣211 - 2=2046
17∣217- 2 =131070
费马小定理的逆定理不成立，例如
2341 ≡ 2 （mod341）
但341不是质数，我们称这样的合数为伪质数。
例1 证明341是伪质数。
证明只要证明341是合数，且
2341 ≡ 2 （mod341）就可以了。
341=11×31。
又由费马小定理知
211 ≡ 2 （mod11）
231 ≡ 2 （mod31）
所以有
2341 =（211）31 ≡ 231 = 29×（211）2≡ 29×22 = 211 ≡ 2 （mod11）及
2341 =（231）11 ≡ 211 = 2×1024 ≡ 2×1≡ 2 （mod 31）即11∣2341 - 2，31∣2341 - 2，
又 （11，31） =1，所以 341∣2341 - 2
也就是 2341 ≡ 2 （mod 341）
这就证明了341是伪质数。
341是最小的伪质数，在1000以下还有另外两个伪质数：
561 =3×11×17，645 =3×5×43
N = 561时，对每一个与561互质的整数a ，
a p - 1 ≡ 1 （mod p ）都成立。
例如 取a = 7
则 7560 ≡ 1560 ≡ 1 （mod 3）
7560 ≡ 49280 ≡ 5280 ≡62570 ≡62570 ≡270 ≡3214 ≡（-1）14 ≡1 （mod 11）
7560 ≡ 49280 ≡（-2）280 ≡ 2280 ≡ 1670 ≡（-1）70 ≡ 3214 ≡ 1 （mod
17）
即 3∣7560 - 1，11∣7560 - 1，17∣7560 - 1，
又 （3，11，17） =1，
所以 3×11×17∣7560 - 1
即 7560 ≡ 1 （mod 561）。
例2 证明有无穷多个伪质数。
证明 若a n 是一个伪质数，则22-n a n a ，
令121
-=+n a n a ，以下证明 1、a n +1是合数。
2、2211-++n a n a
则由第一章第三节例11（教材22页）
证明：当2n - 1为质数时，n 一定是质数。知a n +1是合数。因为
若a n +1不是质数，121-=+n a n a 为合数，则a n 是质数，与a n 是伪质数
相矛盾。 又因为22-n a n a ，所以
N k ka a n a a n n n ∈=-=--=-+,2211211，从而
Q n n n n a k a ka a )12(1)2(121211-=-=-=--+
被12-n a 整除，即
)(0
12111+-≡-+n a a od m n
12111--++n a n a 22)12(21111-=-⨯++-+n n a a n a
于是a n +1是伪质数。
例如341是伪质数，a n +1 = 2341 - 1是伪质数，先证明2341 - 1可以被2047整除，即2341 ≡ 1 （mod 2047）。
11)2048()2(231313111341=≡== （mod 2047），
2341 - 1是合数。以下证明
221212341341---
34122112341341⨯=-=--k
1)2(12121234134122112341341-=-=-=-⨯---k k Q )12(341-=
即2341 - 1可以整除12112341---，从而2341 - 1可以整除
22)12(212112341341-=-⨯---。
例5 求710000与79999的末三位数字。
解 求一个数的末三位数字，就是求这个数除以1000的余数。 因为400452)52()1000(2233=⨯⨯=⨯=ϕϕ，
所以由Euler 定理，7400 ≡ 1 （mod 1000），
从而，710000 =7400×25 ≡ 125 ≡ 1 （mod 1000），
即710000的末三位数字为0，0，1。
因为7×79999 = 710000 ≡ 1≡ 1001 （mod 1000）， 所以，)1000(1437100179999od m =≡，
即79999的末三位数字为1，4，3。
说明 为了求79999的末三位数字，应当先求710000的末三位数字。
因为后者借助Euler 定理不难求出。
初 等 数 论 （18）
（第二章 同余 第八节 Euler 定理（2））
一、复习
二、例题
例4若n ≥ 1，则 ∑=n
d n d )(ϕ。
证明 考虑将整数1，2， ，n ，根据它们与n 的最大公约数分类，即（a ，n ）= d 时，将a 归入c d 中，
例如n =12时，1，2， ，12被分为以下6类：
C 1={ 1，5，7 ，11 }， C 2={ 2，10 }，
C 3={ 3，9 }， C 4={ 4，8 }，
C 6={ 6 }， C 12={ 12 }
这样，每一个a 恰好属于一个类，因此，
∑=n d n （c d 的元素的个数）。
由于（a ，n ）= d ，1)(=d
n d a ，，而d a 的个数就是1，2， ，d a 中与d a 互质的数的个数，即)(d
n ϕ。于是，c d 中的元素个数为)(d
n ϕ，从而 )(∑=n
d d n n ϕ。 当d 跑遍n 的因数时，
d n 也跑遍n 的因数，所以∑∑=n d n d d d n
)()(ϕϕ。因此∑=n
d n d )(ϕ成立。
例6 设n 是正整数，则5|/1n + 2n + 3n + 4n 的充要条件是4∣n 。
证明因为ϕ（5）= 4，所以，
k 4≡ 1 （mod5），1 ≤k≤ 4。
因此，设n = 4q+r，0 ≤r ≤ 3，则
1n≡ 1r（mod5）
2n ≡ 2r （mod5）
3n≡ 3r （mod5）
4n ≡ 4r （mod5）
1n+ 2n+ 3n+ 4n≡ 1r+ 2r+ 3r+ 4r
≡ 1r + 2r+ (-2)r+ (-1)r（mod5）（1）
用r = 0，1，2，3分别代入式（1）即可得出所需结论。
r = 0，1，2，3时，1r + 2r+ (-2)r+ (-1)r = 4，0，10，0，
|/1n+ 2n+ 3n+ 4n，5|/1n+ 2n+ 3n+ 4n，r = 0。
r = 0时，5
|/1n+ 2n+ 3n+ 4n，
即若4∣n，则5
|/1n+ 2n+ 3n+ 4n，则4∣n。
若5
例7 设a，b，c，m是正整数，m > 1，（b，m）= 1，并且
b a≡1 （mod m），b c≡1 （mod m），
（1）
记d = （a，c），则b d≡ 1 （mod m）。
证明利用辗转相除法可以求出整数x，y，使得ax+cy = d，显然xy < 0。
若x > 0，y < 0，由（1）式知
1≡b a≡b a x = b d b-cy = b d （b c ）-y≡b d（mod m）。
若x < 0，y > 0，由（1）式知
1≡b c y = b d b-a x = b d(b a )-x≡b d（mod m）。（注意证明过程中的指数大于0）
例如取m =15，b =19，a = 10，C = 12，则
1912 ≡（- 4）12 ≡166 ≡1 （mod15），
1910 ≡（- 4）10≡16 5 ≡1 （mod15），
2 =（10，12），192 ≡（- 4）2 ≡16 2 ≡1 （mod15）。
例8 设（a, m）= 1，d0是使
a d ≡ 1 （mod m ）成立的最小正整数，则 d 0∣ϕ（m ）。 证明 由Euler 定理，
a ϕ (m ) ≡ 1 （mod m ），
所以存在d 0 ≤ ϕ (m )，使a d ≡ 1 （mod m ）
因此，由带余数除法，有
ϕ（m ）= qd 0 + r ，q ∈Z ，q > 0，0 ≤ r < d 0。
因此，由上式及d 0的定义，利用定理1，我们得到
)(10)(m d mo a a a r r qd m ≡=≡+ϕ
即整数r 满足a r ≡ 1 （mod m ）， 0 ≤ r < d 0 。
由d 0是使a d ≡ 1 （mod m ）
成立的最小正整数可知必是r = 0，即d 0∣ϕ (m )。
例如 取m = 17，则ϕ （m ）= 16
28 ≡ 44 ≡ 16 2 ≡（-1）2 ≡1 （mod 17）
8是使2d ≡ 1 （mod 17）成立的最小正数，8∣ 16 =ϕ （m ）。 再如 取m = 19，则ϕ（m ）= 18
59 ≡ 5×58 ≡ 5×254 ≡ 5×64 ≡ 5×172 ≡ 5×（-2）2 ≡ 20 ≡1
（mod 19）
9是使59 ≡1 （mod 19）
的最小整数，9∣ 18 =ϕ（19）。
例9 设p 是质数，p ∣b n - 1，n ∈N ，则下面的两个结论中至少有一个成立：
(ⅰ) p ∣b d - 1对于n 的某个因数d < n 成立；
(ⅱ) p ≡ 1 （mod n ）。
若2|/n ，p > 2，则(ⅱ)中的mod n 可以改为mod 2n 。 证明 记d =（n ，p - 1），
由Euler 定理有b p - 1 ≡ 1 （mod p ），
又b n ≡ 1 （mod p ），（b ，p ） =1 由例题6，有 b d ≡ 1 （mod p ）。若d < n ，则d ∣n ，结论（ⅰ）成立。
若d = n ，则n ∣p - 1，p ≡ 1 （mod n ），这就是结论(ⅱ)。 若2|/n ，p > 2，则p ≡1 （mod 2）。
又p ≡ 1 （mod n），利用同余的基本性质，得到
p ≡ 1 （mod2n）。
注：例8给出了一个求质因数的方法，就是说，整数b n - 1的质因数p，是b d- 1（当d∣n时）的质因数，或者是形
|/n，p > 2时，是形如2kn+ 1的数)。
如kn+ 1的数（当2
例如将38- 1分解因数。
由例5，n = 8，
38- 1的因数是31 - 1，32 - 1，34 - 1的因数，或是9，17，25，33，41，……
中的质数。
31 - 1=2，32 - 1=8，34 - 1=80
9，17，25，33，41，……中的质数为17，41，……。
所以38- 1的因数可能是2，5，17，41，……。
38- 1=25×5×41
再如，126 - 1的因数是121 - 1，122 - 1，123 - 1的因数，或是7，13，19，25，……中的质数。
121 - 1=11，
122 - 1=143=11×13
123 - 1=1727=11×157
126 - 1=2985983=11×19019
=11×13×133×157
其中133满足133 ≡ 1 （mod6）
例10 将211- 1 = 2047分解因数。
解由例8，若p∣211- 1，则p≡ 1 （mod 22），即p只能在数列23，45，67， ，22k+ 1， 中。逐个用其中的质数去除2047，得到
23∣2047，2047 = 23⋅89。
例11 将235- 1 = 34359738367分解因数。
解由例8，若p∣235- 1，则p是25- 1 = 31或27- 1 = 127的质因数，或者p ≡ 1 (mod70)。由于31和127是质数，并且
235- 1 = 31⋅127⋅8727391，
所以，235- 1的另外的质因数p只可能在数列
71，141，211，281， (1)
中。经检验，得到8727391 = 71⋅122921。
显然，122921的质因数也在31，127或者数列(1)中。简单的计算说明，122921不能被31和127整除，也不能被数列（1）中的不超过122921< 351的数整除，所以122921是质数，于是
235- 1 = 31⋅127⋅71⋅122921。
练习题
将136 - 1分解因数。
[文档可能无法思考全面，请浏览后下载，另外祝您生活愉快，工作顺利，万事如意!]
第三讲 同余理论
第二章 同余理论 2.1 同余的概念和基本性质 【定义2.1.1】给定一个正整数m ，两个整数a 、b 叫做模m 同余，如果a －b 被m 整除，或b a m -|，记作b a ≡ ()m mod ； 否则叫做模m 不同余，记作a≠b （（mod m ）） 【注】由于b a m -|等价于b a m --|，所以同余式 b a ≡ ()m mod 等价于 b a ≡()()m -mod ， 故以后总假定模1≥m 。 【例1】 7│28＝29－1，故29≡1（mod 7）； 7│21＝27－6，故27≡6（mod 7）； 7│28＝23－（－5），故23≡－5（mod 7）； 同余运算的相关性质： 【性质1】设m 是一个正整数，a 、b 是两个整数，则a≡b（mod m ）?存在整数k ，使得a ＝b ＋km 。 （证）a≡b（mod m ） ? b a m -| ? 存在k ，使得 a －b ＝km ，即a ＝b ＋km 【性质2】同余是一种等价关系。即 自反性：a≡a（mod m ） 对称性：a≡b（mod m ）? b≡a （mod m ） 传递性：a≡b（mod m ）且b≡c （mod m ）? a≡c （mod m ） （证）（i ）m│0＝a －a ? a≡a（mod m ） （ii ）a≡b （mod m ）? m│a－b ? m│b－a ＝－(a －b) ? b≡a （mod m ） （iii ）a≡b（mod m ），b≡c（mod m ）? m│a－b ，m│b－c ? m│(a－b)＋ (b －c)＝a －c ? a≡c （mod m ） 【性质3】（等价定义）整数a 、b 模m 同余?a 、b 被m 除的余数相同。 （证）由欧几里得除法，存在q ，r ，q '，r '，使得 a ＝qm ＋r ， b ＝q 'm ＋r ' 即 a －b ＝(q －q ')m ＋(r －r ') 或 （r －r '）＝(a －b)－ (q －q ')m
高中数学竞赛数论
高中数学竞赛 数论 剩余类及剩余系 (1)定义1 设m 为正整数，把全体整数按对模m 的余数分成m 类，相应m 个集合记为：K 0,K 1,…,K m-1,其中K r ={qm+r|q ∈Z,0≤余数r ≤m-1}称为模m 的一个剩余类(也叫同余类)。K 0,K 1,…,K m-1为模m 的全部剩余类. (2)性质(ⅰ)i m i K Z 1 0-≤≤= 且K i ∩K j =φ(i ≠j). (ⅱ)每一整数仅在K 0,K 1,…,K m-1一个里. (ⅲ)对随意a 、b ∈Z ，那么a 、b ∈K r ⇔a ≡b(modm). (1)定义2 设K 0,K 1,…,K m-1为模m 的全部剩余类，从每个K r 里任取一个a r ，得m 个数a 0,a 1,…,a m-1组成的数组，叫做模m 的一个完全剩余系,简称完系. 特殊地,0,1,2,…,m -1叫做模m 的最小非负完全剩余系.下述数组叫做模m 的肯定最小完全剩余系:当m 为奇数时,21,,1,0,1,,121,21--+---- m m m ;当m 为偶数时,12 ,,1,0,1,,12,2--+--m m m 或2,,1,0,1,,12m m -+-. (2)性质(ⅰ)m 个整数构成模m 的一完全剩余系⇔两两对模m 不同余. (ⅱ)假设(a,m)=1，那么x 及ax+b 同时遍历模m 的完全剩余系. 证明:即证a 0,a 1,…,a m-1及aa 0+b, aa 1+b,…,aa m-1+b 同为模m 的完全剩余系, 因a 0,a 1,…,a m-1为模m 的完系时,假设aa i +b ≡aa j +b(modm),那么a i ≡a j (modm), 冲突!反之,当aa 0+b, aa 1+b,…,aa m-1+b 为模m 的完系时,假设a i ≡a j (modm),那么有
同余理论及其应用
同余理论及其应用 基础知识 一. 定义 定义1. 设m 为正整数，整数a 和b 之差可被m 整除时，称为a 和b 关于模m 同余，记作 ).(mod m b a ≡ 定义2. 被正整数m 除余数相等的所有整数的集合称为模m 的剩余类。模m 的剩余类共有m 个。 定义3. 在模m 的m 个剩余类中各取一个整数作为代表，这些代表的集合称为模m 的完全剩余系。 定义4. 绝对值不超过]2 [ m 的模m 的完全剩余系称为模m 的绝对最小剩余系。 定义5. 当模m 的某一剩余类的所有整数均与m 互素时，则称此剩余类是模m 的简化类。模m 的简化类共有)(m φ个。 定义6. 在模m 的)(m φ个简化类中各取一个整数作为代表，这些代表的集合称为模m 的简化剩余系。 定义7. 欧拉函数：设n 为正整数，从1到n 的整数中与n 互素的整数的个数用)(n φ表示，称)(n φ为欧拉函数。当12 12 s s n p p p ααα=时，有)1 1)...(11)(11()(21s p p p n n --- =φ 二. 定理 定理1. ).(mod m b a ≡ 的必要充分条件是a 和b 被m 除的余数相等。 定理 2. I .);(mod m a a ≡II .若),(mod m b a ≡则);(mod m a b ≡III .若),(mod m b a ≡),(mod m c b ≡则 ).(mod m c a ≡ 定理3. 若)(m od 11m b a ≡，)(m od 22m b a ≡，则I .)(m od 2121m b b a a +≡+；II .(m od 2121m b b a a -≡-2 )(m od 212m b b a -≡；III .)(m od 2121m b b a a ≡. 定理4. 如果),...,2,1)((m od n i m b a i i =≡，则I .)(m od ......2121m b b b a a a n n +++≡+++；II . ).(m od ......2121m b b b a a a n n ≡ 推论. 如果).(mod m b a ≡n 为任意正整数，则).(mod m b a n n ≡ 定理5. 如果).(mod m cb ca ≡则).) ,((mod m c m b a ≡ 推论. 如果1),(=m c ，).(mod m cb ca ≡则).(mod m b a ≡ 定理6. 如果).(mod m b a ≡则).,(),(m b m a = 定理7. a 和b 属于模m 的同一剩余类的充要条件是).(mod m b a ≡ 定理8. m 个整数m a a a ,...,,21是模m 的完全剩余系的充要条件是m a a a ,...,,21关于模m 两两互不同余。 定理9. 设f 是正整数m 的正因数。在模f 的属于c 的剩余类中取整数f f m c f c c )1(,...,,-++，则它们是模m 的 f m 个剩余类。 定理10. 与m 互素的)(m φ个整数是模m 的简化剩余系的充要条件是这)(m φ个整数关于模m 两两互不同 余。又设r a a a ,...,,21是模m 的简化剩余系，如果1),(=m c ，则r ca ca ca ,...,,21也是模m 的简化剩余系。
模12的最小非负简化剩余系
模12的最小非负简化剩余系 首先，我们来了解一下什么是最小非负简化剩余系。在数学中，一个 简化剩余系可以看作是给定一个模数，然后将所有同余于该模数的数 放在一个集合中，这个集合就称为简化剩余系。而最小非负简化剩余 系则是在简化剩余系的基础上，使得集合中的数都是非负整数，并且 从0开始，直至模数减1。这个系列对于计算所有模数同余运算的答案 特别有用。 下面是模12的最小非负简化剩余系： {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} 可以看到，我们将所有同余于12的数都放入了一个集合中，并且从0 开始逐一往上加，直至11。这个集合中的数就是模12的最小非负简化 剩余系。 现在让我们来看几个例子，来了解一下模12的最小非负简化剩余系的 使用。 例1：计算10 + 9 (mod 12) 首先我们在模12的简化剩余系中找到10和9，它们分别对应着10和9。
我们将它们相加得到19，但是19不在最小非负简化剩余系中，因此我们需要将19减去12直到得到的数在最小非负简化剩余系中。这里，19 - 12 = 7，因此10 + 9 (mod 12) = 7。 例2：计算8 + 6 (mod 12) 同样地，在模12的最小非负简化剩余系中找到8和6，它们分别对应着8和6。将它们相加得到14，但是14不在该系列中，因此我们需要将14减去12直到得到的数在最小非负简化剩余系中。这里，14 - 12 = 2，因此8 + 6 (mod 12) = 2。 以上这些例子都是比较简单的，但是当数值较大或运算较复杂时，使用最小非负简化剩余系可以大大减少计算量，并且避免产生过多的溢出和误差。因此，在进行模运算时，使用最小非负简化剩余系是非常方便的。
《初等数论》复习思考题答案
（0346）《初等数论》复习思考题答案 1． 一个不等于1的自然数，分别去除967，1000，2001得到相同的余数。试求这个自然数。 解：设这个自然数为q ，则q | 1000 – 967，即q | 33。又q | 2001 – 1000，即q | 1001，所以 q = 11。 2． 求证：不可能存在两个质数p 1，p 2，使得p 1 + p 2 = 111…1(20位数)。 证明：由于p 1与p 2的和为奇数，故p 1与p 2中有一个为2，设p 2 = 2，则 110101*********-++++=Λp 。因为10 ≡ 1(mod 9)，所以p 1 ≡ 19 – 1 ≡ 0 (mod 9)，即p 1不是质数，矛盾。 3． 如果p 和p + 2都是大于3的质数，求证6 | p + 1。 证明：首先p 是大于3的质数，则p 不是3的倍数。又p + 2是大于3的质数，所以p – 1不是3的倍数。故p + 1 必为3的倍数。但p + 1 为偶数，所以p + 1 为2的倍数。由于2与3互质，所以p + 1 为6的倍数，于是6 | p + 1。 4． 设m , n 为整数，求证m +n , m -n 与mn 中一定有一个是3的倍数。 证明：若m 或n 为3的倍数，则mn 是3的倍数；若m 是3的倍数加1，n 是3的倍数加1，则m -n 是3的倍数；若m 是3的倍数加1，n 是3的倍数加2，则m +n 是3的倍数；若m 是3的倍数加2，n 是3的倍数加1，则m +n 是3的倍数；若m 是3的倍数加2，n 是3的倍数加2，则m -n 是3的倍数，结论成立。 5． 证明：两个奇数的平方差是8的倍数。 证明：若a =2k +1为奇数，则a 2-1=4k (k +1)，因2|k (k +1)，所以8| a 2-1。于是当a , b 均为奇数时，由8| a 2-1与8| b 2-1得8|a 2-b 2。即两个奇数的平方差是8的倍数。 6．已知p 为偶数，q 为奇数。方程组???=+=-q y x p y x 39918的解是整数，那么（ ）。 A. x 是奇数，y 是偶数 B. x 是偶数，y 是奇数 C. x 是偶数，y 是偶数 D. x 是奇数，y 是奇数 答：B. 7．求1980的标准分解式。 解：1980=22?32?5?11。 8． 求792与594的最大公因数。
剩余系
剩余系 一、基础知识： 对于任意正整数n而言，一个整数除以m所得的余数只能是0,1,2, …,n-1中的某一个。依次可将整数分成n个类（例如n＝2时，就是奇数或偶数），从每一类中各取一个数所组成的集合就称为模的一个完全剩余系，简称为模的完系。 定义1：如果一个剩余系中包含了这个正整数所有可能的余数（一般地，对于任意正整数n，有n个余数：0,1,2,...,n-1），那么就被称为是模n的一个完全剩余系。 定义2：剩余系：设模为m,则根据余数可将所有的整数分成m类，分别记成 [0],[1],[2],…[m-1]，这m个数{0,1,2,…m-1}称为一个完全剩余系，每个数称为相应类的代表元。 例如：当m=10则,{0,1,2,3,4,5,6,7,8,9} 最小非负完全 {-5,-4,-3,-2,-1,0,1,2,3,4} 绝对值最小 {-4,-3,-2,-1,0,1,2,3,4,5} 绝对值最小 （一）根据剩余类的概念，很容易得到以下几条有关剩余类的性质： ①每一个整数一定包含在而且仅包含在模m的一个剩余类中 ②整数p所属的模m的剩余类中的每一个数都可以写成km+p的形式，这里k是整数 用符号p mod m表示p所属的模m的剩余类，这条性质写成数学表达式就是 p mod m= {p+km（k是整数）} ③整数p、q在模m的同一个剩余类中的充要条件是p、q对模m同余。这条性质用数学符号就可表示为：p mod m= q mod ≡q（mod m） 实际上，同余式就是剩余类等式的一个特殊情况，是集合中的一个元素，前面有关同余的一些性质对剩余类仍然成立。 这条性质表明，对于模m的两个剩余类要么相等，要么它们的交集为空集，因此，模m有且仅有m个剩余类，它们是： 0modm，1 mod m，2 mod m，…（m―1）mod m。 在解决一些有关模m余数的问题时，我们就可以查看m个数：0，1，2，…，m―1，从而得相应的剩余类的情况，使问题变得异常简单，具体例子，请看后面的例题。 ④在任意取定的m+1个整数中，必有两个整数对模m同余。 在解决一些有关模m余数的问题时，我们就可以查看m个数：0，1，2，…，m―1，从而得相应的剩余类的情况，使问题变得异常简单，具体例子，请看后面的例题。 ④在任意取定的m+1个整数中，必有两个整数对模m同余。 （二）根据同余式的性质，我们很容易得到剩余系的其它一些性质： ⑤m个整数x1，x2，…，x m是模m的一组完全剩余系的充要条件是x1，x2，…，x m 中的任意两个数对模m都不同余。 ⑥如果x1，x2，…，x m是模m的一组完全剩余系，那么对任意的整数c，x1+c，x2+c，…，x m+c也是模m的一组完全剩余系。 ⑦设k1，k2，…，k m是m个整数，如果x1，x2，…，x m是模m的一组完全剩余系，那么x1+k1m，x2+k2m，…，x m+k1m也是模m的一组完全剩余系。 二、典型例题： 1．求证：一定存在整数n，使4n2+27n―12能被5整除，并求出这些数。 分析：可以选模5的一个完全剩余系逐个验算，只要数a使4a2+27a―12能被5整除，那么剩余类a mod 5中的任何一个整数也满足条件。 解：取模5的一个完全剩余系0，1，2，3，4直接计算可知，3和4满足条件，所以使4n2+27n―12能被5整除的所有的整数是n≡3（mod 5）和n≡4（mod 5）。 2．求使2n-1为7的倍数的所有正整数n．
信息安全数学基础习题答案 2
信息安全数学基础习题答案 第一章整数的可除性 1．证明：因为2|n 所以n=2k , k∈Z 5|n 所以5|2k ，又（5，2）=1，所以5|k 即k=5 k1，k1∈Z 7|n 所以7|2*5 k1 ,又（7，10）=1，所以7| k1即k1=7 k2，k2∈Z 所以n=2*5*7 k2即n=70 k2, k2∈Z 因此70|n 2．证明：因为a3-a=(a-1)a(a+1) 当a=3k，k∈Z 3|a 则3|a3-a 当a=3k-1，k∈Z 3|a+1 则3|a3-a 当a=3k+1，k∈Z 3|a-1 则3|a3-a 所以a3-a能被3整除。 3．证明：任意奇整数可表示为2 k0+1，k0∈Z （2 k0+1）2＝4 k02+4 k0+1=4 k0 (k0+1)+1 由于k0与k0+1为两连续整数，必有一个为偶数，所以k0 (k0+1)=2k 所以（2 k0+1）2=8k+1 得证。 4．证明：设三个连续整数为a-1,a,a+1 则(a-1)a(a+1)= a3-a 由第二题结论3|（a3-a）即3|(a-1)a(a+1) 又三个连续整数中必有至少一个为偶数，则2|(a-1)a(a+1) 又（3，2）=1 所以6|(a-1)a(a+1) 得证。 5．证明：构造下列k个连续正整数列： (k+1)！+2, (k+1)！+3, (k+1)！+4,……, (k+1)！+(k+1), k∈Z 对数列中任一数 (k+1)！+i=i[(k+1)k…(i+1)(i-1)…2*1+1], i=2,3,4,…(k+1) 所以i|(k+1)！+i 即(k+1)！+i为合数 所以此k个连续正整数都是合数。 6．证明：因为1911/2＜14 ,小于14的素数有2，3，5，7，11，13 经验算都不能整除191 所以191为素数。 因为5471/2＜24 ,小于24的素数有2，3，5，7，11，13，17，19，23 经验算都不能整除547 所以547为素数。 由737=11*67 ,747=3*249 知737与747都为合数。 8．解：存在。eg：a=6,b=2,c=9 10．证明：p1 p2 p3|n，则n= p1 p2 p3k，k∈N+ 又p1≤p2≤p3，所以n= p1 p2 p3k≥p13 即p13≤n1/3 p1为素数则p1≥2，又p1≤p2≤p3，所以n= p1 p2 p3k≥2 p2 p3≥2p22 即p2≤(n/2)1/2得证。 11．解：小于等于5001/2的所有素数为2，3，5，7，11，13，17，19，依次删除这些素数的倍数可得所求素数： 12．证明：反证法 假设3k+1没有相同形式的素因数，则它一定只能表示成若干形如3k-1的素数相乘。 (3 k1+1)(3 k2+1)=[( 3 k1+1) k2+ k1]*3+1 显然若干个3k+1的素数相乘，得
初等数论课程教学大纲新
《初等数论》课程教学大纲 一、课程的性质与地位 “初等数论”课程是宿迁高等师范学校数学学科专业必修的一门课程。数学专业的学生学习初等数论的基础知识可以加深对数的性质的了解与认识，便于理解和学习与其相关的一些课程。数论是研究整数性质的一门很古老的数学分支，其初等部分是以整数的整除性为中心的，包括整除性、不定方程、同余式、连分数、素数（即整数）分布以及数论函数等内容，统称初等数论（elementary number theory）。 初等数论的大部份内容早在古希腊欧几里德的《几何原本》中就已出现。欧几里得证明了素数有无穷多个，他还给出求两个自然数的最大公约数的方法，即所谓欧几里得算法。我国古代在数论方面亦有杰出之贡献，现在一般数论书中的“中国剩余定理”正是我国古代《孙子算经》中的下卷第26题，我国称之为“孙子定理”。 近代初等数论的发展得益于费马、欧拉、拉格朗日、勒让德和高斯等人的工作。1801年，高斯的《算术探究》是数论的划时代杰作。高斯还提出：“数学是科学之王，数论是数学之王”。可见高斯对数论的高度评价。 由于自20世纪以来引进了抽象数学和高等分析的巧妙工具，数论得到进一步的发展，从而开阔了新的研究领域，出现了代数数论、解析数论、几何数论等新分支。而且近年来初等数论在计算器科学、组合数学、密码学、代数编码、计算方法等领域内更得到了广泛的应用，无疑同时间促进着数论的发展。 二、课程教学目标 初等数论是研究整数性质的一门学科，历史上遗留下来没有解决的大多数数论难题其问题本身容易搞懂，容易引起人的兴趣，但是解决它们却非常困难。本课程的目的是简单介绍在初等数论研究中经常用到的若干基础知识、基本概念、方法和技巧。 数论是以严格和简洁著称，内容既丰富又深刻。通过这门课的学习，使学生获得关于整数的整除性、不定方程、同余式、数论函数及简单连分数的基本知识，掌握数论中的最基本的理论和常用的方法，加强他们的理解和解决数学问题的能力，为今后的学习奠定必要的基础。 三、教学基本内容及要求
第二章--同余---第七节--简化剩余系(2)
初 等 数 论 （16） （第二章 同余 第七节 简化剩余系（2）） 一、复习 二、例题 例2 什么样的正整数满足 ϕ (2x ) = ϕ (3x ) 解 设x =2a 3b y ，其中ab 为非负整数，y |6/ 。 若b > 0，（a 、b 大于或等于0）则 ϕ (2x ) =ϕ (2a +1) ϕ (3b ) ϕ (y ) =2a ×3b -1×(3-1)ϕ (y ) ϕ (3x ) =ϕ (2a ) ϕ (3b +1) ϕ (y ) =2a -1×3b ×(3-1)ϕ (y ) 这时ϕ (2x )和ϕ (3x )不会相等。 所以在ϕ (2x ) =ϕ (3x )时，b = 0，x =2a y 。这时， ϕ (2x ) =2a ×ϕ (y )，ϕ (3x ) =2×ϕ (2a )×ϕ (y ) 由ϕ (2x ) = ϕ (3x )得 ϕ (2a ) =2a -1， (a > 0) 故 x =2a y ，a 为正整数，y |6/ 。 例如 x = 215×35，则 ϕ (2×215×35) =215×ϕ (35) ϕ (3×215×35) =（3 - 1）×214×ϕ (35) 例3 证明：n n 41)(= ϕ不可能成立。 证明 若n n 4 1)(=ϕ，则n 4。设 k p p p n αααα 21212=，其中p i 为奇质数，a ≥ 2，则 k k p p p n αααα 2121224 1-= )1()1(2)(111211121--=----k k p p p p p n k ααααϕ，于是 )1()1)(1(22121---=k k p p p p p p 上式右边为偶数，左边为奇数，矛盾。
《初等数论》教学大纲
《初等数论》教学大纲 一、课程名称 《初等数论》 二、课程的性质 数学与应用数学，信息与计算科学专业的限制性选修课。 三、课程的教学目的 初等数论是研究整数最基本性质，是一门十分重要的数学基础课。它以算术方法为主要方法来研究整数本身所包含的丰富而重要的内涵与特征。同时，初等数论是数学中“理论与实践”相结合得十分紧密的课程。近代数学中许多重要的思想，概念，方法与技巧都是从对整数性质的深入研究而不断丰富和发展起来的。它在计算机科学、代数编码，信号的数字处理，组合数学，离散数学，计算方法等领域中有着广泛的应用。本课程的教学目的是使学生对整数形成清楚而正确的认识，并经过本课程的学习，使他们掌握初等数论的基本思想方法，以培养和增强学生运用数学手段分析和解决实际问题的能力。 每一章节的教学目标： 第一章 整数的可除性（8学时） 1、整除·带余数除法 2、最大公约数与辗转相除法 3、整除的性质及最小公倍数 4、素数·算术基本定理 5、函数 {}X X ],[ 及其在数论中的应用 6* 整数的正约数的个数及其和 重点内容：整除的概念，算术基本定理，最大公约数理论。 带有“*”的内容可作为学生自学内容或选讲内容。 第一章 不定方程
1、二元一次不定方程 2、多元一次不定方程 3、勾股数 4* Fermat问题的介绍 重点内容：一次不定方程的解法，勾股数问题。 带有“*”号的内容可作为学生自学内容。 第二章同余理论（10学时） 1、同余的概念与基本性质 2、同余的代数运算性质 3、检查约数的方法 4、弃九法 5、剩余类与完全剩余系 6、简化剩余类（系）与Eule r函数 7、Euler定理·Fermat定理与Wilson定理 重点内容：同余的概念与性质，剩余类与剩余系，Euler函数与Euler定理以及同余计算。 第三章同余方程（8学时） 1、一次同余方程及其求解 2、孙子定理·一次同余方程组的求解 3、高次同余方程的解数与解法 4、素数模的同余方程 5* 一般二次同余方程 6* 单素数的平方剩余与平方非剩余
10的简化剩余系
10的简化剩余系 简化剩余系是数论中一个重要的概念，它在解决整数的除法问题时起到了关键作用。简化剩余系指的是对于给定的整数m，我们可以找到一组整数{r1, r2, ..., rn}，使得对于任意的整数a，都存在唯一的ri满足a ≡ ri (mod m)。 在了解简化剩余系之前，我们先来了解一下模运算。模运算是将一个数除以另一个数，得到的余数。例如，6除以4的余数是2，可以用符号表示为6 ≡ 2 (mod 4)。模运算在数论中经常被使用，它可以帮助我们研究整数的性质和推导一些结论。 简化剩余系的概念就是基于模运算而来。当我们考虑一个整数a时，可以将它表示为a = qm + r，其中q是商，r是余数。我们可以将 r视为a在模m下的简化剩余。简化剩余系的关键在于，对于给定的m，我们可以找到一组整数{r1, r2, ..., rn}，使得它们在模m 下都是不同的，并且对于任意的整数a，都存在唯一的ri满足a ≡ ri (mod m)。 简化剩余系在解决整数除法问题时非常有用。例如，我们想要求解一个整数b除以m的余数，我们可以利用简化剩余系来简化计算过程。首先，我们找到一个在模m下等于b的整数ri，然后我们可以将b表示为b = qm + ri，其中q是商。这样，我们就可以得到b 除以m的余数为ri。
简化剩余系还可以用来解决同余方程。同余方程指的是形如ax ≡ b (mod m)的方程，其中a、b和m都是整数，x是未知数。通过简化剩余系，我们可以找到同余方程的解。首先，我们找到一个在模m下等于b的整数ri，然后我们可以将同余方程表示为ax = qm + ri，其中q是商。我们可以通过对等式两边同时乘以a的逆元来消去a，得到x = (ri * a^-1 - q)m的形式。这样，我们就可以得到同余方程的解x。 简化剩余系还有很多其他的应用。例如，在密码学中，简化剩余系被广泛应用于RSA算法和离散对数问题的求解。在计算机科学中，简化剩余系可以用来进行哈希函数的设计和散列算法的实现。在代数学中，简化剩余系是研究同余环和模运算的基础。 总结来说，简化剩余系是数论中一个重要的概念，它在解决整数的除法问题和同余方程时起到了关键作用。通过简化剩余系，我们可以简化计算过程，得到有效的解。简化剩余系还有很多其他的应用，在不同领域中发挥着重要的作用。对于数论的研究和应用而言，简化剩余系是一个不可或缺的工具。
人教版高中选修(B版)4-6第二章同余课程设计 (2)
人教版高中选修(B版)4-6第二章同余课程设计 1. 课程设计目标 本课程设计的目标是： •了解同余运算及其基本性质； •掌握同余方程的求解方法及应用； •学会使用同余运算解决实际问题。 2. 教学内容 本课程的主要教学内容包括： 1.同余运算及其基本性质 2.同余方程的求解方法 3.同余方程在密码学中的应用 3. 教学方法 本课程的教学方法主要采用讲授、示范和练习相结合的方法，其中： 1.讲授：教师向学生讲解同余运算及其基本性质、同余方程的求解方法 和同余方程在密码学中的应用； 2.示范：教师用实例或算法向学生演示同余方程的求解过程； 3.练习：教师设计题目，要求学生完成同余方程的求解和应用练习，加 强学生的动手操作能力。 4. 教学进度 本课程建议分为5个课时，教学进度如下：
1.第一课时：同余运算及其基本性质（1小时） 2.第二课时：同余方程的定义及其求解方法（2小时） 3.第三课时：同余方程的应用，密码学中的同余方程（1小时） 4.第四课时：同余方程的应用，剩余系定理（1小时） 5.第五课时：同余方程的应用，中国剩余定理（1小时） 5. 教学内容详细安排 第一课时 同余运算及其基本性质 1.同余的定义和性质 2.同余的三大性质：自反性、对称性、传递性 3.同余的四则运算：加、减、乘、除 4.同余的幂运算和逆元 第二课时 同余方程的定义及其求解方法 1.同余方程的定义和表示法 2.同余方程的求解方法 –数学方法 –直观方法 3.同余方程的通解和特解 4.一元一次同余方程组的求解（两个方程） 第三课时 同余方程的应用，密码学中的同余方程 1.同余方程在密码学中的应用
第三节 简化剩余系
初等数论第二章同余 第三节简化剩余系 在模m的完全剩余系中，与m互素的整数所成的集合有一些特殊的性质，我们要在这一节中对它们做些研究。 定义1 设R是模m的一个剩余类，若有a R，使得(a, m) = 1，则称R是模m的一个简化剩余类。 显然，若R是模的简化剩余类，则R中的每个整数都与m互素。 例如，模4的简化剩余类有两个： R1(4) = { , -7 , -3, 1 , 5 , 9 , }， R3(4) = { , -5 , -1 , 3 , 7 , 11 , }。 定义2对于正整数k，令函数ϕ(k)的值等于模k的所有简化剩余类的个数，称ϕ(k)为Eule r函数，或Eule r—ϕ函数。 例如，容易验证ϕ(2) = 1，ϕ(3) = 2，ϕ(4) = 2，ϕ(7) = 6。 显然，ϕ(m)就是在m的一个完全剩余系中与m互素的整数的个数。 定义3对于正整数m，从模m的每个简化剩余类中各取一个数x i，构成一个集合{x1, x2, ,xϕ(m)}，称为模m的一个简化剩余系（或简称为简化系）。 显然，由于选取方式的任意性，模m的简化剩余系有无穷多个。 例如，集合{9, -5, -3, -1}是模8的简化剩余系，集合{1, 3, 5, 7}也是模8的简化剩余系，通常称最小非负简化剩余系。 定理1整数集合A是模m的简化剩余系的充要条件是 (ⅰ) A中含有ϕ(m)个整数； (ⅱ) A中的任何两个整数对模m不同余； (ⅲ) A中的每个整数都与m互素。 证明留作习题。 定理2设a是整数，(a, m) = 1，B = {x1, x2, , xϕ(m)}是模m的简化剩余系，则集合A = {ax1, ax2, , axϕ(m)}也是模m的简化剩余系。 证明显然，集合A中有ϕ(m)个整数。其次，由于(a, m) = 1，所以，对于任意的x i（1 ≤i≤ϕ(m)），x i B，有(ax i, m) = (x i, m) = 1。因此，A中的每一个数都与m互素。最后，我们指出，A中的任何两个不同的整数对模m不同余。事实上，若有x', x B，使得 a x'ax(mod m)，
初等数论教案第二章同余式
第二章同余式 第一节同余的基本概念与基本性质 教学目的：同余的基本定义与性质. 教学重点：同余的性质. 教学课时：2课时 教学过程 1定义1给定正整数m,如果整数a与b之差被m整除，则称a与b 对于模m同余，或称a与b同余，关于模m，记为 a = b (mod m)， 此时也称b是a对模m的同余. 如果整数a与b之差不能被m整除，则称a与b对于模m不同余, 或称a与b不同余，模m，记为a = b (mod m). 2、定理1下面的三个叙述是等价的： (i ) a = b (mod m); (ii)存在整数q,使得a = b qm; (iii)存在整数q i, q2，使得a = q〔m r, b = q2m r, 0 乞r < m. 证明：留作习题. 3、定理2同余具有下面的性质： (i ) a = a (mod m); 证明：留作习题.
(i ) a = b (mod m) = b = a (mod m); (iii) a 三b, b - c (mod m)二a - c (mod m).证明：留作习题.
(1) 证明：留作习题. 4、 定理3设a , b , c , d 是整数，并且 a = b (mod m), c = d (mod m), 则 (i ) a c 三 b d (mod m); (ii) ac 三 bd (mod m); (iii) a n 三 b n (mod m); (iv) f(a) = f(b) (mod m),其中f(x) 是任意整系数多项式 证明：(i )由式(1)及定义1可知 m a - b , m c - d , 因此 m (a c) - (b d), 此即结论(i ); (ii )由式(1)及定理1可知，存在整数q i 与q 2使得 a = b q 1m , c = d q 2m , 因此 ac = bd (qqm q 1d q 2b)m , 再利用定理1,推出结论(ii )•证毕. 5、 定理4 设a i , b i (0乞匕n )以及x , y 都是整数，并且 x = y (mod m), a i = bi (mod m), 0 乞 i 乞 n , 则
第二讲 同余(数论复赛辅导)
第二讲 同余 一.根底知识 1.定义1. 设m 是正整数，假设用m 去除整数b a ,，所得的余数一样，则称a 与b 关于模m 同余，记作)(mod m b a ≡，否则称a 与b 关于模m 不同余，记作a )(mod m b .例如：)15(mod 434≡， )7(mod 11000-≡，98(mod 2) 等等。 当m b <≤0时，)(mod m b a ≡，则称b 是a 对模m 的最小非负剩余。 对于固定的模m ，通常有下面的性质： 性质1.)(mod m b a ≡的充要条件是,a mt b t Z =+∈也即)(|b a m -。 性质2.同余关系满足以下规律： 〔1〕〔反身性〕)(mod m a a ≡； 〔2〕〔对称性〕假设)(mod m b a ≡，则)(mod m a b ≡； 〔3〕〔传递性〕假设)(mod m b a ≡，)(mod m c b ≡，则)(mod m c a ≡； 〔4〕〔同余式相加〕假设)(mod m b a ≡，)(mod m d c ≡，则)(mod m d b c a ±≡±； 〔5〕〔同余式相乘〕假设)(mod m b a ≡，)(mod m d c ≡，则)(mod m bd ac ≡； 注意：①反复利用〔4〕〔5〕，可以对多于两个的〔模一样的〕同余式建立加、减和乘法的运算公式 ； ②特别地，由〔5〕易推出：假设)(mod m b a ≡，c k ,为整数且0>k ，则)(mod m c b c a k k ≡； ③同余式的消去律一般并不成立，即从)(mod m bc ac ≡未必能推出)(mod m b a ≡，可是我们却有以下结果：假设)(mod m bc ac ≡，则⎪⎪⎭ ⎫ ⎝⎛ ≡),(mod c m m b a . 由此可以推出： 〔6〕假设,1),(=m c )(mod m bc ac ≡，则有)(mod m b a ≡，即在c 与m 互素时，可以在原同余式两边约去c 而不改变模. 〔7〕假设)(mod m b a ≡，d ｜m ，则)(mod d b a ≡； 〔8〕假设)(mod m b a ≡，0≠d ，则)(mod dm db da ≡； 〔9〕假设(mod )(1,2, ,)i a b m i k ≡=，则12(mod [,,,])k a b m m m ≡， 特别地，假设12,,,k m m m 两两互素时，则有12(mod )k a b m m m ≡⋅⋅⋅；
3 简化剩余系与欧拉函数#优选.
§3 简化剩余系与欧拉函数 定义 欧拉函数()n ϕ是一个定义在正整数集上的函数，()n ϕ的值等于系列 0,1, ,1n -中与n 互质的整数的个数。 ()()()()11,21,32,42, ϕϕϕϕ==== 当1n >时，()0.n n ϕ<<当p 为质数时，() 1.p p ϕ=- 定义 如果一个模m 的剩余类里的数与m 互质（在模m 的一个剩余类中，只要有其中一个数和m 互质，则该剩余类中所有的数就都与m 互质），就把它叫做一个与m 互质的剩余类. 在与m 互质的全部剩余类中，各取一个数所组成的一组数，叫做模m 的一个简化剩 余系. 定理1 模m 的一个简化剩余系含有()m ϕ个数. 证 模m 的全部剩余类是011,, ,m K K K -. 因为,0,1, ,1r r K r m ∈=-，所以对每个 ()01r r m ≤≤-，r K 是一个与m 互质的剩余类的充要条件是(), 1.r m =因此，在模m 的 全部剩余类011,, ,m K K K -中，与m 互质的全部剩余类是满足条件()01,,1 r m r m ≤≤-=的所有剩余类r K . 这样的剩余类公有()m ϕ个，故由简化剩余系的定义知，模m 的简化剩余系含有()m ϕ个数. 定理2 若()1, ,m a a ϕ是()m ϕ个与m 互质的整数，则()1, ,m a a ϕ是模m 的一个简化 剩余系的充要条件是它们两两对模m 不同余. 证 必要性 设()12,, ,m a a a ϕ是模m 的一个简化剩余系，则由简化剩余系的定义，这 ()m ϕ个数是取自模m 的不同剩余类的，故这()m ϕ个数两两对模m 不同余. 充分性 设与m 互质的()m ϕ个整数()12,, ,m a a a ϕ两两对模不同余. 因每个整数都与 m 互质，故每个整数都属于一个与m 互质的剩余类. 因这()m ϕ个整数两两对模m 不同余， 故这()m ϕ个整数分别属于不同的与m 互质的剩余类. 另一方面，与m 互质的剩余类共有 ()m ϕ个，故()12,,,m a a a ϕ分别属于这()m ϕ个与m 互质的剩余类，故()12,,,m a a a ϕ是 模m 的一个简化剩余系.
自考初等数论复习
初等数论 初等数论自学安排 第一章：整数的可除性（6学时）自学18学时 整除的定义、带余数除法 最大公因数和辗转相除法 整除的进一步性质和最小公倍数 素数、算术基本定理 [x]和{x}的性质及其在数论中的应用 习题要求3p ：2，3 ； 8p ：4 ；12p ：1；17p ：1，2，5；20p ：1。 第二章：不定方程（4学时）自学12学时 二元一次不定方程c by ax =+ 多元一次不定方程c x a x a x a n n =++Λ2211 勾股数 费尔马大定理。 习题要求29p ：1，2，4；31p ：2，3。 第三章：同余（4学时）自学12学时 同余的定义、性质 剩余类和完全剩余系 欧拉函数、简化剩余系 欧拉定理、费尔马小定理及在循环小数中的应用 习题要求43p ：2，6；46p ：1；49p ：2，3；53p 1，2。 第四章：同余式（方程）（4学时）自学12学时 同余方程概念 孙子定理
高次同余方程的解数和解法 素数模的同余方程 威尔逊定理。 习题要求60p ：1；64p ：1，2；69p ：1，2。 第五章：二次同余式和平方剩余（4学时）自学12学时 二次同余式 单素数的平方剩余与平方非剩余 勒让德符号 二次互反律 雅可比符号、 素数模同余方程的解法 习题要求78p ：2； 81p ：1，2，3；85p ：1，2；89p ：2；93p ：1。 第六章：原根与指标（2学时）自学8学时 指数的定义及基本性质 原根存在的条件 指标及n 次乘余 模2 及合数模指标组、 特征函数 习题要求123p ：3。 ➢ 第一章 整除 一、主要内容 筛法、[x]和{x}的性质、n ！的标准分解式。 二、基本要求 通过本章的学习，能了解引进整除概念的意义，熟练掌握整除 整除的定义以及它的基本