ka 三 1 (mod /?). (6)
因此，整数2,3,…，p_2可以两两配对使得式(6)成立.所以
2-3 ..... (p - 2) = 1 (mod p),
从而
123 ....... (p - 2)(/? - \)=p - 1 = -1 (mod p).
例3设m > 0是偶数，｛如,。2,…，如｝与｛伤，九…，仇,｝都是模m 的完全剩余系,证明：｛⑷+仞心+ /?2,…,4“ + ®”｝不是模加的完全剩 余系.
解：因为｛1,2,…，间与仙,如…,心都是模加的完全剩余系,所 以
二 吕.m(m +1) m
22% - =
三〒(mod m). (7) /=i /=1 2 2
同理
严. m Di = — (mod in).
(8)
r=l L 如果｛如+ bi, “2 + b 2,…,如+九｝是模m 的完全剩余系,那么也有 艺(©
+如三等(mod in).
i=i 2
联合上式与式(7)和式(8),得到
这是不可能的，所以｛如+ bl, U2 +九…,cim +加｝不能是模m 的完 2 2 2 (mod ni),
全剩余系.
二、缩系
在模皿的完全剩余系中，与m互素的整数所成的集合有一些特殊的性质，我们下而对它们做些研究.
1、定义1设R是模加的一个剩余类，若有处/?,使得(“,m)=l,
则称R是模力的一个简化剩余类.
显然，若R是模的简化剩余类，则7?中的每个整数都与用互素.
例如，模4的简化剩余类有两个：
用(4)={…,-7,-3,1,5,9,— },
7?3(4)= { --,-5,-1 ,3,7, 11 , --- }.
2、定义2对于正整数k,令函数仅Q的值等于模k的所有简化剩余类的个数，称於)为Eulb函数，或Eu心一°函数.
例如，容易验证仅2)=1,讽3) = 2,祕4) = 2,仅7) = 6.
显然，仅呦就是在加的一个完全剩余系中与m互素的整数的个数.
3、定义3对于正整数m,从模m的每个简化剩余类中各取一个数七，构成一个集合{力,兀2,…,兀酬”)}，称为模加的一个简化剩余系(或简称为简化系或缩系).
显然，由于选取方式的任意性，模加的简化剩余系有无穷多个.
例如,集合{9, -5, -3,-1}是模8的简化剩余系,集合{1,3, 5,7} 也是模8的简化剩余系，通常称最小非负简化剩余系.
4、定理1整数集合A是模加的简化剩余系的充要条件是
(i ) A中含有讽》个整数；
(ii)A中的任何两个整数对模加不同余；
(iii)A中的每个整数都与加互素.
5、定理 2 设“是整数，(a, m) = 1, B = [x\,X2, ■ • 是模zn 的简化剩余系,贝！I集合A = {ax\, ax2,心枷)}也是模m的一个缩系.
证明:显然,集合A中有讽加个整数.其次，由于(t/,772)=1,所以，对于任意的x,- (1
A中的每一个数都与加互素.最后，我们指出，A中的任何两个不同的整数对模加不同余.事实上，若有使得
a x f = ax n (mod in),
那么，因为(a, m)=所以x r =x r, (mod m),于是x f =x r,.由以上结论及定理1可知集合A是模m的一个缩系.
注：在定理2的条件下，若b是整数，集合
{ax\ + b, ax^ + /?,,•••, ax^m)+ b}
不一定是模加的简化剩余系.例如,取加=4, a= 1, b = l f以及模4 的简化剩余系{1,3}.
6、定理3 设m\y 7M2eN, (mi, mi) = L 又设
X ={.¥1,X2,---,X分别是模切与加2的缩系，则
A = { m\y + mix\ xeX f yeY }
是模m\ni2的缩系.
证明：若以X，与厂分别表示模加]与牝的完全剩余系，使得Xu X，, Yu厂，贝I」
A f = [ ni\y + zmx；xeX f f yeY' }
是模“也的完全剩余系.因此只需证明A'中所有与加"2互素的整数的集合R是集合A.显然，
若m\y + m/wR，贝'JO^iy + mix,= 1,所以(in\y + mix, m\) = 1,
于是("a, ")=1, (x, m\) = 1, xeX.
同理可得到ywY,因此/niy + m2xeA.这说明R^A.
另一方而，若n?i)? + 则xwX, yeY,即
(x,血1)=1, (y\ mi) = 1.
由此及伽，加2)= 1得到
(mox + m\y, m\) = 加1) = 1
以及
("?2兀 + 必1” "？2)=(必1幵"？2)= 1 ・
因为““与也2互素，所以(血2兀+ 加1加2) = 1，于是+ miyeR・因此A^R.综合以上，得到A = R.
7、定理4 设in, /?eN»伽,斤)=1,则(p(mn) =(p(m)(f)(n).
证明：这是定理3的直接推论.
8、定理5设斤是正整数，门丿2,…，以是它的全部素因数，则
(p(n) =〃(1 -—)(1 _ —…(1 _ —!—) = 〃口(1 _ —).
Pl Pl Pk P\n P
证明：设斤的标准分解式是由定理4得到
r=l
(p(n)=Y［i=l
对任意的素数P，讽严)等于数列1,2,…,〃呻与严(也就是与卩)互素的整数的个数，因此
殉产)=p a—［以］十-pg =P a (1-1),
p p
将上式与式(1)联合，证明了定理.
由定理5可知，仅町=1的充要条件是1或2.
例1设整数H>2,证明：
匸・_1
乙l^^n(p(n)9
l
a •刃)=i
即在数列1,2,…』中，与”互素的整数之和是卜讽心
解：设在1,2, -,77中与n互素的冷)个数是
a\. 02,…，a他幷” (CH. 7?) = h \ < Ui < n - \, 1 < / <(p(n), (n - cii, n) = L \因此，集合｛di, U2,…，伽”｝与集合也- di, n - U2,…，n - a(p(n)｝是相同
的,J •是⑷ + a? + …+ a2(如+ © +・・・+ a M) = n快",
d] +如+…+伽)=切呦.
因此
例2设〃是正整数，则
2>(〃)= n,
d\n
此处E是对n的所有正约数求和.
d\n
解：将正整数1,2,…丿按它们与整数”的最大的公约数分类，则
n n
n =Z1 = Z S 1 = Z Z 1 =工0(了)=工©(〃)・
/=1 diJi (tn)=t/ d\n . i n d\n " d\n
I —J —1
\例3设*N,证明：
(i )若"是奇数，则讽4”) = 2仅n)；
(ii)刃2)弓”的充要条件是n = 2*,辰N；
(iii)刃2)=卜的充要条件是n =刘,k, /eN；
(iv)若6 In,则刃2)<»
(v )若八-1与斤+1都是素数，n>4,贝^\(p(n) <1/?.
解：(i)我们有
仅4n)=仅2S) =(p(22)(ii)若n = 2*,贝lj
讽2°"(1冷)=2讥如
若(p(n) =-??,设斤= 2®i，2//?i，则由
2
仅町=讽2切J =讽2。讽小)=2*」刃21)
=丄2^皿丄皿
2 7J] 2 〃1
推出(p(n\) - 7?i，所以??1 = 1,即n = 2”；
(iii)若Ti = 2*3',则
刃2)=仅2")讽3，) = 2A (1 - ■|)3/ (1 -1) = 1 .
若(p(n) =-n，设n = 2k3'n[, 6Mi，则由
3
；"=(p(n)=卩(2*3,;»]) =(p(2k妙(3‘ 加(”i) = ；n——~
3 3 ?i|
推出(p(n\) = m,所以HI = 1,即71 = 2*3、
(iv)设n = 2k3'm，6IT?I，贝lj
讽n)=讽2。讽3')刃“)=”珈的)吕2智® =卜；
J J J
(V)因为”>4,所以料-1与n+1都是奇素数，所以n是偶数. 因为n-l>3,所以n-1与n+1都不等于3,当然不被3整除, 所以3 |弘因此6 b.再由上面己经证明的结论(iv),即可得到结论(v).
例 4 证明：若m, neN,则(p(inn) = (m, n)(p(\m, n])；
解：显然mn与⑷，川有相同的素因数，设它们是Pi (1 < / < k),
g)(mn) = — )(1 — ) (1 ---- ),
P\ Pl Pk
川)=[m, ”](1 - —)(1- —) (1 - —) o
Pi Pl Pk
由此两式及mn = (m, n)\m, n]即可得证.
三、Euler定理与Fermat小定理
1、定理l(Euler)设加是正整数,(«, ^)=1,则
c妙")三1 (mod tn).
证明：由第三节定理2,设｛心，也，…，X%)｝是模m的一个简化剩
余系,则｛。七,0X2, - , ox刃“)｝也是模m的简化剩余系,因此
ax\ax2- = X1X2,…x似加)(mod m),
= X]X2,…X做加)(mod m).(1) 由于(X[X2- - /n) = 1,所以由式(1 )得出
= 1 (mod in).
2、定理2(Fermat)设卩是素数，则对于任意的整数“，有
a p三a (mod p).
证明：若(a, p) = 1,则由定理1得到
a p~[ = \ (mod p) => a p = a (mod p).
若(d,p) > 1,则p\a,所以
a p = 0 = a (mod p).
例1设”是正整数，则5口" + 2" + 3“ + 4”的充要条件是4|几
解因为仅5) = 4,所以，由定理2
k4 = 1 (mod 5), 1 < ^ < 4.
因此，若n = 4^ + r, 0 < r < 3,则
l n + 2" + 3" + 4"三F + 2r + 3r + 4r = l r + 2r + (-2)r + (-1/ (mod 5), (2) 用r = 0, 1, 2, 3, 4分别代入式⑵即可得出所需结论.
例2设｛兀1,尤2,…，兀刃“)｝是模加的简化剩余系,贝I」
(xiX2- - -x^m))2 = 1 (mod m).
解记P = xix2-- x(p(m),则(P, m) = 1.又记
y, =— , 1 < / < 快n),
X i
则｛yiy,…,〉如)｝也是模加的简化剩余系,因此
0加) ^｛m｝ p
n A i = 口―(mod m),
/-I /-I x i
再由Eule定理，推出
P~ =P0‘”)= 1 (mod m).
例3设(a, m) = 1, Jo是使
a d = 1 (mod in)
成立的最小正整数，则
(i)災加);
(ii)对于任意的i, OGJSdo-l, iHj,有
a'^a j (mod m).(3) 解：(i)由Euler定理，Jo <(p(m｝,因此，由带余数除法，有
(p(m) = qdo + r, qwZ, q > 0, 0 < r < Jo・
因此，由上式及山的定义，利用定理1,我们得到
即整数7•满足
a r = 1 (mod in), 0 < r < Jo.
由〃o的定义可知必是r = o,即
(ii)若式(3)不成立，贝!J存在i, j, 0 < i,j • •
a1 = a} (mod th).
不妨设i > j.因为(",加)=1,所以
a1 ~j = 0 (mod m), 0这与〃。的定义矛盾，所以式(3)必成立.
例4设d, b, c,加是正整数，"?>1, (b9 m) = L并且
b a =\ (mod 加),b
c = \ (mo
d m),(4) 记〃 =(a, c),则b d = 1 (mod m).
解：利用辗转相除法可以求出整数x,)，，使得必+巧==〃，显然xy < 0.
若x>0, y < 0,由式(4)知
1 三b ax = ZbF = b\b c)-y = b d (mod m).
若xvO, y > 0,由式(4)知
1 = b cy = b d b ~ax = b d(b a) ~x = b J (mod tn).
例5设p是素数，p\b n-\, neN,则下而的两个结论中至少有
一个成立：
(i ) p\b d对于n的某个因数d(ii) p = 1 ( mod n ).
若2M, p > 2,贝!](ii)中的mod n可以改为mod 2n.
解：记〃=(n,p-l),由b n = 1, b p~l = 1 (mod/?),及例题4,有
b J= 1 (mod p).
若J <77,则结论(i)得证.
若〃=n,则n\p - 1,即p = 1 (mod /?),这就是结论(ii).
若2M, p > 2,则p=\ (mod 2).由此及结论(ii),并利用同余的基本性质,得到p = 1 (mod 2n).
注：例5提供了一个求素因数的方法，就是说，整数夕-1的素因数卩，是决-1 (当〃b时)的素因数，或者是形如如+1的数(当2M, p>2时，是形如2kn+ 1的数).
例6将211- 1 =2047分解因数.
解：由例5,若p I 211 - 1,则p = 1 (mod 22),即p只能在数列
23, 45, 67,…，22k + 1,---
中.逐个用其中的素数去除2047,得到
23 | 2047, 2047 = 23-89.
例7 将235 - 1 = 34359738367 分解因数.
解：由例5,若p|235 -l,则p是2—1=31或2?-1 = 127的素
因数，或者p三1 (mod 70).由于31和127是素数，并且
235- 1 =31-127-8727391,
所以，2站_1的另外的素因数p只可能在数列
71, 211, 281, (5)
中.经检验，得到8727391 =71 122921.
显然，122921的素因数也在31, 127或者数列(5)中.简单的计算说明，122921不能被31和127整除，也不能被数列(5)中的不超过712292K351的数整除，所以122921是素数，于是
235 - 1 =31-127-71-122921.
例8设n是正整数，记F n = 22" +1,则2仏三2 (mod几).
证：容易验证，当斤＜4时几是素数，所以，由Fermat定理可知结论显然成立.
当”25 时，有料+1V2", 2”+】丨2「记2?” =£2“+i,贝ij
2〃" -2 = 22 +1 _ 2 = 2(22 -1) = 2(2A- - 1)
° 〃十 1 I yr+1 QH
= 2((2- )A -1) = 22! (2- -1) = Q2(2- +1),
其中2i与Qi是整数.上式即是2仏三2 (mod F”).
注1：我们己经知道，E是合数，因此，例8说明，一般地，Fermat 定理的逆定理不成立.即若有整数d,(U, 77)=1,使得
a n~l = 1 (mod/?), (6) 并不能保证n是素数.
注2：设”是合数，若存在整数°, («,«)= 1,使得式(6)成立，则
称n是关于基数"的伪素数.
四、小结
五、作业
补充：证明Wilson定理的逆定理.
P60： ex3> ex6^ ex9、ex!2> exl4^ exl7> ex 18
联赛新高一暑假第13讲初等数论(2)
同余是大数学家高斯的一个天才发明，这个符号使得原来难以表述的很多数论问题表述起来简单清晰.利用同余符号，可以方便地处理各种复杂的数字相对于另一数的余数这一类问题.本讲将着重讲述同余的基本性质，并利用这些性质来解决各类同余的典型问题.此外，基于同余，还给出了剩余系与完系的概念.尽管联赛大纲没有明确对这两个概念作要求，但是有了对剩余系的基本认识后对很多问题处理起来会更为方便. 同余的定义： 设m 是一个给定的正整数，如果两个整数a 与b 用m 除所得的余数相同，则称a 与b 对模m 同余，记作)(mod m b a ≡，否则，就说a 与b 对模m 不同余.（用≡符号上面加一个斜线来表示，类似不等符号）. 显然，(mod ),)|()a b m a km b k Z m a b ≡?=+∈?-（ ； 剩余类与完全剩余系（简称完系）： 我们可以将所有的整数按模m 分类．例如：按模2分类，可将所有整数分成两类，模2余1的分成一类，即奇数；模2余0的一类，即偶数．按模3分类，可分成3k 、31k +、31k -三种类型；等等. 剩余类的定义：设m 为一给定的正整数，则全体整数可以分为m 个集合0K ，1K ，…，1m K -，这里{|,(mod )},0,1,...,1r K x x Z x r m r m =∈≡=-．我们称0K ，1K ，…，1m K -为模m 的剩余类． 在模m 的m 个剩余类中分别取一个数，共取出m 个，我们把这m 个数成为模m 的一组完全剩余系,简称完系.例如：0,1,2，…,1m -就是一组完系，显然，它们两两对模m 不同余. 性质1：每个整数在且仅在模m 的一个剩余类中． 性质2：若0a ，1a ，…，1m a -是模m 的一个完系，而(,)1a m =，b Z ∈，则0aa b +，1aa b +，…， 1m aa b -+也是模m 的一个完系．（此性质可自行证明，联赛范围内一般不需要掌握） 同余的性质非常之多，以下仅列举最常用的一些， （1）自反性：(mod )a a m ≡(a 为任意自然数) （2）对称性：若(mod )a b m ≡，则(mod )b a m ≡ 本讲概述 第13讲 初等数论(2) 同余
初等数论教学大纲
《初等数论》教学大纲 Elementary number theory 一、本大纲适用专业 数学与应用数学。 二、课程性质与目的 1. 课程目标 初等数论是数学与应用数学专业一门专业选修课。通过这门课的学习，使学生获得关于整数的整除、不定方程、同余、原根与指数的基本知识，掌握数论中的最基本的理论和常用的方法，加强他们的理解和解决数学问题的能力，为今后的实际工作打下良好基础。 2. 与其它课程的关系 本课程是初等数学研究、C语言程序设计A，近世代数等课程的后续课程。 3. 开设学期 按培养方案规定的学期开设。 三、教学方式及学时分配 四、教学内容、重点 第一章整数的可除性 1. 教学目标 理解整数整除的概念、最大公约数的概念、最小公倍数的概念，掌握带余除法与辗转相除法；理解素数与合数的概念；理解和掌握素数的性质、整数关于素数的分解定理、素数的求法；掌握函数[x]和 {x} 的性质。 2. 教学内容 （1）整数整除、剩余定理：带余除法与辗转相除法；最大公约数的概念、性质及求最大公约数的方法；最小公倍数的概念、性质及最小公倍数的求法。（2）素数与合数：素数与合数的概念、素数的性质、整数关于素数的分解定理、素数
的求法；函数[x] {x} 的性质及其应用。 3. 教学方法 讲解教学。 4. 本章重点 辗转相除法，整数的素数分解定理。 5. 本章难点 求最大公因子的方法。 第二章不定方程 1. 教学目标 理解不定方程的概念，理解和掌握元不定方程有整数解的条件，会求一次不定方程的解。 2. 教学内容 （1）一次不定方程，多元一次不定方程的形式，多元一次不定方程有解条件，求简单的多元一次不定方程的解。（2）二元一次不定方程有整数解的条件，求一次不定方程的解。 3. 教学方法 讲解教学。 4. 本章重点 多元一次不定方程有解条件，二元一次不定方程有整数解的条件。 5. 本章难点 不定方程的整数解的形式，求多元不定方程的整数解。 第三章同余、同余式 1. 教学目标 理解整数同余的概念，理解和掌握同余的基本性质、整数具有素因子的条件函数相关性质；理解剩余类与完全剩余系的概念，理解欧拉函数的定义及性质；掌握欧拉定理、费马定理、孙子定理。 2. 教学内容 （1）整数同余：整数同余的概念、同余的基本性质；整数具有素因子的条件；利用同余简单验证整数乘积运算的结果。（2）剩余类与完全剩余系：剩余类与完全剩余系的概念；判断剩余系的方法；欧拉函数的定义及性质；欧拉定理、费马定理。（3）同余式的基本概念、孙子定理。 3. 教学方法 讲解教学。 4. 本章重点 剩余系的判定，欧拉函数的定义及性质，中国剩余定理。 5. 本章难点
初等数论教案第二节剩余类与完全剩余系
第二节剩余类与完全剩余系 第三节缩系 教学目的：1、掌握剩余类与完全剩余系的定义与基本性质； 2、掌握缩系的定义与基本性质； 3、证明及应用Wilson定理； 4、证明及应用Fermat小定理、Euler定理的证明及应用； 5、掌握Euler函数计算方法及其基本性质. 教学重点：1、剩余类与完全剩余系的基本性质； 2、证明及应用Wilson定理； 3、证明及应用Fermat小定理； 4、掌握Eule『函数计算方法及其基本性质. 教学课时：8课时 教学过程 一、剩余类与完全剩余系 由上一节我们知道，同余关系满足自反性、对称性、传递性，即对于整数集来说，同余是一个等价关系.这样，可以按同余关系将所有的整数分类. 1、定义1给定正整数加，对于每个整数「，0而且，属于同一剩余类的任何两个整数对模皿是同余的，不同剩余类中的任何两个整数对模”?是不同余的. 例如，模5的五个剩余类是 K()(5)={…，—10,—5, 0,5, 10,…} &(5)={ ..,-9,-4 J,6 JI,-.- } 心5)={ -,-8,-3,2,7,12,--- } 心5)={ -,-7,-2,3,8,13,--. } 辰(5)={…，_6,—1,4,9,14,…} 2、定义2设〃是正整数，从模加的每一个剩余类中任取一个 数尢(0 < z < m - 1 称集合｛xo, 口…丸加-1｝是模加的一个完全剩余系(或简称为完全系)・ 由于占的选取是任意的，所以模加的完全剩余系有无穷多个，通常称 (i)｛0,1, 2,…，加一1｝是模m的最小非负完全剩余系; —~ + 1, •••, — 1, 0, 1, •••, — }(当2 I AH)或(ii) 乎…—…耳}(当2") 是模血的绝对最小完全剩余系. 例如,集合｛0,6,7, 13,24｝是模5的一个完全剩余系,集合｛0, 1,2, 3,4｝是模5的最小非负完全剩余系. 3.定理1整数集合A是模〃的完全剩余系的充要条件是 (i) A中含有血个整数; (ii)A中任何两个整数对模血不同余.
高二数学竞赛辅导-初等数论
高二数学竞赛辅导－初等数论 一、奇数、偶数、质数、合数 1. 整数的奇偶性 （1）奇、偶数具有如下性质：奇数±奇数=偶数；偶数±偶数=偶数；奇数±偶数=奇数；偶数×偶数=偶数； 奇数×偶数=偶数；奇数×奇数=奇数； （2）奇数的平方都可表为81m +形式，偶数的平方都可表为8m 或84m +的形式（m Z ∈）. （3）任何一个正整数n ，都可以写成2m n l =的形式，其中m 为非负整数，l 为奇数. 2. 质数与合数、算术基本定理 定理：任何大于1的整数A 都可以分解成质数的乘积，若不计这些质数的次序，则这种质因子分解表示式是惟一的，进而A 可以写成标准分解式：1212n a a a n A p p p =? （*）.其中 12,n i p p p p <<< 为质数，i α为非负整数，1,2,3,i n = . 注：1:（合数的因子个数计算公式）若1212n n A p p p α α α = 为标准分解式，则A 的所有因子（包括1和A 本身）的个数等于12(1)(1)(1)n ααα+++ 推论2：（互质元素个数的计算公式）若1212n n A p p p α α α = 为标准分解式，则在1到A 中与A 的互质的元素的个数等于12111 (1)(1)(1)n A p p p --- 。 二、整除 1．整数的整除性 定义一：（带余除法）对于任一整数a 和任一整数b ，必有惟一的一对整数q ，r 使得r bq a +=， b r <≤0，并且整数q 和r 由上述条件惟一确定，r 称为b 除a 的余数.若0=r ，则称b 整除a ， 或a 被b 整除，或称b a 是的倍数，或称a b 是的约数（又叫因子），记为a b |.否则，b | a . 由整除的定义，不难得出整除的如下性质： （1）若.|,|,|c a c b b a 则（2）若.,,2,1,,| ,|1 n i Z c b c a b a i n i i i i =∈∑=其中则 （3）若c a |，则.|cb ab 反之，亦成立.（4）若||||,|b a b a ≤则.因此，若b a a b b a ±=则又,|,|. （5）a 、b 互质，若.|,|,|c ab c b c a 则 （6）p 为质数，若,|21n a a a p ??? 则p 必能整除n a a a ,,,21 中的某一个.特别地，若p 为质
初等数论答案到第四章
第一章 整数的可除性 §1 整除的概念·带余除法 1．证明定理3 定理3 若12n a a a ，，，都是m 得倍数，12n q q q ，，，是任意n 个整数，则1122n n q a q a q a ++ +是m 得倍数． 证明： 12 ,,n a a a 都是m 的倍数。 ∴ 存在n 个整数12,, n p p p 使 1122,, ,n n a p m a p m a p m === 又12,, ,n q q q 是任意n 个整数 1122n n q a q a q a ∴++ + 1122n n q p m q p m q p m =+++ 1122()n n p q q p q p m =++ + 即1122n n q a q a q a ++ +是m 的整数 2．证明 3|(1)(21)n n n ++ 证明 (1)(21)(1)(2n n n n n n n ++=+++- (1)(2)(1)(n n n n n n =+++-+ 又 (1)(2)n n n ++，(1)(2)n n n -+是连续的三个整数 故3|(1)(2),3|(1)(1)n n n n n n ++-+ 3|(1)(2)(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 不全为0 ∴在整数集合{}|,S ax by x y Z =+∈中存在正整数，因而有形如ax by +的最小整
初等数论教学大纲(本科)
初等数论教学大纲 （本科） 哈尔滨师范大学数学系
初等数论(本科) 教学大纲 说明 《初等数论》是师范本科学校数学与应用数学专业的一门重要专业课，数学与应用数学专业的学生学习一些初等数论的基础知识可以加深对数的性质的了解与认识，便于理解和学习与其相关的一些课程。是在学生进入四年级后开设的一门课程。通过对《初等数论》的教学，使学生掌握初等数论的最基本的内容，使学生在掌握其基本理论的同时为从事中学数学竞赛工作提供宏观理论的积累，初等数论是研究整数最基本的性质，是一门重要的数学基础课。 初等数论开设的目的： 通过这门课的学习，使学生获得关于整数的整除性、不定方程、同余式、原根与指标及不定方程的基本知识，掌握数论中的最基本的理论和常用的方法，加强他们的理解和解决数学问题的能力，为今后的学习奠定必要的基础。 1、国际奥林匹克数学竞赛中所占初等数论内容很多，学好初等数论对于培养学生进行奥林匹克数竞赛的培训工作提供理论的知识储备。 2、培养学生初步的科研能力，因为初等数论是数学中理论与实践结合得最完美的基础课程，近代数学中的很多数学思想、概念、方法与技巧都是从整数的性质的深入研究而不断丰富和发展起来的。 确定《初等数论》的教学内容应依据初高中教学实际，立足于培养学生的数学思想、方法和技巧，掌握竞赛数学中初等数论的主要理论和进一步提高和学习的基本理论，因而整个课程分为整除、同余、同余式、不定方程和原根指标几部分。这样处理有助于形成学生完善的数学知识结构，进而从根本上提高学生的素质。 根据教学计划规定，本课程教学时数为48学时，其中讲授课和习题课共48学时，本课程安排在第七学期，周学时4，具体分配如下： 1．整除12学时； 2．同余8学时； 3．同余方程18学时； 4．不定方程4学时； 5．原根和指标5学时。 大纲内容 一、整除 （一）教学目的 通过本章的教学，使学生掌握整除的性质、带余数除法、辗转相除法，掌握最大公因数和最小公倍数
高中数学竞赛——数论
高中数学竞赛 数论 剩余类与剩余系 1.剩余类的定义与性质 (1)定义1 设m 为正整数，把全体整数按对模m 的余数分成m 类，相应m 个集合记为：K 0,K 1,…,K m-1,其中K r ={qm+r|q ∈Z,0≤余数r ≤m-1}称为模m 的一个剩余类( (2)2.(1)a r ，得m 个数特别地,完全为偶数时,,2-m (2)证明:即证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),则有 aa i +b ≡aa j +b(modm),也矛盾! (ⅲ)设m 1,m 2是两个互质的正整数,而x,y 分别遍历模m 1,m 2的完系,则
m2x+m1y历遍模m1m2的完系. 证明:因x,y分别历遍m1,m2个整数,所以,m2x+m1y历遍m1m2个整数. 假定m2x/+m1y/≡m2x//+m1y//(modm1m2),其中x/,x//是x经历的完系中的数,而y/,y//是y经历的完系中的数.因(m1,m2)=1,所以,m2x/≡m2x//(modm1),m1y/≡m1y// (modm2),从而x/≡x//(modm1),y/≡y//(modm2),矛盾! 3. (1).在与模m的一个 (2) (ϕ m ) x1≡x2 ,则a1,a2,…,aφ(m)是模m的一个既约剩余系. 证明:因a1,a2,…,aφ(m)是)m(ϕ个与m互质的整数,并且两两对模m不同余, 所以,a1,a2,…,aφ(m)属于)m(ϕ个剩余类,且每个剩余类都与m互质,故a1,a2,…,aφ(m) 是模m的一个既约剩余系. (ⅴ)设m1,m2是两个互质的正整数,而x,y分别历遍模m1,m2的既约剩余系,
数论中的完全剩余系
在数论中，完全剩余系是一种重要而有趣的概念。简而言之，完全剩余系是指在某个取模运算下，能够包含所有剩余类的一个子集。理解和应用完全剩余系对解决一些数论问题至关重要。 首先，让我们来理解一下什么是剩余类。在数论中，当我们用一个整数a去除以一个正整数n时，会得到商和余数。那么余数的集合{0, 1, 2, ..., n-1}称为模n的剩余类。例如，当我们用5去除以3时，商为1，余数为2，所以余数2就是模3的剩余类之一。 接下来，我们来看一个具体的例子。假设我们要找出模5的完全剩余系。那么我们需要选取一些整数，使得它们的余数分别是0, 1, 2, 3和4。可以很容易地得出这样一组完全剩余系：{0, 1, 2, 3, 4}。因为对于任意一个整数，它一定是这五个整数中的一个。 对于模n的完全剩余系的求解，有一个重要的定理——厄拉托斯特尼斯筛法。厄拉托斯特尼斯筛法是一种求素数的方法，在求出素数的同时，我们也可以得到模n的完全剩余系。该算法的基本思想是从小到大枚举所有可能的数，然后删除它的所有倍数，直到找不到更多的素数为止。 通过厄拉托斯特尼斯筛法，我们可以得到模n的完全剩余系。这对于解决一些数论问题非常有帮助。例如，当我们需要求解一个同余方程时，可以通过求解模n的完全剩余系，然后找到满足方程的剩余类。 另外，完全剩余系还有一个重要的性质——平方剩余。当我们对一个数求平方时，会得到一个更小的数。因此，我们只需要关注完全剩余系中的平方数对应的剩余类。平方剩余的研究在数论中有着广泛的应用，例如在密码学中的重要性就不言而喻。 总结起来，数论中的完全剩余系是一类重要的数学概念。它能够帮助我们解决一些数论问题，找到同余方程的解，研究平方剩余等。厄拉托斯特尼斯筛法是求解模n的完全剩余系的一种有效方法。通过深入研究完全剩余系，我们可以进一步发展数论的理论，并应用于实际问题中。
《初等数论》教学大纲
课程名称：初等数论（Elementary Number Theory） 《初等数论》教学大纲 一、课程说明 “初等数论”课程是数学与应用数学专业（师范）的一门专业选修课。数学与应用数学专业的学生学习一些初等数论的基础知识可以加深对数的性质的了解与认识，便于理解和学习与其相关的一些课程。 通过这门课的学习，使学生获得关于整数的整除性、不定方程、同余式、原根与指标及简单连分数的基本知识，掌握数论中的最基本的理论和常用的方法，加强他们的理解和解决数学问题的能力，为今后的学习奠定必要的基础。 本课程属于数学与数学专业（师范）的专业选修课。 本课程的教学时间安排：每周2节课，计划教学周为16周，总课时数32学时，其中实践时数0学时。 本课程总学分数为2学分。 本课程安排在第5学期开设。 二、学时分配表
三、教学目的与要求 初等数论是研究整数性质的一门学科，历史上遗留下来没有解决的大多数数论难题其问题本身容易搞懂，容易引起人的兴趣，但是解决它们却非常困难。本课程的目的是简单介绍在初等数论研究中经常用到的若干基础知识、基本概念、方法和技巧。 通过本课程的学习，使学生加深对整数的性质的了解，更深入地理解初等数论与其它邻近学科的关系。 四、教学内容纲要 第一章整数的可除性（ 6学时） 目的要求： 1、理解整数整除、公因子、公倍数的概念及相关性质，理解剩余定理，熟练掌握用剩余定理求最大公因子、最小公倍数的方法。 2、理解素数与合数的概念、素数的性质，理解整数的素数分解定理，会用筛法求素数。 3、了解函数[x]与{x}的概念、性质，n!的素数分解、组合数为整数的性质。 难点：定理的证明处理方法，定理的灵活运用。 讲授内容：
《初等数论》课程标准
《初等数论》课程标准 1.课程说明 (1)课程性质：本门课程是数学教育专业的核心课、必修课课程。通过本课程的教 学，介绍初等数论的基础知识，使学生掌握整除理论的基础，其基本内容是算术基本理论 和最大公约数理论；掌握初等数论的核心，即同余理论的基本知识；并能运用整除理论和 同余理论来求解几类最基本的不定方程；掌握连分数等有关概念、性质及其应用，为学生 以后继续学习数论或从事教学工作打下基础。 (2)课程任务：本课程主要针对中小学数学教育教师及相关等岗位开设，主要任务 是培养学生在 中小学数学教育教师岗位的数学课程教学能力，要求学生掌握中小学数学教 师在代数方面的专业理论基础知识、基本技能及思想方法和解决相关问题的能力。 (3)课程衔接：在课程设置上，前导课程有高等代数，后续课程有数学解题研究等。 2 .学习目标 通过本课程的教学，学习初等数论的基础知识，使学生掌握初等数论的基本内容和方 法。能培养学生的逻辑思维能力，为学习其它的数学课程打下良好的基础 3 .知识目标 通过这门课的学习，使学生获得关于整数的整除性、不定方程、同余式、原根与指标 及简单连分数的基本知识。 (1)掌握带余除法定理及证明，掌握余数的概念； (2)掌握公因数、最大公因数的概念及相关的性质；掌握素数与合数的概念，掌握算 术基本定理； (3)掌握同余关系的概念及等价的另外两定义；熟练掌握同余关系的基本性质；掌握 完全剩余系、 简化剩余系的概念； (4)掌握欧拉定理及其证明；掌握费尔马定理；利用它们解决求余数、判断整除性等 问题； (5)掌握平方剩余平方非剩余的概念，了解欧拉判别条件； (6)掌握指数及其基本性质 (7)判定原根存在性 (8)掌握连分数的定义及其基本性质； 《初等数论》课程标准 课程编码(34970) 制定( 〕 审核( ) 批准( ) 承担单位〔师范学院) 制定日期() 审核日期() 批准日期()
《初等数论》教学大纲
《初等数论》教学大纲 一、课程名称 《初等数论》 二、课程的性质 数学与应用数学，信息与计算科学专业的限制性选修课。 三、课程的教学目的 初等数论是研究整数最基本性质，是一门十分重要的数学基础课。它以算术方法为主要方法来研究整数本身所包含的丰富而重要的内涵与特征。同时，初等数论是数学中“理论与实践”相结合得十分紧密的课程。近代数学中许多重要的思想，概念，方法与技巧都是从对整数性质的深入研究而不断丰富和发展起来的。它在计算机科学、代数编码，信号的数字处理，组合数学，离散数学，计算方法等领域中有着广泛的应用。本课程的教学目的是使学生对整数形成清楚而正确的认识，并经过本课程的学习，使他们掌握初等数论的基本思想方法，以培养和增强学生运用数学手段分析和解决实际问题的能力。 每一章节的教学目标： 第一章 整数的可除性（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* 单素数的平方剩余与平方非剩余
初等数论课程教学大纲新
《初等数论》课程教学大纲 一、课程的性质与地位 “初等数论”课程是宿迁高等师范学校数学学科专业必修的一门课程。数学专业的学生学习初等数论的基础知识可以加深对数的性质的了解与认识，便于理解和学习与其相关的一些课程。数论是研究整数性质的一门很古老的数学分支，其初等部分是以整数的整除性为中心的，包括整除性、不定方程、同余式、连分数、素数（即整数）分布以及数论函数等内容，统称初等数论（elementary number theory）。 初等数论的大部份内容早在古希腊欧几里德的《几何原本》中就已出现。欧几里得证明了素数有无穷多个，他还给出求两个自然数的最大公约数的方法，即所谓欧几里得算法。我国古代在数论方面亦有杰出之贡献，现在一般数论书中的“中国剩余定理”正是我国古代《孙子算经》中的下卷第26题，我国称之为“孙子定理”。 近代初等数论的发展得益于费马、欧拉、拉格朗日、勒让德和高斯等人的工作。1801年，高斯的《算术探究》是数论的划时代杰作。高斯还提出：“数学是科学之王，数论是数学之王”。可见高斯对数论的高度评价。 由于自20世纪以来引进了抽象数学和高等分析的巧妙工具，数论得到进一步的发展，从而开阔了新的研究领域，出现了代数数论、解析数论、几何数论等新分支。而且近年来初等数论在计算器科学、组合数学、密码学、代数编码、计算方法等领域内更得到了广泛的应用，无疑同时间促进着数论的发展。 二、课程教学目标 初等数论是研究整数性质的一门学科，历史上遗留下来没有解决的大多数数论难题其问题本身容易搞懂，容易引起人的兴趣，但是解决它们却非常困难。本课程的目的是简单介绍在初等数论研究中经常用到的若干基础知识、基本概念、方法和技巧。 数论是以严格和简洁著称，内容既丰富又深刻。通过这门课的学习，使学生获得关于整数的整除性、不定方程、同余式、数论函数及简单连分数的基本知识，掌握数论中的最基本的理论和常用的方法，加强他们的理解和解决数学问题的能力，为今后的学习奠定必要的基础。 三、教学基本内容及要求
剩余类与剩余系
飞同餘，剩餘類與剩餘系 (a) 同餘的性質： (1) a= b (mod m), 尸d (mod m),貝U a - c= b_d (mod m) 且ac= bd (mod m)。 (2) a= b (mod m), c N,貝U ac= bc (mod cm)。 (3) a= b (mod m), n迂N 且nm ,貝U a= b (mod n)。 (4) 若a= b (mod m),貝U (a, m)= (b, m)。 (5) 整數a, b,貝U ab= 1 (mod m) iff (a, m) = 1。 (b) 剩餘類： m為正整數，將全體整數按照對模m的餘數進行分類，餘數為r (0 —r 一m -1)的所有整數歸為一類，記為K r (r=0,1,..,m-1)，每一類K r均稱為模m的剩餘類(同餘類)。 剩餘類K r是數集K r={mq+r|m是模，r是餘數，q Z} = {a|a・Z且a三r(modm)}, 它是一個以m為公差的(雙邊無窮)等差數集。並具有如下的性質： (1) Z 二K0_• K, _• K2一. - K mJ且心 - K j = 一(i = j )。 ⑵對於任意的Z，有唯一的r0使y K r0。 (3)對於任意的a、b Z , a、b K r = a=b(modm) (c) 完全剩餘系： 設K。，K1,…，K m-1是模m的全部剩餘類，從每個K r中取任取一個數a r,這m個數a0, a1,…， a m-1組成的一個數組稱為模m的一個完全剩餘系。 (d) 簡化剩餘系： 如果一個模m的剩餘類K r中任一數都與m互質，就稱K r是一個與模m互質的剩餘 類。在與模m互質的每個剩餘類中，任取一個數(共(m)個)所組成的數組，稱為 模m的一個簡化剩餘系
初等数论 讲稿：完全剩余系
第十五讲完全剩余系 你好，欢迎和我一起学习完全剩余系。我们知道，如果两个整数a，b被正整数m除的余数相同，那么a，b关于模m同余。 根据同余的概念，我们可以把全体整数用同一个正整数去除，把余数相同的放在一个集合，那么会得到多少个集合，集合里面的元素有什么特点呢？这就是我们接下来要学习的内容。 下面我们先看定义1，设m是正整数，全体整数用m去除，所得的余数有0,1,2,一直到到m-1，余数相同的数放在同一个集合里，那么我们就得到m个集合：k0，k1，一直到km-1，其中，k0里面的元素是a等于mq+0，即被m除余数为零的集合，k1里面的元素是被m除余数为1的集合，km-1里面的元素是被m除余数为m-1的集合。 我们把k0，k1,一直到km-1称为模m的剩余类。 在模m的每一个剩余类k0，k1，一直到km-1中，我们取一个数，就可以得到m个整数，a0，a1，am-1，那么我们称a0,a1,一直到am-1为模m的一个完全剩余系。 由模m的完全剩余系的定义，我们知道一组整数要构成模m的一个完全剩余系，必须有m个整数，而且这m个整数要在不同的剩余类里面，也就是下面的定理1，m个整数作成模m 的一个完全剩余系的充要条件是它们两两对模m不同余。 比如所有的整数用1去除，得到的余数都为零，从而模1的剩余类只有一个k0，等于...,-2，-1，,0，1，2,... 我们在k0里面任取一个数，就构成了模1的一个完全剩余系，比如-2构成模1的一个完全剩余系，1也构成模1的一个完全剩余系，可以看到模1的完全剩余系有无数个，但每一个完全剩余系所含元素的个数都是1。在模1的完全剩余系里面，有两个非常特殊的完全剩余系，一个叫模1的非负最小完全剩余系，一个叫模1的绝对最小完全剩余系。所谓模1的非负最小完全剩余系，就是在k0里面取非负的最小的数，就是零，所以模1的非负最小完全剩余系为零。所谓模1的绝对最小完全剩余系，即取k0里面绝对值最小的数，就是零，所以模1的绝对最小完全剩余系为零。 类似的模2的剩余类有k0,k1，模2的完全剩余系也有无数个，模2的非负最小完全剩余系是0,1；模2的绝对最小完全剩余系是0,1或0，-1. 模3的剩余类有k0,k1，k2。模3的非负最小完全剩余系是0,1，2；模3的绝对最小完全剩余系是0,1，-1. 模4的剩余类有k0,k1，k2,k3。模4的的非负最小完全剩余系是0,1，2,3；模4的绝
第二节 完全剩余系
初等数论 第二章 同 余 第二节 完全剩余系 由带余数除法我们知道，对于给定的正整数m ，可以将所有的整数按照被m 除的余数分成m 类。本节将对此作进一步的研究。 一、知识与方法 定义1 给定正整数m ，对于每个整数i ，0 ≤ i ≤ m - 1，称集合 R i (m ) = { n |n ≡ i (mod m )，n ∈Z } 是模m 的一个剩余类。 显然，每个整数必定属于且仅属于某一个R i (m )（0 ≤ i ≤ m - 1），而且，属于同一剩余类的任何两个整数对模m 是同余的，不同剩余类中的任何两个整数对模m 是不同余的。 例如，模 5的五个剩余类是 R 0(5) = { , -10, -5, 0 , 5, 10, }， R 1(5) = { , -9 , -4 , 1 , 6 , 11, }， R 2(5) = { , -8 , -3 , 2 , 7 , 12, }， R 3(5) = { , -7 , -2 , 3 , 8 , 13, }， R 4(5) = { , -6 , -1 , 4 , 9 , 14, }。 定义2 设m 是正整数，从模m 的每一个剩余类中任取一个数x i （0 ≤ i ≤ m - 1），称集合{x 0, x 1, ,x m - 1}是模m 的一个完全剩余系（或简称为完全系）。 由于x i 的选取是任意的，所以模m 的完全剩余系有无穷多个，通常称 (ⅰ) {0, 1, 2, , m - 1}是模m 的最小非负完全剩余系； (ⅱ) ）（当m m m |22 ,,1,0,1,,12}{ -+-或 ） （当m m m |22 1,,1,0,1,,21}{/---- ,是模m 的绝对最小完全剩余系。 例如，集合{0, 6, 7, 13, 24}是模5的一个完全剩余系，集合{0, 1, 2, 3, 4}是模5的最小非负完全剩余系。 定理1 整数集合A 是模m 的完全剩余系的充要条件是 (ⅰ) A 中含有m 个整数； (ⅱ) A 中任何两个整数对模m 不同余。 【证明】
初等数论知识点总结
《初等数论》总结 姓名 xxx 学号 xxxxxxxx 院系 xxxxxxxxxxxxxxx 专业 xxxxxxxxxxxxxxx
个人感想 初等数论是一门古老的学科，它对于数的性质以及方程整数的解做了深入的研究，是对中等数学数的理论的继续和提高。 有时候上课听老师讲解一些例题，觉得比较简单，结果便是懂非懂地草草了之，但是过段时间做老师留下的一些相似的课后练习时，又毫无头绪，无从下手。这就是上课的时候没做到全神贯注地去听，所以课下的时间尤为重要，一定做好复习巩固的工作。 老师讲课的方法也十分好，每次上课都会花二十分钟到半个小时来对上节课的知识帮助我们进行回顾，我想很多同学都喜欢并适合这种教学方式。 知识点总结 第一章整数的可除性 1. 2性质： (1) 传递性质)； (2) 闭。若反复运用这 一性质，易 则对 于任意的整 更一般， (3)
若p 是质数，若n a p |，则a p |； (6)(带余数除法)设b a ,为整数，0>b ，则存在整数q 和r ，使得r bq a +=，其中b r <≤0，并且q 和r 由上述条件唯一确定；整数q 被称为a 被b 除得的(不完全)商，数r 称为a 被b 除得的余数。注意：r 共有b 种可能的取值：0,1，……， 1-b 。若0=r ，即为a 被b 整除的情形； 易知，带余除法中的商实际上为⎥⎦ ⎤ ⎢⎣⎡b a （不超过b a 的最大整数），而带余除法的核 心是关于余数r 的不等式：b r <≤0。证明a b |的基本手法是将a 分解为b 与一个整数之积，在较为初级的问题中，这种数的分解常通过在一些代数式的分解中 取特殊值而产生 若n 是正整数，则))((1221----++++-=-n n n n n n y xy y x x y x y x Λ； 若n 是正奇数，则))((1221----+-+-+=+n n n n n n y xy y x x y x y x Λ；（在上式中用y -代y ） (7)如果在等式∑∑===m k k n i i b a 1 1 中取去某一项外，其余各项均为c 的倍数，则这一项也 是c 的倍数； (8)个连续整数中，有且只有一个是n 的倍数； (9)任何n 个连续的整数之积一定是n!的倍数，特别地，三个连续的正整数之积能被6整除； 第二章 不定方程 1. 定义：二元一次不定方程的一般形式是ax +by = c ，其中a ,b ,c 是整数 2. 定理： (1) 不定方程有整数解的充要条件为 (a,b) | c. (2) 设 是方程的一组解，则不定方程有无穷解，其一切解可表示成
夏建新--初等数论
初等数论 江苏省南菁高级中学 夏建新 一、整除 ⑴带余除法：对于任一整数a 和任一非零整数b ，必有惟一的一对整数q 和r ，使得a ＝bq ＋r ，0≤r ＜b ，且q 和r 由上述条件惟一确定。 若r ＝0，则称b | a 。 ⑵部分性质： ①若c | b ，b | a ，则c | a ②若c | a ，d | b ，则cd | ab ③若c | a ，c | b ，则c |（ka ＋nb ）；若c | a ，c |╲b ，则c |╲（a ＋b ） ④若ma | mb ，则a | b ⑤若a ＞0，b ＞0，b | a ，则b ≤a ⑥若n ∈N*，则（a －b ）|（a n －b n ）。若n 为奇数，则（a ＋b ）|（a n ＋b n ）。若n 为偶数，则（a ＋b ） |（a n －b n ） ⑦任意n 个连续正整数的乘积必能被n ！整除。 ⑶当（a ，b ）＝1时，称a 、b 互素（互质）。有： ①已知（a ，c ）＝1，若a | bc ，则a | b ；若a | b ，c | b ，则ac | b ②p 为质数，若p | ab ，则p | a 或p | b ③[a ，b ]·（a ，b ）＝ab ④（a ，b ）＝（a ，b －ac ）＝（a －bc ，b ）对任何整数c 成立 ⑤（裴蜀定理）存在整数x 、y ，使ax ＋by ＝（a ，b ） ⑥m （a ，b ）＝（ma ，mb ） ⑦若（a ，b ）＝d ，则),( d b d a ＝1 ⑧若a | m ，b | m ，则[a ，b ] | m ⑨m [a ，b ]＝[ma ，mb ] ⑩费尔马小定理：p 是素数，则p |a p －a 若另上条件（a ，p ）＝1，则p |a p －1－1 例1、求所有的正整数n ，使得8n ＋n 可以被2n ＋n 整除。（2009年日本数学奥林匹克） 例2、设n ≥m ≥1，m 、n 为整数，证明：(m ，n )n ·C m n 为整数。（2000年普特南） 例3、求所有的正整数n ，使n 能被所有不大于n 的正整数整除。 例4、已知a ，b ，c 为两两互质的正整数，且a 2|(b 3＋c 3)，b 2|(a 3＋c 3)，c 2|(a 3＋b 3)，求a ，b ，c 的值．（2011年东南数学奥林匹克） 例5、求有序三元正整数组（a ，b ，c ）的个数，其中[a ，b ]＝1000，[b ，c ]＝2000，[a ，c ]＝2000。（[x ，y ]表示x 、y 的最小公倍数） 例6、证明：对所有的非负整数n ，77n ＋1至少是2n ＋3个质数（不一定互不相同）的乘积。（2007年第36届美国数学奥林匹克） 例7、是否存在奇数n （n ≥3）及n 个互不相同的质数p 1，p 2，…，p n ，使得p i ＋p i ＋1（i ＝1，2，…，n ，p n ＋1＝p 1）都是完全平方数？请证明你的结论。（2011年中国西部数学奥林匹克） 二、同余 1、定义：设m 是正整数，叫做模，若m |（a －b ），称a ，b 对模m 同余，记作a ≡b （mod m ） 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 ） ④若a ≡b （mod m ），c ≡d （mod m ），则a ±c ≡b ±d （mod m ），ac ≡bd （mod m ）
2 剩余类及完全剩余系
§2 剩余类及完全剩余系 定义 设m 是一个给定的正整数，()0,1, ,1r K r m =-表示所有形如 ()0,1,2,qm r q +=±±的整数组成的集合，则称011,, ,m K K K -为模m 的剩余类. 定理1 设0110,,, ,m m K K K ->是模m 的剩余类，则 〔ⅰ〕每一整数必包含于*一个类里，而且只能包含于一个类里； 〔ⅱ〕两个整数,x y 属于同一类的充分必要条件是()mod .x y m ≡ 证 〔ⅰ〕设a 是任意一个整数，则由带余除法，得,0a qm r r m =+≤<，故.r a K ∈ 故每一整数必包含于*一类里. 又设 ,r a K ∈且r a K '∈，这里0,0r m r m '≤<≤<，则存在整数,q q '使得 于是，|,|.m r r m r r ''--但是0r r m '≤-<，故0,0,.r r r r r r '''-=-== 〔ⅱ〕设,a b 是两个整数，并且都在r K 内，则存在整数12,q q 分别使得 故()mod .a b m ≡ 反之，假设()mod a b m ≡，则由同余的定义知，,a b 被m 除所得的余数一样，设余数都为()0r r m ≤<，则a 和b 都属于同一类r K . 定义 在模m 的剩余类011,, ,m K K K -中，各取一数,0,1, ,1j j a C j m ∈=-，此m 个数 011,,,m a a a -称为模m 的一个完全剩余系. 推论m 个整数作成模m 的一个完全剩余系的充分必要条件是这m 个整数两两对模m 不同余. 证 充分性 设12,, ,m a a a 是m 个两两对模m 不同余的整数. 由定理1知，每个整数i a 必 在模m 的m 个剩余类011,, ,m K K K -中*一剩余类里，且只能在一个剩余类里. 因 12,,,m a a a 是m 个两两对模m 不同余的整数，故有定理1得，12,, ,m a a a 分别属于不同 的剩余类，故12,,,m a a a 是模m 的一个完全剩余系. 必要性 设12,, ,m a a a 是模m 的一个完全剩余系，则由完全剩余系的定义得，这m 个
