联赛自招修订版数论解答
关于威尔逊定理的详细证明
威尔逊（Wilson ）定理：设p 为质数，则)(mod 1)!1(p p -≡-。 1. 数论倒数：若≡ab 1(modm),则的数论倒数是关于模与m b a
2. 若必有数论倒数关于模则m a m a ,1),(=。这由欧拉定理或裴蜀定理可保证
3. 质数p 的一个缩系为：.1,2,,3,2,1--p p 则：)(m od 11),(mod 11m p m -≡-≡
4. 主要证明：{})(mod 1,,,2,,3,2p xy x y A y p A x ≡≠∈-=∈?使得且存在唯一的
5. 因为),(mod 1,.2,1),(p xz z p x ≡∴=知存在由：可以证明: 1),(=p z 所以在模p 的缩
系中，必存在{}1,,3,2,1-∈p y ，使得)(mod p y z ≡，所以)(mod 1p xy ≡ 6. 若1),(mod 1,1-≠≡=p y p x y 矛盾，同理则。所以，A y ∈ 7. 若)(mod 1,1),(mod 1,2
p p x p x y x -≡≡=则，矛盾，所以y x ≠
8. 现在证明y 的唯一性：设又有)(mod 1,11p xy y ≡使得，则)(mod 1p xy xy ≡，易知：
)(mod 1p y y ≡，由2)2(1-≤-≤--p y y p 知1y y =，唯一性得到证明。于是有
9. {})(mod 1,,,2,,3,2p xy x y A y p A x ≡≠∈-=∈?使得且存在唯一的 ，即集合A 中的数两两配对，成为数论倒数，乘积为1
=-)!1(p )(mod 1)1()]2(32[1p p p -≡-?-??? 证毕
第一章 初等数论
第一节 数的整除性
1.1 整除
典例分析
例1．证明：10010
2000
个被1001整除。 证明：10010
2000
个=1101001,1)10(110366732001
+=+=+，)1001(mod 1103-≡，故
)1001(mod 1)10(6673-≡，故结论成立
例2．对正整数n ，记)(n S 为n 的十进制表示中数码之和。证明：n |9的充要条件是)(|9n S 。
证明：==--0121a a a a n m m 0111
11010
a a a m m +?++?-- ，而)9(m o d 110≡k ，对即可证明模9n
例3．设1≥k 是一个奇数，证明：对于任意正整数n ，数k k k n +++ 21不能被2+n 整除。 提示：倒叙相加求和
例4．设n m ,是正整数，2>m ，证明：（12-m ）（12+n
）。
证明：设m r r mq n <≤+=0,，))12(mod(1212)),12(mod(12-+≡+∴-≡m
r
n
m
m
又12-m >12+r
,(以下略)
例5．设正整数d c b a ,,,满足cd ab =，证明：d c b a +++不是质（素）数。
例6．求出有序整数对（n m ,）的个数，其中991≤≤m ，991≤≤n ，n m n m +++3)(2
是完全平方数。
提示：两个相邻的完全平方数之间没有完全平方数
例7．证明：若正整数b a ,满足b b a a +=+2
232，则b a -和122++b a 都是完全平方数。
证明: ]221)[()(22
2
2
2
b a b a b b b a b a ++-=?=-+-,
同理：)331)((2
b a b a a ++-=，)331)(221()(2
2
2b a b a b a b a ++++-= ，
又1)331,221(=++++b a b a ，均为完全平方数与所以
b a b a 331221++++ 例8．证明不存在正整数n ，使2n 2+1，3n 2+1，6n 2+1都是完全平方数。
提示：此题是否定语气的命题，可用反证法，假设存在n ，使他们都是完全平方数，则乘积也是完全平方数，若介于两个相邻的完全平方数之间，则矛盾
1．证明：如果p 和2+p 都是大于3的素数，则6是1+p 的因子。 提示：对p 选个模分类讨论 2．设0≥>n m ，证明：)12
(|)12(22-+m
n
；
证明：)),12(mod(1222+-≡n
n
又n
m n
m
-=2
22)2(2，)),12(mod()1()
2(22
22+-≡--n
n
m n
m n
立证
3．已知n 为正奇数，求证：1236|60---n
n
n
。
提示：因为涉及幂次，建议利用数论的有力工具：同余
5. 已知x 、y 、z 是三个大于1的正整数，且xyz 整除(xy -1)(yz -1)(zx -1)，求x 、y 、z 的所有 可能的值。（13华约） 提示：限定范围，合理筛选。设z y x ≥≥，则 3,31<<-++≤z xy zx yz xy xyz （略） 1.2 质数与合数
典例分析
例1 设不是质数的正整数，证明：数为大于
114
5++n n n 提示：因式分解
例2 考察下面的数列：101，10101,1010101，…。问：该数列中有多少个质数？ 证明：利用因式分解公式 ))((1221
----++++-=-n n n n n
n
y xy y x x
y x y x
可得：n
)10()10(10122
22
++++ =9
)
110)(110(11+---n n ，9与每个括号内的数都不
能约为1，是合数（除非n=1），只有一个质数101
例3 求所有的正整数n ，使得
12
)
1(-+n n 是一个质数 提示：分类则明了
例4 对任意正整数n ，证明：存在n 个连续正整数，他们都是合数 （提示：123)1(!???-?= n n n ）研究：k n ++)!1(
例5 设n 为大于2的正整数，证明：存在一个质数，满足：!n p n << 提示：设小于n 的质数只有有限个
1 设是一个合数的正整数，证明：为大于
n
n n 414+ 证明: n 为偶数显然，12+=k n 时，2
1244)2(4++=+k n n n 配方法
2 求使得x x x 为质数的所有整数271242
-- 提示：因式分解法5,4,2,1--=x
3 能否将1,2,3，…，50两两配对，使得所配的25对数之和两两不同，且都是质数？
证明：假若成立，则在1到99有25个不同的质数，事实上，从1到100仅有2,3,5,7,11,13,17,19，23,29，31,37,41,43,47,53,59,61,67,71,73,79,83,89,97共25个质数，但前面无2，故不成立
4 是否存在3个不同的质数,,,r q p 使得下面的整除关系都成立？
,2
d p qr + ,2d q rp + d r pq +2
其中;10)1(=d 11)2(=d
证明：由对称性，不妨设：,1r q p <<<则：r q q p ≤+≤+1,1，三数中r q ,较大，
可构造同向不等式：d p p p qr d p ≤+++≥≥+23),2)(1(2
。10=d 时，无有，
11=d 时，三数 2,3,5
点评：限定范围，合理筛选
5 设为质数是质数，求证：为正整数，且p p p
12- 提示：反证法
6 正整数m
k
n
k
m
n
k m k n n m k n m 证明：满足：.,,,
证明：由已知：m
n m
k k
m k
n k n n m )()(,)()(，由整除的传递性既得 7 设bc ad c a cd ab c a c a d c b a +-+-≠证明：都是整数，且,,,,, 提示：被除式作差即可
8 设,1263,,,d c b a d c b a >>>都是质数，且 17492
2
2
2
=-+-d c b a 求2
2
2
2
d c b a +++的所有可能值
证明：因为有四个质数，可先考虑质数的分类：奇质数，偶质数1749是奇数，故2=d
1753222=+-c b a ，5,2≥>c d c ，基于“限定范围”的想法，将222c b a +-缩小 22222221)12(6)12(8168)13(1753c c c c b b c b b +++++≥+++=+-+≥
得：173844332
≤+c c ，7 6 2 2 321728?==-b a （1），又b a ,有相同 的奇偶性，37,333,11,2≥=>≥>a b a b c b ，48≥+b a ，将（1）分解 532,32=-?=+b a b a ，其它情形不符合，11,43==b a 1.3 因数与倍数 典例分析 例1． 设y x ,是正整数，y x <且667=+y x ，它们的最小公倍数是最大公约数的120倍， 求y x ,。 解：设d y x =),(，则nd y md x ==,，其中1),(=n m 且n m <，于是mnd y x =],[。 所以?????==+120667d mnd nd md 即?????=?=+5322923)(3mn d n m )2()1( 由n m <及（2）可得： ?? ????====;60 2 ;1201n m n m ?? ????====;30 4 ;403n m n m ?? ????====;206;245n m n m ??????====12 10 ;158n m n m 。 由（1）可知只能取? ?????====;158 ;245n m n m 从而23=d 或29，故552,115==y x 或435,232==y x 。 例2．设0,>n m ，)(|2 2 n m mn +，则n m =。 提示：设d n m =),(，证明相互整除与n m 例3．设正整数c b a ,,的最大公约数是1，并且 c b a ab =-，证明b a -是一个完全平方数。 证明: d b a c d d b b d a a d b a =-====1111,1),(,,,),(证明设： 例4． b a ,都是正整数，是否存在整数q p ,使得对任意的正整数n ，na p +与nb q +互质？ 证明;d b b d a a d b a 11,,),(===设：，n d nb q na p =++),(，则可证)(11qa pb p -，存在 1,11=+y b x a y x ，使（以下略） 例6．求出所有的正整数对),(n m ，使得1 13-+mn n 是一个整数。 解：由于1)1,(3 =-mn m 且)1(|11|13 3 3 +-?+-n m mn n mn 11|13 3 3++--?m n m mn 1|13+-?m mn ，所以n m ,是对称的。不妨设n m ≥。 当n m =时，则211 111 1*223=?∈-+=-+-=-+n N n n n n n n n ，从而n m =＝2； 当n m >时，若1=n 时，则有2|1-m ，所以2=m 或3； 若2≥n 时，由于113-+mn n 是一个整数，从而*N k ∈?使得)1)(1(13 --=+mn kn n （商式至多是n 的一次式）即=-1kn <-+113mn n 1 1 1123-+ =-+n n n n ， 所以1-kn ＜1 1-+ n n 。又由于2≥n ，* N k ∈，所以1=k 。 1)1)(1(13 3 +--=--=+mn n mn mn n n ，从而*21 2 111N n n n n m ∈-++=-+= 得2=n 或3，所以5=m ； 综上知所有的),(n m 为（2,2）,(2,1),(1,2),(3,1),(1,3),(5,2),(2,5),(5,3),(3,5). 法2： 例7．已知* ,,,N n m b a ∈，且2,1),(>=a b a ，试问m m n n b a b a ++|的充要条件是m n |吗？ 分析：因为)()(n k n k n n n n k k k b a b b a a b a -----+=+，所以?++k k n n b a b a |n k n k n n b a b a --++|； 又)()(n r n r n n n n r r r b a b b a a b a ---+-+=-，所以?++r r n n b a b a |n r n r n n b a b a --++|； 令)0(n r r nq m <≤+=，则有?++++r nq r nq n n b a b a |r n q r n q n n b a b a +-+--+)1()1(| ???+++-+- r n q r n q n n b a b a )2()2(|r q r n n b a b a )1(|-++ 又因为r n >，所以<-+r q r b a )1(n n b a + 从而上式0=?r 且q 为奇数，即m m n n b a b a ++|的充要条件是m n |且n m 为奇数。 例8．我们知道9123=+有1个质因子，且12|33 2+； 19351312 332 ?==+有2个质因子，且|33122 3+ ……………… 如此下去，我们可以猜想：,* N k ∈ 123+k 至少有k 个质因子，且|31+k 123 +k 。试证明之。 证明：令k a ＝12 3+k ，则k a ＝k k b 13+，即要证k b 是整数且有1-k 个质因子。下用数学归 纳法证明k b 是整数。 1=k 时，结论显然； 假设k n =时，成立； 当k n =＋1时，因为=+1k a (k a －1)3+1=k a 3－3k a 2＋3k a ； 因为|3 1 +k k a ，所以|32+k 1+k a ，即1+k b 是整数。 下证1+k b 至少有k 个质因子。 =+1k a 23+k 1+k b ＝k a 3－3k a 2＋3k a ＝(13+k k b )3－3(13+k k b )2＋3(13+k k b ). 因为1+k b ＝k b (133 121 2+-++k k k k b b )，令=k c 1331212+-++k k k k b b ，则1+k b ＝k b k c 由于(k c ,3)=1，所以(k c ,k b )=1，从而k c 必有异于k b 质因子的质因子， 所以1+k b 至少有k 个质因子。 证毕！ 练习题 1．若m N n ,∈是奇数，则1)12,12(=+-n m 。 证明：))12(mod(12)),12(mod(12-≡∴-≡m mn m m ，又))12(mod(12+-≡m n 所以：))12(mod(12 +-≡m mn ，而 1)12,12(=+-mn mn ，所以结论成立 2．若17|(2a +3b ),试证：17|(9a +5b ). 提示：k b a 1732=+，所以：b k a 3172-=代入上式 3．设a n ,是正整数，若n a 不是整数，则必为无理数。 提示：反证法，假设为有理数 4. 记F n ＝n 22＋1，试证：(F n ,F m )=1,这里n m ≠. 证明：设k n m k k n m 222)2(2,0,=≠+=，))12(mod(12)),12(mod(122222+≡∴+-≡n m n n 即：)12()12 (22-+m n ，又1)12,12(22=-+m m ，故结论成立 1.4 算数基本定理 例1 一个走廊里依次排列着编号为1,2,3，…，2014的灯共有2014盏。一好动生作了下面 的2014次操作：对的倍数的灯为次操作时，将所有编号 该生第k k k ,20141≤≤的开关都拉了一下，问：最后还有多少等是亮着的？ 提示：第k 号灯亮，当且仅当k 有偶数个约数，即k 为非完全平方数 例2 设n 为正整数，证明：数1221 22++-n n 有至少n 个不同的质因子 解析：原式=1 1 1222 22 12 2)2(----+?+n n n 依次进行因式分解 练习题 1 设n 是大于1的正整数，证明：n 为合数的充要条件是存在正整数,,,,,b a n y x b a +=使得 1=+b y a x 证明;?若d b b d a a d b a 11,,),(===，代入上式得：y a x b b da 1111+= 易证;y b x a 11,,所以，2≥d ， ?设q q p pq n +-==)1(，通过代入构造：1,1-=-=q y p x 2 整数1),(,1,,,2 2 =++=-bd ac b a bc ad d c b a 证明： 满足 拉格朗日恒等式 3 设n 为大于13的正整数，且的最小值不互质，求与n n n 6513+- 84=n 4 已知正整数的倍数或是证明；的最小公倍数为53,,,,abcd d c b a d c b a +++ 提示: ,abcd d c b a +++由对称性，不妨假设d c b a ≤≤≤≤1，先证四数不全相等，估计个范围d d c b a d 4<+++<，所以,3,2d d d c b a =+++依次讨论 5 求所有的正整数1)1)(1(11,,,2 2 2 2 2 +=++++c b a b a c b a 都是质数，且满足和使得 （1,2,3），（2,1,3） 第二节 同余 典例分析 例1 求所有的质数使得),(,,r q p r q p ≤≤2 2 2 ,,,,,q rp q rp p qr p qr r pq r pq ++++++都是质数 证明：奇偶性分析知：,2=p 3≥q ,2 2 2,2,4,2,2,2q r q r qr qr r q r q ++++++,根据取模求质数的方法，并注意到，若模3，则,4,2++qr qr 属于不同类，故可设23,13++=k k qr 均不成立，故k qr 3=，…对取模分类r …（2,3,5） 例2 设n 是正奇数，证明数：12,,12,12,12132-----n 中必有一个数是n 的倍数 解析：因为n 是正奇数，故1)2,(=k n ，利用抽屉原理 例3 设n 为大于1的正整数，且 1！，2！，…，n!中任意两个数除以n 所得的余数不同。证明：n 是一个质数 直接理解：显然有!n n ，若n 不是质数，有两种情形： （1）n q p pq n <<<=1,，则)!1(-≤=n pq n ，所以)!1(-n n ，矛盾 （2）2 22,1,p p n p p n <<<=，所以，)!1()2(-≤n p p ，即)!1(,)!1(22 2--n p n p 即， 矛盾 例4 设整数的倍数是证明：满足：27,))()((,,z y x z y x x z z y y x z y x ++++=--- 证明：由于字母具有优美的对称，思考也理想化， (1) 若互不同余模3,,z y x (2) 若有两个同余模3,,z y x ，分此两类进行讨论即可 例5．试解方程：57 15865-=?? ????+x x 。 分析，由左边知， 5 7 15-x 是个整数，由取整函数的性质：1][][+<≤x x x 解此不等式，即可 解：因为左边是整数，因而右边的分式也应该是整数，所以 086557155715865=?? ????++--=??? ???--+x x x x 于是0409081=?? ? ???-x ，从而14090810<-≤x ，故4090810<-≤x 。 但是 5 7 15-x 是整数，故7515+=t x ，Z t ∈，代入前面的不等式，得Z t t ∈<-≤,4030390，直接观察即知1,0=t ，于是5 4 ,157=x 。 例6．数100！的十进位制表示中，未尾连续地有多少位全是零？ 解：命题等价于100！最多可以被10的多少次方整除。因为5210?=因而100！中2的指数大于5的指数，所以100！中5的指数就是所需求出的零的位数。 由24420510051002=+=??? ???+??????=α即可知100！的未尾连续地有24位全是数码零。 例7．试求2633 )46257(+被50除所得的余数。 解：由于2633 )46(+x 是关于x 的整系数多项式，而)50(mod 7257≡，于是知 2633)46257(+)50(mod )467(2633+≡。 又注意到)50(mod 14972-≡≡，故2633 )46257 (+)50(mod )467(2633+≡26162)467)7((+?≡ )50(mod 353)467()467)1((2626262616≡≡+≡+?-≡ 又)50(mod 7725024335 -≡-≡≡，所以2633 )46257 (+3)7(3)3(555?-≡?≡ )50(mod 292137)7(22≡-≡??-≡ 注意到50290<<，因而29就是所求的余数。 例8．设10 1010 =a ，计算某星期一后的第a 天是6星期几？ 解；星期几的问题是被7除求余数的问题。由于)7(mod 310≡，于是)7(mod 23102 2 ≡≡， )7(mod 163231033-≡≡?≡≡，因而)7(mod 1106≡。 为了把指数a 的指数10 10写成r q +6的形式，还需取6为模来计算10 10。为此我们有 )6(mod 410≡，进而有)6(mod 441022≡≡，)6(mod 441033≡≡，依次类推，有)6(mod 41010≡，所以)6(mod 461010+≡q 从而，)7(mod 4310110)10(10 44464 6≡≡?≡?≡≡+q q q a 这样，星期一后的第a 天将是星期五。 例9．求所有的素数p ，使142 +p 与162 +p 也是素数。 分析：要使142 +p 与162 +p 也是素数，应该是对p 除以某个数素q 的余数进行分类讨论，最后确定p 只能是这个素数。由于只有两个数，所以q 不能太大，那样讨论起来也不会有什么效果，试验3,2=q 发现对本题不起任何效果，现对5=q 展开讨论。 解：设=u 142+p ，=v 162 +p ，且}4,3,2,1,0{,,15∈∈+=r Z k k p 若1=r 或4时，)5(mod 12 ≡p ，u 142 +=p )5(mod 014≡+≡； 若2=r 或3时，)5(mod 42 ≡p ，=v 162 +p )5(mod 0124≡+≡； 即0≠r 时，v u ,为5的倍数且比5大，不为质数。故0=r ，此时5=p ， 1011452=+?=u ；1511652=+?=v 都是素数。 即可题有唯一解5=p 。 注：要使几个数同为质数，一般是对这几个数也合乎以某一质数的余数来确定，如 4,2,++p p p 均为质数，可得p 只能为3，由于这是p 的一次式，故三个数就模3，而二 次式对三个数就模5，四个数一般就模7了。 例10．求满足7|512|=-n m 的全部正整数n m ,。 分析：如果712 5=-m n ，两边4mod ，得)4(mod 31≡，这是不可能的； 如果7512=-n m ，而n m ,中有一个大于1，则另一个也大于1，3mod 得 )3(mod 1)1(≡--n ，故n 为奇数，8mod ，得)8(m od 15-≡-n ，而)8(m od 152≡，n 为 奇数，从而)8(mod 15-≡-，矛盾！ 所以1==n m 为唯一解。 注：在解不定方程时，往往要分情况讨论，也常常利用同余来导出一些性质求出矛盾！ 例11 求所有满足z y x 17158=+的正整数三元组),,(z y x 解析:(1)你能一眼看出它的特解吗？ （2,2,2） （2）尝试：模3，得 y x ,同奇偶性 （3）模4，得y 为偶数 （4）模5，不易观察 （5）模7（注意到方程左边有数8）左边余2，右边)7(mod 317z z ≡，由费尔马小定理 )7(mod 136≡，所以，26+=t z ，z 为偶数，得z y x ,,同为偶数 （6）原方程可化为)62261517)(1517(2,17152 r r r r m r n m +-==+ 所以，,2 1517,215176s m r r s r r -=+=-解得1612217---+=s m s r ，由左右两边奇偶性知， 01=-s ，所以，1,21517==-r r r ，2≥r 时无解，2=z ，由原方程知，2≤y 例12．数列}{n a 满足：.,2 36 457,12 10N n a a a a n n n ∈-+= =+ 证明：（1）对任意n a N n ,∈为正整数；(2)对任意1,1-∈+n n a a N n 为完全平方数。 （2005年全国高中数学联赛试题） 证明：（1）由题设得,51=a 且}{n a 严格单调递增.将条件式变形得 ,36457221-=-+n n n a a a 两边平方整理得0972 121=++-++n n n n a a a a ① 0972 112=++-∴--n n n n a a a a ② ①-②得1111111()(7)0,,70n n n n n n n n n n a a a a a a a a a a +-+-++=-+-=>∴+-=? .711-+-=n n n a a a ③ 由③式及5,110==a a 可知，对任意n a N n ,∈为正整数. （2）将①两边配方，得.)3 (1),1(9)(2 1112 1n n n n n n n n a a a a a a a a +=-∴-=+++++ ④ 由③式119()n n n n n a a a a a +-+=-+≡()1()mod3n n a a --+ ∴1n n a a ++≡()10(1) n a a -+≡0（mod3）∴ 13 n n a a ++为正整数，④式成立. 11-∴+n n a a 是完全平方数. 例13．若 ) 12(1 3-+n n n 可以写成有限小数，那么自然数n 的值是多少？ 解：由于1)13,(=+n n 若13+n 与12-n 互素，则分数) 12(1 3-+= n n n p 是既约分数； 若13+n 与12-n 不互素，设它们的公约数为d ，且1>d ，设db n da n =-=+12,13，则5)12(3)13(2)32(=--+=-n n b a d ，故13+n 与12-n 的公约数是5，此时分数p 的分子、分母只有公约数5。 由于p 可以写成有限小数，故约分之后p 的分母除了2,5以外，没还有其它的公约数，因此 m k n n 52)12(?=-。 因为12-n 是奇数，1)12,(=-n n ，故???=-=m k n n 5 122，即1521+=+m k 。 由于15+m )4(mod 2≡故)4(mod 22 1 ≡+k ，从而0=k ，即1,0==n m ， 故只有p n ,1=才是有限小数。 练习题 1． 试求5010 )19991998 (+被25除所得的余数。 余数24 2． 设的值求也是质数且都是质数))((,11,7,,22q p p q q p pq q p q p ++++ 解析：先对质数作奇偶性分析：知一奇一偶，必有一个为2，然后对另一个取模分类： 221 3． 的最小值求成等差数列且个质数是55432154321,,,,,,5p p p p p p p p p p p <<<< 5，11,17,23,29 4． 求最大的正整数132:,+n k n k ，满足使得存在正整数 2=k 5． 证明：对每个正整数n ，数都是合数17819+?n 解析：从特殊性看问题 （1） 从n 8，考虑模7或9，经尝试，由模9得，若n 为偶数时，原式为合数 （2） 21317819,1=+?=n 为合数，若)13(mod 1781917819+?≡+?n ，则可 只要)13(mod 88≡n 即可，由费尔马小定理13=n 即可，但归纳知：)13(mod 184 ≡ 所以，14+=k k 结论成立 最后剩下34+=k k ，考虑特例9845178193 =+?，取模5，问题全部解决 6． 求下列方程的正整数解：（1）2 12y x =+ （2）2 12y x =- （3）235=-y x 答案（1）3==y x （2）1,1==y x （3）1,1==y x 2.2 奇数与偶数 例1 已知n n n n 40,1312,证明： 都是完全平方数与且为正整数++ 提示：奇数的平方模8余1，研究模5的情形 例2 设质数从小到大依次排列为，的正整数证明：对任意大于n p p 1.,,21 数121-n p p p 和121+n p p p 数都不是完全平方数 利用完全平方数的性质：模3余0,1，模4余0,1 例3 若a ab b a ，则记为完全平方数的正整数是使得1,+≈b 。证明：若a ≈b 则存在正整数,c 使得：a ≈c ，b ≈c 通过因式分解可找到b a m c ++=2 例4 求最小的正整数满足： 使得存在整数n x x x n ,,,,21 15994 4241=+++n x x x 解析：因为159964 >，故数不会太大，)16(mod 1,0),8(mod 1,04 2 ≡∴≡x x ， )16(mod 151599≡，故15≥n ，当15=n 时，只要)16(mod 14≡i x ，从奇数中找，只能取 1,3,5. 15995314 44=?+?+?z y x ，解得：15,1,12,2=∴===n z y x 例 5 设正整数都是证明：并且满足z y z x y x z y x z y x z y x --+=+=,,,1 11,1),,(,,完全平方数 法1：设最大公约数法 法2：利用分比定理 例6 求所有的正整数对),(b a ，得使16,163 3++++ab b ab a 都是完全立方数 证明：不妨设b a ≤，完全立方数夹在完全立方数之间，这是“限定范围”，然后筛选 1==b a 练习题 1.设a 是任意整数，试证下面形式的数都不是完全平方数：（1）25+a ；（2）652 +a 。 解：（1）225≡+a 不同余2 x )5(mod ； （2）652+a ≡222≡+a 或3)5(mod ，但02 ≡x 或1)5(mod 。 2.设12)12()12(.1,,2--->n m m n m m n m 的充要条件是： 证明：为正整数 证明：先证? 设n m m )12(-，则,)12(k m n m -= ]12) 2() 2)[(12 (1) 2(123 22 21 2++++-=-=----mk mk mk mk mk n m m m = B A ?， 项和是12-m B ),(mod 1)2(A i mk ≡所以)(mod A A B ≡，B A 再证?设m r r mq n <≤+=0,，0),(mod 1212 12=-≡-=-+r A r r mq n 推知，故 mq n =，C A C A A q m n 易证,]1)2[(121?=++?=-- 3 求所有的正整数组 !!!!),,,,(w z y x w z y x =++使得 提示：2,1,≤+≥<≤≤ωωω推知故z z y x （2,2,2,3） 4 设是一个完全平方数证明：且为正整数m m n m mn n m ,,,2 2 ++ 证明：由条件：0,2 2 2 2 =++-=++m m kmn n kmn m n m 即 （1）有解，关于n 的方程 )44()(4)(2 2 2 --=+-=?m m k m m m km ， 若m 是奇数，m 与括号内的数互质，m 为完全平方数 若m 偶数，（1）知：2 n 为偶数，分析知，m 是4的倍数，设s m 4=， )14(162--=?s s k s ，s 与括号内的数也互质，s 也是完全平方数 5 求最小的正整数n ，使得在十进制之下，3 n 的末三位数字是888. 192=n 6 设正整数12,1->n n 证明： 既不是完全平方数，也不是完全立方数。 7 设都是完全平方数证明：为整数且为正整数c b a c b a c b a ,,,,,,++ 8 已知正整数c 是一个奇合数，证明：存在正整数c a c a a 8)12(,13 ,2+--≤ 且使得：是一个完全平方数 9 圆周上有800个点，依顺时针方向标号为1,2，…，800.它们将圆周分为800个间隙，现在选定某个点，，将其染上红色，然后进行下属操作：如果第k 号染成了红色，那么依顺时针方向转过k 个间隙，将所到达的点染成红色。问：依次规则，圆周上最多有多少个点被染成了红色？证明你的结论 第三节 进位制与数字问题 典例分析 例1．将一个十进制数字2004（若没有指明，我们也认为是十进制的数字）转化成二进制与八进制，并将其表示成多项式形式。 分析与解答 分析：用2作为除数（若化为p 进位制就以p 作为除数），除2004商1002，余数为0；再用2作为除数，除1002商501余数为0；如此继续下去，起到商为0为止。所得的各次余数按从左到右的顺序排列出来，便得到所化出的二进位制的数。 解： 故210)01111101010()2004(=，246789104212121212121214102?+?+?+?+?+?+?=+?； 同理，有810)3274()2004(=，48782834102234+?+?+?=+?。 处理与数字有关的问题，通常利用定义建立不定方程来求解。 例2．求满足3 )(c b a abc ++=的所有三位数abc 。 （1988年上海市竞赛试题） 解：由于999100≤≤abc ，则999)(1003 ≤++≤c b a ，从而95≤++≤c b a ； 当5=++c b a 时，3 3 )521(1255++≠=； 当6=++c b a 时，3 3 )612(2166++≠=； 当7=++c b a 时，3 3 )343(3437++≠=； 当8=++c b a 时，3 3 )215(5128++==； 当9=++c b a 时，3 3 )927(7299++≠=； 于是所求的三位数只有512。 例3．一个四位数，它的个位数字与百位数字相同。如果将这个四位数的数字顺序颠倒过来（即个位数字与千位数字互换，十位数字与百位数字互换），所得的新数减去原数，所得的差为7812，求原来的四位数。 （1979年云南省竞赛题） 解：设该数的千位数字、百位数字、十位数字分别为z y x ,,，则 原数y z y x +++=1010102 3 ① 颠倒后的新数x y z y +++=1010102 3 ② 由②－①得7812＝)(90)(999y z x y -+- 即)()(10)(10)(10)(1118682 x y x z x y y z x y -+-+-=-+-= ③ 比较③式两端百位、十位、个位数字得6,8=-=-x z x y 由于原四位数的千位数字x 不能为0，所以1≥x ，从而98≥+=x y ，又显然百位数字 9≤y ，所以76,1,9=+===x z x y 。所以所求的原四位数为1979。 例4．递增数列1,3，4,9，10,12,13，……是由一些正整数组成，它们或是3的幂，或是若个不同的3的幂之和，求该数列的第100项。 （第4届美国数学邀请赛试题） 解：将已知数列写成3的方幂形式： ,333,33,33,3,33,3,30127126025240131201++=+=+==+===a a a a a a a 易发现其项数恰好是自然数列对应形式的二进制表示： 即 ,2227,226,225,24,223,22,210 1 2 2 2 2 1 1 ++=+=+==+=== 由于100＝2 5 6 2222)1100100(++= 所以原数列的第100项为9813332 56=++。 例5．1987可以在b 进制中写成三位数xyz ，如果7891+++=++z y x ，试确定所有可能的z y x ,,,和b 。 （1987年加拿大数学竞赛试题） 解：易知19872 =++z yb xb ，从而1962)1()1(2 =-+-b y b x 即109321962])1)[(1(2 ??==++-y x b b 由10>b 知91>-b 。由119622 -≥b 知451963<≤b 故4519<- 又因为109 321962 ??=有12个正约数，分别为1,2，3,6， 9,18,109,218,327,654,981,1962，所以181=-b ，从而19=b 。 又由1119919519872 +?+?=知.11,9,5===z y x 例6．设n 是五位数（第一个数码不是零），m 是由n 取消它的中间一个数码后所成的四位数，试确定一切n 使得 m n 是整数。 （第3届加拿大数学竞赛试题） 解：设v u z y x xyzuv n +?+?+?+?==101010102 3 4 ，其中}9,,2,1,0{,,,, ∈v u z y x 且 1≥x ；v u y x xyuv m +?+?+?==10101023； 而m n k = 是整数，可证n m <9，即<+?+?+?)101010(923v u y x v u z y x +?+?+?+?101010102 34 即z y x v u 2 2 3 101010880++<+，这显然是成立的； 又可证m n 11<，即v u z y x +?+?+?+?101010102 3 4 ＜)101010(112 3 v u y x +?+?+? 即v u y x z 101010101022 3 2 +++<，这显然也是正确的。 于是m n m 119<<，即119< 3 4 ＝)101010(102 3 v u y x +?+?+? 即)10(9990102v v u z +=+=?，而z 2 10|9但3 102 知t t z (9=为正整数） 从而v u t +=?10102 ，显然0===v u t ，因而推得31000?==N xyz n 其中9910≤≤N 。 例7．若}100,,2,1{ ∈n 且n 是其各位数字和的倍数，这样的n 有多少个？（2004年南昌竞赛试题） 解：（1）若n 为个位数字时，显然适合，这种情况共有9种； （2）若n 为100时，也适合； （3）若n 为二位数时，不妨设ab n =，则b a n +=10，由题意得)10(|)(b b a ++ 即 Z b a b a ∈++10即Z b a a ∈+9也就是a b a 9|)(+； 若0=b 显然适合，此种情况共有9种； 若0≠b ，则由a b a >+，故)(|3b a + 若9|)(b a +，则显然可以，此时共有2＋8＝10个； 若（b a +）9，则6=+b a 或12=+b a ，这样的数共有24,42,48,84共4个； 综上所述，共有9＋1＋9＋10＋4＝33个。 练习题 1 设，为两两不等的非负整数其中n a a a a a a n ,,,,22 22014212 1 +++= 求n a a a +++ 21 提示：将2014化为二进制数 2 设N 是整数，它的 b 进制表示是777，求最小的正整数b,使得N 是整数的四次方 18=b 3 如果一个正整数n 在三进制下表示的各数字之和可以被3整除，那么我们称n 为“好的”，则前2005个“好的”正整数之和是多少？（2005年中国奥林匹克协作体夏令营试题） 第四节 初等数论中的几个重要定理 典例分析 例1. 设1),91(=ab ，求证：)(|911212 b a -。 证明：因为13791?=，故由1),91(=ab 知1),91(=a ，从而1),13(,1),7(==a a ，但是 12)13(,6)7(==??，故由欧拉定理得：)7(mod 11)(22612≡≡≡a a ，)13(mod 112≡a ， 从而)91(mod 112 ≡a ；同理，)91(mod 112≡b 。 于是，)91(mod 0111212 ≡-≡-b a ，即)(|911212b a -。 注明：现考虑整数a 的幂n a 所成的数列： ,,,,2 n a a a 若有正整数k 使)(mod 1m a k ≡， 则有)(mod m a a r n ≡，其中k r r kq n <≤+=0,； 因而关于)mod(m ，数列 ,,,,2 n a a a 的项依次同余于,,,,2 k a a a ,,,,2 k a a a ,a 这个数列相继的k 项成一段，各段是完全相同的，因而是周期数列。如下例： 例2．试求不大于100，且使)473(|11++n n 成立的自然数n 的和。 . 解：通过逐次计算，可求出n 3关于11m od 的最小非负剩余（即为被11除所得的余数）为： ),11(mod 53),11(mod 93),11(mod 3332≡≡≡)11(mod 1343),11(mod 435354=?≡≡?≡ 因而通项为n 3的数列的项的最小非负剩余构成周期为5的周期数列： 3，9，5，4，1，3，9，5，4，1，……… 类似地，经过计算可得n 7的数列的项的最小非负剩余构成周期为10的周期数列： 7，5，2，3，10，4，6，9，8，1，……… 于是由上两式可知通项为473++n n 的数列的项的最小非负剩余，构成周期为10（即上两式周期的最小公倍数）的周期数列： 3，7，0，0，4，0，8，7，5，6，……… 这就表明，当101≤≤n 时，当且仅当6,4,3=n 时，)11(mod 0473≡++n n ，即)473(|11++n n ； 又由于数列的周期性，故当)1(10110+≤≤+k n k 时，满足要求的n 只有三个，即 610,410,310+++=k k k n 从而当1001≤≤n 时，满足要求的n 的和为： 148013045301310301330)610()410()310(90 9 90 =+?=?+=+=+++++∑∑∑===k k k k k k k k 例3．求证：对于任意整数x ， x x x 15 7 315135++是一个整数。 证明：令=)(x f x x x 15 7 315135++，则只需证=)(15x f x x x 75335++是15的倍数即可。 由3，5是素数及Fetmat 小定理得)5(mod 5 x x ≡，)3(mod 3 x x ≡，则 )5(mod 07375335≡+≡++x x x x x ；)3(mod 0275335≡+≡++x x x x x 而（3，5）=1，故)15(mod 07533 5 ≡++x x x ，即)(15x f 是15的倍数。所以)(x f 是整数 例4．求证：n n -13 |2730（n 为任意整数）。 证明：令=)(n f n n -13，则=)(n f )1)(1)(1)(1)(1(6 22++-+++-n n n n n n n n ； 所以)(n f 含有因式n n n n n n n n ----2 3 5 7 ,,, 由Fetmat 小定理，知13|,13 n n -7|n n n n n n n n ----2 3 5 7 |2,|3,|5, 又13，7，5，3，2两两互素，所以2730=235713????能整除n n -13 。 例5．设c b a ,,是直角三角形的三边长。如果c b a ,,是整数，求证：abc 可以被30整除。 证明：不妨设c 是直角三角形的斜边长，则2 22b a c +=。 若2 a ，2 b ，2 c ，则)2(mod 0112 2 2 ≡+≡+=b a c ，又因为)2(mod 12 ≡c 矛盾！ 所以2|abc . 若 3 a ，3 b ，3 c ，因为)3(mod 1)13(2 ≡±k ，则)3(mod 2112 2 ≡+≡+b a ，又 )3(mod 12≡c ，矛盾！从而3|abc . 若 5 a ，5 b ，5 c ，因为)5(mod 1)15(2≡±k ，)5(mod 1)25(2 -≡±k ， 所以222±≡+b a 或0(mod5)与)5(mod 12 ±≡c 矛盾！ 从而5|abc . 又(2,3,5)=1，所以30|abc . 例6 设n n n n m m m m n m +++=- 21.1),12(,,证明：为奇数，并且为正整数 提示：1)2,(=m ，则1,2，…，m 是模m 的完系，所以，m ???2,,22,12 也是完系，利用完系的性质既得 例7 设13737.33+?+n n n n n 证明： 为正整数 提示：利用整除的性质：若ab m a m b m ?=则,1),(，命题中可以将被除式扩大若干倍 先证?可推得1),7(=n ，由费尔马小定理：,176 -n 113)3(6 333-++=+n n n n n n 高中数学竞赛中数论问题的常用方法 数论是研究数的性质的一门科学,它与中学数学教育有密切的联系.数论问题解法灵活,题型丰富,它是中学数学竞赛试题的源泉之一.下面介绍数论试题的常用方法. 1.基本原理 为了使用方便,我们将数论中的一些概念和结论摘录如下: 我们用),...,,(21n a a a 表示整数1a ,2a ,…,n a 的最大公约数.用[1a ,2a ,…,n a ]表示1a ,2a ,…,n a 的 最小公倍数.对于实数x ,用[x ]表示不超过x 的最大整数,用{x }=x -[x ]表示x 的小数部分.对于整数 b a ,,若)(|b a m -,,1≥m 则称b a ,关于模m 同余,记为)(mod m b a ≡.对于正整数m ,用)(m ?表示 {1,2,…,m }中与m 互质的整数的个数,并称)(m ?为欧拉函数.对于正整数m ,若整数m r r r ,...,,21中任何两个数对模m 均不同余,则称{m r r r ,...,,21}为模m 的一个完全剩余系；若整数)(21,...,,m r r r ?中每一个数都与m 互质,且其中任何两个数关于模m 不同余,则称{)(21,...,,m r r r ?}为模m 的简化剩余系. 定理1 设b a ,的最大公约数为d ,则存在整数y x ,,使得yb xa d +=. 定理2(1)若)(mod m b a i i ≡,1=i ,2,…,n ,)(m od 21m x x =,则 1 1n i i i a x =∑≡2 1 n i i i b x =∑； (2)若)(mod m b a ≡,),(b a d =,m d |,则 )(mod d m d b d a ≡； (3)若b a ≡,),(b a d =,且1),(=m d ,则)(mod m d b d a ≡； (4)若b a ≡(i m mod ),n i ,...,2,1=,M=[n m m m ,...,,21],则b a ≡(M mod ). 定理3(1)1][][1+<≤<-x x x x ； (2)][][][y x y x +≥+； (3)设p 为素数,则在!n 质因数分解中,p 的指数为 ∑≥1 k k p n . 定理4 (1)若{m r r r ,...,,21}是模m 的完全剩余系,1),(=m a ,则{b ar b ar b ar m +++,...,,21}也是模 m 的完全剩余系； (2)若{)(21,...,,m r r r ?}是模m 的简化剩余系,1),(=m a ,则{)(21...,,m ar ar ar ?}是模m 的简化剩余系. 定理5(1)若1),(=n m ,则)()()(n m mn ???=. (2)若n 的标准分解式为k k p p p n ααα (2) 121=,其中k ααα,...,21为正整数,k p p p ,...,21为互不相 几何学基础简介 Lex Li 几何原本简介 古希腊大数学家欧几里德是与他的巨著——《几何原本》一起名垂千古的。这本书是世界上最著名、最完整而且流传最广的数学著作，也是欧几里德最有价值的一部著作。欧几里德把人们公认的一些事实列成定义和公理，以形式逻辑的方法，用这些定义和公理来研究各种几何图形的性质，从而建立了一套从公理、定义出发，论证命题得到定理得几何学论证方法，形成了一个严密的逻辑体系——几何学。而这本书，也就成了欧式几何的奠基之作。 作为基础的五条公理和公设 五条公理 1.等于同量的量彼此相等； 2.等量加等量，其和相等； 3.等量减等量，其差相等； 4.彼此能重合的物体是全等的； 5.整体大于部分。 五条公设 1.过两点能作且只能作一直线； 2.线段(有限直线)可以无限地延长； 3.以任一点为圆心,任意长为半径,可作一圆； 4.凡是直角都相等； 5.同平面内一条直线和另外两条直线相交，若在直线同侧的两个内角之和小于180°，则这两条直线经无限延长后在这一侧一定相交。 《几何原本》的主要内容 欧几里得的《几何原本》共有十三卷。 目录 第一卷几何基础 第二卷几何与代数 第三卷圆与角 第四卷圆与正多边形 第五卷比例 第六卷相似 第七卷数论（一） 第八卷数论（二） 第九卷数论（三） 第十卷无理量 第十一卷立体几何 第十二卷立体的测量 第十三卷建正多面体 各卷简介 第一卷：几何基础。重点内容有三角形全等的条件，三角形边和角的大小关系，平行线理论，三角形和多角形等积（面积相等）的条件，第一卷最后两个命题是毕达哥拉斯定理的正逆定理； 第二卷：几何与代数。讲如何把三角形变成等积的正方形；其中12、13命题相当于余弦定理。 第三卷：本卷阐述圆，弦，切线，割线，圆心角，圆周角的一些定理。 第四卷：讨论圆内接和外切多边形的做法和性质； 第五卷：讨论比例理论，多数是继承自欧多克斯的比例理论,被认为是"最重要的数学杰作之一" 第六卷：讲相似多边形理论，并以此阐述了比例的性质。 第五、第七、第八、第九、第十卷：讲述比例和算术的理论；第十卷是篇幅最大的一卷，主要讨论无理量（与给定的量不可通约的量），其中第一命题是极限思想的雏形。 第十一卷、十二、十三卷：最后讲述立体几何的内容. 从这些内容可以看出，目前属于中学课程里的初等几何的主要内容已经完全包含在《几何原本》里了。因此长期以来，人们都认为《几何原本》是两千多年来传播几何知识的标准教科书。 《几何原本》的意义和影响 在几何学发展的历史中，欧几里得的《几何原本》起了重大的历史作用。这种作用归结到一点，就是提出了几何学的“根据”和它的逻辑结构的问题。在他写的《几何原本》中，就是用逻辑的链子由此及彼的展开全部几何学，这项工作，前人未曾作到。《几何原本》的诞生，标志着几何学已成为一个有着比较严密的理论系统和科学方法的学科。 论证方法上的影响 关于几何论证的方法，欧几里得提出了分析法、综合法和归谬法。所谓分析法就是先假设所要求的已经得到了，分析这时候成立的条件，由此达到证明的步骤；综合法是从以前证明过的事实开始，逐步的导出要证明的事项；归谬法是在保留命题的假设下，否定结论，从结论的反面出发，由此导出和已证明过的事实相矛盾或和已知条件相矛盾的结果，从而证实原来命题的结论是正确的，也称作反证法。 揭阳职业技术学院 毕业论文（设计） 题目：浅谈同余定理及其应用 学生姓名黄指导教师某某某 系（部）师范教育系专业数学教育 班级 999 班学号 11211211 提交日期200 年月日答辩日期 200 年月日 200 年月日 浅谈同余定理及其应用 摘要 初等数论是研究数的规律，特别是整数性质的数学分支。它以算术方法为主要研究方法，在日常生活中，我们所要注意的常常不是某些整数，而是这些数用某一固定的数去除所得的余数。同余理论是初等数论中的重要内容之一，其性质及应用研究已引起许多学者的关注。本文归纳总结了同余的若干性质，结合实例，探究了同余性质在检验、判断整除问题、求余数、判断合数、韩信点兵问题等方面的具体应用。体现了用同余性质解决问题的简洁性。 关键词：同余整除余式方程 绪论 初等数论是研究整数性质的一门学科，它是数学中最古老的分支之一，内容极为丰富，曾被数学家说成是数学的皇后。同余问题在当今中小学乃至大学的数学教学中都有涉及，它作为初等数论的核心内容之一，具有很强的应用价值，很多数学问题都要借助同余理论来解决。同余的应用问题分为很多种类型，每种类型的题目又有一定的解题技巧。掌握了这些题型的技巧，可以提高大家解决问题的能力。本文基于对同余理论的理解，将应用同余理论解决的问题具体整理分类，从中分析出一些借助同余理论解题的技巧与规律。现在初等数论中关于同余的内容主要包括：同余的定义及基本性质、剩余类与剩余系、欧拉定理、费马小定理、循环小数、一次同余方程及一次同余方程组。 到目前为止，古今中外很多学者与数学家，对同余的应用问题都有了一定的研究。在中国，早在宋代，大数学家秦九韶所著的《数书九章》中就记载了求解同余方程的“大衍求一术”。还有，著名的古代数学著作《孙子算经》中也记载能解决“物不知其数”问题的孙子定理，也被称作“中国剩余定理”。以及“韩信点兵”问题的研究，都为解决一次同余方程和同余方程组的问题带来了便利。在西方，除了高斯引入同余的概念之外，欧拉和费马提出的定理也为解决同余的相关问题做出了重要的贡献。希望通过本文的研究能将同余理论的应用问题更加系统全面的展现出来。以便，今后大家在探究同余理论时，能对同余应用问题的类型和解决技巧有一个清晰的认识和理解，更好的解决相关问题。 1 相关性质定理[1] 性质1同余是一种等价关系，即有： （1）反身性 a≡a（mod m）. （2）对称性若a≡b（mod m），则b≡a（mod m）. （3）传递性若a≡b（mod m）， b≡c（mod m）， 则a≡c（mod m）. 性质2同余式可以相加减,即 若 a≡b（mod m），c≡d（mod m），则 (1) a＋c≡b＋d（mod m）. (2) a－c≡b－d（mod m）. 性质3同余式可以相乘,即有： 全国初中数学联赛初二卷及详解 ————————————————————————————————作者：————————————————————————————————日期： 2017年全国初中数学联合竞赛试题 初二卷 第一试 一、选择题：（本题满分 42 分，每小题 7 分） 1.已知实数a,b,c 满足2a+13b+3c=90，3a+9b+c=72，则32b c a b ++的值为（ ）. A.2 B.1 C.0 D.-1 2.已知实数a,b,c 满足a+b+c=1， 1110135 a b c ++=+++，则(a+1)2+(b+3)2+(c+5)2 的值为（ ）. A.125 B.120 C.100 D.81 3.若正整数a,b,c 满足a ≤b ≤c 且abc=2(a+b+c)，则称(a,b,c)为好数组.那么好数组的个数为（ ）. A.4 B.3 C.2 D.1 4.已知正整数a,b,c 满足a 2 -6b-3c+9=0，-6a+b 2 +c=0，则a 2 +b 2 +c 2 的值为（ ）. A.424 B.430 C.441 D.460 5.梯形ABCD 中，AD ∥BC ，AB=3，BC=4，CD=2，AD=1，则梯形的面积为（ ）. A. 1023 B.103 3 C.32 D.33 6.如图，梯形ABCD 中，AD ∥BC ，∠A=90°，点E 在AB 上，若AE=42，BE=28，BC=70，∠DCE=45°，则DE 的值为（ ）. A.56 B.58 C.60 D.62 二、填空题：（本题满分 28 分，每小题 7 分） 7.使得等式3 11a a ++=成立的实数a 的值为________. 8.已知△ABC 的三个内角满足A ＜B ＜C ＜100°.用θ表示100°-C,C-B,B-A 中的最小者，则θ的最大值为________. 9.设a,b 是两个互质的正整数，且3 8ab p a b =+为质数.则p 的值为________. 一、 带余除法的定义及性质 1. 定义：一般地，如果a 是整数，b 是整数（b ≠0）,若有a ÷b =q ……r ，也就是a ＝b ×q ＋r , 0≤r ＜b ；我们称上面的除法算式为一个带余除法算式。这里： (1)当0r =时：我们称a 可以被b 整除，q 称为a 除以b 的商或完全商 (2)当0r ≠时：我们称a 不可以被b 整除，q 称为a 除以b 的商或不完全商 一个完美的带余除法讲解模型:如图 这是一堆书，共有a 本，这个a 就可以理解为被除数，现在要求按照b 本一捆打包，那么b 就是除数的角色，经过打包后共打包了c 捆，那么这个c 就是商，最后还剩余d 本，这个d 就是余数。 这个图能够让学生清晰的明白带余除法算式中4个量的关系。并且可以看出余数一定要比除数小。 2. 余数的性质 ⑴ 被除数=除数?商+余数；除数=（被除数-余数）÷商；商=（被除数-余数）÷除数； ⑵ 余数小于除数． 二、 余数定理： 1.余数的加法定理 a 与 b 的和除以 c 的余数，等于a ,b 分别除以c 的余数之和，或这个和除以c 的余数。 例如：23，16除以5的余数分别是3和1，所以23+16＝39除以5的余数等于4，即两个余数的和3+1. 当余数的和比除数大时，所求的余数等于余数之和再除以c 的余数。 例如：23，19除以5的余数分别是3和4，所以23+19＝42除以5的余数等于3+4=7除以5的余数为 2 2.余数的加法定理 a 与 b 的差除以 c 的余数，等于a ,b 分别除以c 的余数之差。 知识框架 余数性质及同余定理 例如：23，16除以5的余数分别是3和1，所以23－16＝7除以5的余数等于2，两个余数差3－1＝ 2. 当余数的差不够减时时，补上除数再减。 例如：23，14除以5的余数分别是3和4，23－14＝9除以5的余数等于4，两个余数差为3＋5－4＝4 3.余数的乘法定理 a与b的乘积除以c的余数，等于a,b分别除以c的余数的积，或者这个积除以c所得的余数。 例如：23，16除以5的余数分别是3和1，所以23×16除以5的余数等于3×1＝3。当余数的和比除数大时，所求的余数等于余数之积再除以c的余数。 例如：23，19除以5的余数分别是3和4，所以23×19除以5的余数等于3×4除以5的余数，即2. 乘方：如果a与b除以m的余数相同，那么n a与n b除以m的余数也相同． 一、同余定理 1、定义 整数a和b，除以一个大于1的自然数m所得余数相同，就称a和b对于模m同余或称a和b在模m下同余，即a≡b（modm） 2、同余的重要性质及举例。 〈1〉a≡a（modm）（a为任意自然）； 〈2〉若a≡b（modm），则b≡a（modm） 〈3〉若a≡b（modm），b≡c（modm）则a≡c（modm）； 〈4〉若a≡b（modm），则ac≡bc（modm） 〈5〉若a≡b（modm），c≡d（modm），则ac=bd（modm）； 〈6〉若a≡b（modm）则an≡bm（modm） 其中性质〈3〉常被称为"同余的可传递性"，性质〈4〉、〈5〉常被称为"同余的可乘性，"性质〈6〉常被称为"同余的可开方性" 注意：一般地同余没有"可除性"，但是：如果：ac=bc（modm）且（c，m）=1则a≡b（modm）3、整数分类： 〈1〉用2来将整数分类，分为两类： 1，3，5，7，9，……（奇数）； 0，2，4，6，8，……（偶数） 〈2〉用3来将整数分类，分为三类： 0，3，6，9，12，……（被3除余数是0） 1，4，7，10，13，……（被3除余数是1） 2，5，8，11，14，……（被3除余数是2） 硕士研究生《应用密码学》课程论文浅谈数论在密码学上的应用 指导教师：王玉柱 专业：计算机应用技术 学号：1010706 姓名：杨玖宏 日期：2011年6月30日 浅谈数论在密码学上的应用 摘要：众所周知．数论是数学中最古老、最纯粹、最优美的一个学科．不过鲜为人知的还是，数论同时也是一门应用性极强的应用数学学科．著名国际数学大师陈省身教授早在1992年精辟地指出：“数学中我愿意把数论看作应用数学。”我想数学中有两个很重要的数学部门，一个是数论，另一个是理论物理。在本文中我将先扼要介绍下数论中的一些基本概念、几个主要难题，紧接着我们要介绍数论在现代密码学与计算机科学中的应用。 关键词：数论；计算数论；密码学； 1 引言 随着现代计算机网络通信的广泛使用，传统密码受到很大挑战，它们已经不能完全适应网络环境下使用密码的需求。于是在上世纪七十年代，提出了公钥密码的概念，并且利用数论方法设计了第一个公钥密码体制（RSA公钥密码），经过二十多年的研究，RSA已得到了广泛的应用。在RSA密码体制中，使用了一个大整数（目前通常取这个数有1024比特长），它是两个素数的乘积，这个大整数是公开的，而它的两个素因子是保密的。如果有人能将这个大整数分解因子而得到它的两个素因子，就能破译这个密码体制，所以RSA的安全性是建立在大整数因子分解问题的基础之上的。这是一个经典的数论问题，RSA的提出大大推动了大整数因子分解算法的研究。在上世纪八十年代，人们又提出了椭圆曲线公钥密码，它应用了更深刻的数论知识，它的安全性也得到了密码界的公认，现在也正逐步推向应用。公钥密码的出现，使数学在密码研究中发挥了更加核心的作用。 2 数论概述 数论，顾名思义，就是关于数的理论，数学，顾名思义，就是关于数的学问．高斯曾说过一句名言：“数学是科学的女王，而数论是数学的女王”。基础数论作为一门古老的数学学科，在很常时间内都属于一种纯数学，随着现代科技的发展，数论在整个科学中的应用非常重要[1]。数论中许多基本内容，如同余理论、中国剩余定理（CRT）、高次剩余理论等，在现代密码体制、密钥分配与管理、数字签名、身份认证等方面有重要的应用。 1 数论概述 1.1 整除理论 1)整除：设 a 和 b 是两个整数，且 b≠0，如果存在一个整数 q，使等式a=bq 成立，那么我们称 a 能被 b 整除或 b 整除 a，记作 b— a，其性质有： (1) 若 b | a，a ≠0，则 | b | ? | a | ； (2) 若 b | a，a | b，a ≠0，则 a=b 或 b=a； (3) 若 c | b，b | a, 则 c | a；（c≠0） (4) 若 b | a，则 cb | ca（c≠0）； (5) 若 c | a，c | b,则 c | ma+nb，m，n∈Z（c≠0）。 2) 整除的基本定理：对于任意整数 a，b(b≠0)存在唯一的一对整数 q，r， 数论问题之余数问题:余数问题练习题含答 案 1.数11 1(2007个1),被13除余多少 分析:根据整除性质知:13能整除111111,而2007 6后余3,所以答案为7. 2.求下列各式的余数: (1)2461 135 6047 11 (2)2123 6 分析:(1)5;(2)6443 19=339 2,212=4096 ,4096 19余11 ,所以余数是11 . 3.1013除以一个两位数,余数是12.求出符合条件的所有的两位 数. 分析:1013-12=1001,1001=7 11 13,那么符合条件的所有的两位数有13,77,91 有的同学可能会粗心的认为11也是.11小于12,所以不行.大家做题时要仔细认真. 4.学校新买来118个乒乓球,67个乒乓球拍和33个乒乓球网,如果将这三种物品平分给每个班级,那么这三种物品剩下的数量相同.请问学校共有多少个班 分析:所求班级数是除以118,67,33余数相同的数.那么可知该数应该为118-67=51和67-33=34的公约数,所求答案为17. 5.有一个大于1的整数,除45,59,101所得的余数相同,求这个数. 分析:这个题没有告诉我们,这三个数除以这个数的余数分别是多少,但是由于所得的余数相同,根据性质2,我们可以得到:这个数一定 能整除这三个数中的任意两数的差,也就是说它是任意两数差的公约数. 101-45=56,101-59=42,59-45=14,(56,42,14)=14,14的约数有1,2,7,14,所以这个数可能为2,7,14. 6.求下列各式的余数: (1)2461 135 6047 11 (2)2123 6 分析:(1)5;(2)找规律,2的n次方被6除的余数依次是(n=1,2,3,4 ):2 ,4 ,2 ,4 ,2 ,4 因为要求的是2的123次方是奇数,所以被6除的余数是2. 数学竞赛讲座 数论的方法技巧(上) 数论是研究整数性质的一个数学分支,它历史悠久,而且有着强大的生命力。数论问题叙述简明,“很多数论问题可以从经验中归纳出来,并且仅用三言两语就能向一个行外人解释清楚,但要证明它却远非易事”。因而有人说:“用以发现天才,在初等数学中再也没有比数论更好的课程了。任何学生,如能把当今任何一本数论教材中的习题做出,就应当受到鼓励,并劝他将来从事数学方面的工作。”所以在国内外各级各类的数学竞赛中,数论问题总是占有相当大的比重。 小学数学竞赛中的数论问题,常常涉及整数的整除性、带余除法、奇数与偶数、质数与合数、约数与倍数、整数的分解与分拆。主要的结论有: 1.带余除法:若a,b是两个整数,b>0,则存在两个整数q,r,使得abq+r(0≤r 4.约数个数定理:设n的标准分解式为(1),则它的正约数个数为: d(n)(a1+1)(a2+1)…(ak+1)。 5.整数集的离散性:n与n+1之间不再有其他整数。因此,不等式x 初等数论简介 绪言：在各种数学竞赛中大量出现数论题，题目的内容几乎涉及到初等数论的所有专题。 1． 请看下面的例子： （1） 证明：对于同样的整数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)方程323652x 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） 浅谈数学教学中的哲学思想 数学是整个自然科学发展的前提条件和存在的依据，又是自然科学和社会科学发展的基础。数学也是一门工具性学科，在数学教学中含有丰富的哲学思想，如辩证法，物质和意识的第一性问题，量变到质变的问题，矛盾双方的依存问题，真理的相对性和绝对性问题等等。因此，本文从五个方面谈数学教学中的哲学思想。 一、物质和意识谁是第一性的哲学思想 马克思主义哲学认为，物质第一性，意识第二性，物质决定意识。 世界的本质是物质。人的意识是客观存在的一种反映。如无理数的产生就是人对客观世界的认识的一个飞跃。古希腊时期，著名的毕达哥拉斯学派倡导“唯数论”，即任何量均可以由两个整数之比来表示。但到公元前五世纪末，希腊数学家们却发现有些量例外。在平面几何中寻找正方形的对角线与边的公共度量，其结果与“唯数论”产生了矛盾。因此发生了第一次数学“危机”，其主要原因是认识上的局限性、片面性和绝对化。人们对“唯数论”产生了怀疑。数学家们后来又发现了更多的不能用两个整数之比表示的数，把它们统称为无理数。能用两个整数之比表示的数叫作有理 数。这说明物质不依赖人的意识而客观存在。物质决定一切，意识反映物质。 二、量变到质变的哲学思想 在哲学中，把事物在数量和程度上的逐渐的、不显著的变化叫作量变。把事物显著的、根本性的变化叫作质变。在数学教学中也有这样的情况。如极限的教学中，每个加数都存在极限且每个加数的极限值都等于0，但的确不等于0，它的正确解法是 又如无理数的发现，它也是人的意识由量变到质变的产物，是人对客观事物的认识发生变化的产物。 三、真理的绝对性的哲学思想 真理是绝对的，但人对真理的反映是片面或存在局限的。意识是客观事物在人脑中的反映。这种反映有正确的，也有歪曲的，还有片面性或存在局限的。由此?a生了真理的相对性。如数学悖论的产生和数学“危机”的发生都是人对客观事物的反映的局限性所造成的。数学对客观事物的反映是真实可靠的。但人的意识总达不到完美无缺的状态。由此产生了三次数学“危机”。导致第一次数学“危机”的根本原因是认识上的片面性和绝对化。一方面未能正确认识“一切均可以归纳为整数之比”这一结论的局限性，由此把它看成是绝对的完善的真理。这样实际上就造成了一种片面的、僵化的概念。另一方面，不可通约量的发现，最终必将导致 初中数学竞赛讲座之数论初步(一) 整数的整除性 定义：设a ，b 为二整数，且b ≠０，如果有一整数c ，使a ＝bc ，则称b 是a 的约数，a 是b 的倍数，又称b 整除a ，记作b|a. 显然，１能整除任意整数，任意整数都能整除０. 性质：设a ，b ，c 均为非零整数，则 ①．若c|b ，b|a ，则c|a. ②．若b|a ，则bc|ac ③．若c|a ，c|b ，则对任意整数m 、n ，有c|ma ＋nb ④．若b|ac ，且(a ，b)＝1，则b|c 证明：因为(a ，b)＝1 则存在两个整数s ，t ，使得 as ＋bt ＝1 ∴ asc ＋btc ＝c ∵ b|ac ? b|asc ∴ b|(asc ＋btc) ? b|c ⑤．若(a ，b)＝1，且a|c ，b|c ，则ab|c 证明：a|c ，则c ＝as(s ∈Z) 又b|c ，则c ＝bt(t ∈Z) 又(a ，b)＝1 ∴ s ＝bt'(t'∈Z) 于是c ＝abt' 即ab|c ⑥．若b|ac ，而b 为质数，则b|a ，或b|c ⑦．(a －b)|(a n －b n )(n ∈N)，(a ＋b)|(a n ＋b n )(n 为奇数) 整除的判别法：设整数N ＝121n 1a a a a - ①.2|a 1?2|N ， 5|a 1? 5|N ②.3|a 1＋a 2＋…＋a n ?3|N 9|a 1＋a 2＋…＋a n ?9|N ③.4|a a ? 4|N 25|a a ? 25|N ④.8|a a a ?8|N 125|a a a ?125|N ⑤．7||41n n a a a -－a a a |?7|N ⑥．11||41n n a a a -－a a a |?11|N ⑦．11|[(a 2n ＋1＋a 2n －1＋…＋a 1)－(a 2n ＋a 2n －2＋…＋a 2)] ?11|N ⑧．13||41n n a a a -－a a a |?13|N 推论：三个连续的整数的积能被６整除. 例题： 1.设一个五位数d a c b a ，其中d －b ＝3，试问a ，c 为何值时，这个五位数被11整除. 解：11|d a c b a ∴ 11|a ＋c ＋d －b －a 即11|c ＋3 ∴ c ＝8 1≤a ≤9，且a ∈Z 2.设72|b 673a ，试求a ，b 的值. 解：72＝8×9，且(8，9)＝1 ∴ 8|b 673 a ，且9| b 673a ∴ 8|b 73 ? b ＝6 且 9|a ＋6＋7＋3＋6 即9|22＋a ∴ a ＝5 3.设n 为自然数，A ＝3237n －632n －855n ＋235n ， 整除 一、常见数字的整除判定方法 1. 一个数的末位能被2或5整除，这个数就能被2或5整除； 一个数的末两位能被4或25整除，这个数就能被4或25整除； 一个数的末三位能被8或125整除，这个数就能被8或125整除； 2. 一个位数数字和能被3整除，这个数就能被3整除； 一个数各位数数字和能被9整除，这个数就能被9整除； 3. 如果一个整数的奇数位上的数字之和与偶数位上的数字之和的差能被11整除，那么这个 数能被11整除. 4. 如果一个整数的末三位与末三位以前的数字组成的数之差能被7、11或13整除，那么这 个数能被7、11或13整除. 5.如果一个数能被99整除，这个数从后两位开始两位一截所得的所有数（如果有偶数位则 拆出的数都有两个数字，如果是奇数位则拆出的数中若干个有两个数字还有一个是一位数）的和是99的倍数，这个数一定是99的倍数。 【备注】（以上规律仅在十进制数中成立.） 二、整除性质 性质1 如果数a和数b都能被数c整除，那么它们的和或差也能被c整除．即如果c︱a，c︱b，那么c︱(a±b)． 性质2 如果数a能被数b整除，b又能被数c整除，那么a也能被c整除．即如果b∣a，c∣b，那么c∣a． 用同样的方法，我们还可以得出： 性质3如果数a能被数b与数c的积整除，那么a也能被b或c整除．即如果bc∣a，那么b∣a，c∣a． 性质4如果数a能被数b整除，也能被数c整除，且数b和数c互质，那么a一定能被b 与c的乘积整除．即如果b∣a，c∣a，且(b，c)=1，那么bc∣a． 例如：如果3∣12，4∣12，且(3，4)=1，那么(3×4) ∣12． 性质5 如果数a能被数b整除，那么am也能被bm整除．如果b｜a，那么bm｜am（m为非0整数）； 性质6如果数a能被数b整除，且数c能被数d整除，那么ac也能被bd整除．如果b｜a，且d｜c，那么bd｜ac； 余数 一、三大余数定理： 1.余数的加法定理 a与b的和除以c的余数，等于a,b分别除以c的余数之和，或这个和除以c的余数。 例如：23，16除以5的余数分别是3和1，所以23+16＝39除以5的余数等于4，即两个余数的和3+1.当余数的和比除数大时，所求的余数等于余数之和再除以c的 余数。 例如：23，19除以5的余数分别是3和4，所以23+19＝42除以5的余数等于3+4=7除以5的余数为2 2.余数的减法定理 费马小定理数论的证明方法 2007年12月28日星期五 01:29 P.M. 费马小定理数论的证明方法 Mod的简单介绍 (Congruence) a=b(mod m) a和b除以m以后有相同的余数 不失一般性地另a>b 则a=km+b比如7=1 mod 2 9=4 mod 5 简单的Congruence 计算 如果a=b mod m c=d mod m 则a=km+b c=tm+d 直接可推出 a+b=c+d (mod m) a-b=c-d (mod m) ab=cd (mod m) 并且可得存在正整数c 使得ac=bc (mod mc) 当然ac=bc(mod m) 费马小定理如果a,p互质且q是质数则a^(p-1)=1 (mod p) 考虑数列An= a,2a,3a,4a…… (p-1)a 假设An中有2项ma, na 被p除以后的余数是相同的.那么必然有ma=na (mod p) 即a(m-n)=0(mod p) 由于a和p互质,所以m-n=0(mod p) 但是m,n属于集合{1,2,3..p-1} 且m不等于n,所以m-n不可能是p的倍数.和假设产生矛盾所以An中任意2项被p除 得到的余数都是不同的, 并且对于任一个整数被p除以后的余数最多有p-1个,分别是 1,2,3,….p-1 而数列An中恰好有p-1个数,所以数列中的数被p除以后的余数一定正好包含所有的1,2,3,4,5…. p-1 由此我们可以用Congruence的乘法性质, a*2a*3a*…(p-1)a=1*2*3*4..*(p-1) (mod p) 对两边进行化简,即可以得到a^(p-1)=1 (mod p) Euler’s Totient function 定义o(n)是所有比n小且和n互质的数的总数(包括1) 例如o(5)=4 o(10)=8 我们发现引入这个以后费马小定理可以改写为a^o(p)=1 (mod p) 事实上,这个结论对所有的正整数n都成立即a^o(n)=1 (mod n) 欧几里得算法 欧几里德算法又称辗转相除法，用于计算两个正整数a，b的最大公约数。其计算原理依赖于下面的定理： 定理：gcd(a,b) = gcd(b,a mod b) (a>b 且a mod b 不为0) 证明：a可以表示成a = kb + r，则r = a mod b 假设d是a,b的一个公约数，则有 d|a,d|b，而r = a - kb，因此d|r 因此d也是（b,a mod b）的公约数 因此（a,b）和（b,a mod b）的公约数是一样的，其最大公约数也必然相等，得证欧几里得算法模板 int gcd(int n,int m) { int t,r; if(n 第一章 整数的唯一分解定理 第一节 整除性 教学重点：应用带余数除法 1、定义1 设a ，b 是整数，b ≠ 0，如果存在整数c ，使得 a = bc 成立，则称a 被b 整除，a 是b 的倍数，b 是a 的约数（因数或除数），并且使用记号b ∣a ；如果不存在整数c 使得a = bc 成立，则称a 不被b 整除，记为b |/a . 注：1、显然每个非零整数a 都有约数 ±1，±a ，称这四个数为a 的平凡约数，a 的另外的约数称为非平凡约数. 2、若整数a ≠ 0，±1，并且只有约数 ±1和 ±a ，则称a 是素数（或质数）；否则称a 为合数. 以后若无特别说明，素数总是指正素数. 3、下面的结论成立： (ⅰ) a ∣b ? ±a ∣±b ； (ⅱ) a ∣b ，b ∣c ? a ∣c ； (ⅲ) b ∣a i ，i = 1, 2, , k ? b ∣a 1x 1 + a 2x 2 + + 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； (ⅴi) b ∣a ，a ≠ 0 ? b a ∣a . 证明：留作习题. 例1 设a 1, a 2, , a n 是整数，且 a 1 + a 2 + + a n = 0，a 1a 2 a n = n ， 则4∣n . 解：如果2|/n ， 则n , a 1, a 2, , a n 都是奇数. 于是a 1 + a 2 + + a n 是奇数个奇数之和，不可能等于零，这与题设矛盾，所以2∣n ，即在a 1, a 2, , a n 中至少有一个偶数. 如果只有一个偶数，不妨设为a 1，那么2|/a i （2 ≤ i ≤ n ）. 此时有等式 a 2 + + a n = -a 1， 在上式中，左端是(n - 1)个奇数之和，右端是偶数，这是不可能的，因此，在a 1, a 2, , a n 中至少有两个偶数，即4∣n . 例2 若n 是奇数，则8∣n 2 - 1. 解：设n = 2k + 1，则 n 2 - 1= (2k + 1)2 - 1 = 4k (k + 1). 在k 和k + 1中有一个是偶数，所以8∣n 2 - 1. 高中数学竞赛 数论 剩余类与剩余系 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 的一个剩余类(也叫同余类)。K 0,K 1,…,K m-1为模m 的全部剩余类. (2)性质(ⅰ)i m i K Z 1 0-≤≤=Y 且K i ∩K j =φ(i ≠j). (ⅱ)每一整数仅在K 0,K 1,…,K m-1一个里. (ⅲ)对任意a 、b ∈Z ，则a 、b ∈K r ?a ≡b(modm). 2.剩余系的定义与性质 (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 为奇数时,2 1 ,,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),则有 aa i +b ≡aa j +b(modm),也矛盾! 数论短期班100题手册 知识框架体系 一、奇偶性质 1．奇数和偶数的表示方法： 因为偶数是2的倍数，所以通常用2k这个式子来表示偶数(这里k是整数)； 因为任何奇数除以2其余数总是1，所以通常用式子21 k+来表示奇数(这里k是整数)．特别注意，因为0能被2整除，所以0是偶数．最小的奇数是1，最小的偶数是0． 2．奇数与偶数的运算性质： 性质一：偶数+偶数=偶数(偶数-偶数=偶数) 奇数+奇数=偶数(奇数-奇数=偶数) 偶数+奇数=奇数(偶数-奇数=奇数) 可以看出：一个数加上(或减去)偶数，不改变这个数的奇偶性； 一个数加上(或减去)奇数，它的奇偶性会发生变化． (也可以这样记：奇偶性相同的数加减得偶数，奇偶性不同的数加减得奇数．) 性质二：偶数?奇数=偶数(推广开来还可以得到：偶数个奇数相加得偶数) 偶数?偶数=偶数(推广开就是：偶数个偶数相加得偶数) 奇数?奇数=奇数(推广开就是：奇数个奇数相加得奇数) 可以看出：一个数乘以偶数时，乘积必为偶数；几个数的积为奇数时，每个乘数都是奇数．(也可以这样简记：对于乘法，见偶(数)就得偶(数))． 性质三：任何一个奇数一定不等于任何一个偶数． 二、整除 1．整除的定义 所谓“一个自然数a能被另一个自然数b整除”就是说“商a b 是一个整数”；或者换句话说： 存在着第三个自然数c，使得a b c =?．这是我们就说“b整除a”或者“a被b整除”，其中b 叫a的约数，a是b的倍数，记作：“|b a”． 2．整除性质： ⑴传递性若|c b，|b a，则|c a． ⑵可加性若|c a，|c b，则|c a b ± （）． ⑶可乘性若|c a，|d b，则| cd ab． 3．整除的特征 ⑴4,25,8,125,16,625的整除特征 能否被4和25整除是看末两位；能否被8和125整除是看末三位；能否被16和625整除是看末四位(100425 =?,10008125 =?,1000016625 =?,100000323125 =?) ⑵3,9的整除特征 能否被9整除是看数字之和是否是9的倍数，并且这个数除以9的余数和这个数数字之和除以9的余数相同，因此判断一个数除以九余几就可以先把和是9的倍数的数划掉，剩下的数是几就代表 “4-6 初等数论初步”简介 北京师范大学胡永建 初等数论是研究整数的性质和不定方程（组）的整数解的一门学问，它与几何学是最古老的两个数学分支。初等数论中至今仍有许多没有解决的问题，如哥德巴赫（Goldbach）问题，孪生素数猜想，奇完全数的存在性问题等，它们对人类智慧产生了极大挑战。人们在解决一些初等数论问题的过程中所作的贡献，对数论乃至整个数学的发展起了重要的推动作用，产生了一些直接与数学有关的新的重要数学分支。初等数论在计算机科学和信息工程中有许多重大的实际应用。在本专题中，同学们将通过具体的问题，学习初等数论的一些基本知识，如有关整数和整除的知识，用辗转相除法求解一次同余方程（组）和简单的一次不定方程等，初等数论中蕴含的一些思想方法，以及我国古代数学在初等数论的研究方面取得的一些重要成就。 一、内容与课程学习目标 本专题的学习初等数论的一些基本知识，具体包括：整数的整除、同余与同余方程、一次不定方程和数论在密码中的应用四部分内容。通过本专题的学习，要引导学生：1．通过实例，认识带余除法，理解同余和剩余类的概念及意义，探索剩余类的运算性质（加法和乘法），并且理解它的实际意义。体会剩余类运算与传统数的运算的异同（会出现零因子）。 2．理解整除、因数和素数的概念，了解确定素数的方法,如埃拉托斯特尼（Eratoshenes）筛法，知道素数有无穷多个。 3．了解十进制表示的整数的整除判别法，探索整数能被3，9，11，7等整除的判别法。会检查整数加法、乘法运算错误的一种方法,如弃九验算法。 4．通过实例，探索利用辗转相除法求两个整数的最大公约数的方法，理解互素的概念，并能用辗转相除法证明：若a能整除bc，且a,b互素，则a能整除c。探索公因数和公倍数的性质。了解算术基本定理。 5．通过实例，理解一次不定方程的模型，利用辗转相除法求解简单的一次不定方程。并尝试写出算法的程序框图，在条件允许的情况下上机实现。 6．通过实例（如物不知其数问题），理解一次同余方程组的模型。 7．理解大衍求一术和孙子定理的证明。 8．理解费马小定理（当m是素数时，a m-1≡1(mod m)）和欧拉定理（aφ(m)≡1(mod m),其中φ(m)是1，2，…，m-1中与m互素的数的个数）及其证明。 9．了解数论在密码中的应用——公开密钥。 二、内容安排 本专题共安排了四讲，其中最后一讲“数论在密码中的应用”可根据教学时间的实际情况机动安排，可由教师讲授，也可作为学生课后的阅读材料。本专题教学时间约需18课时，具体分配如下（仅供参考）： 第一讲整数的整除约5课时 一、整除的概念和性质约2课时 二、最大公因数与最小公倍数约2课时高中数学竞赛中数论问题的常用方法
几何学基础简介
浅谈同余及其应用
全国初中数学联赛初二卷及详解
五年级奥数.数论. 余数性质及同余定理(B级).学生版
浅谈数论在密码学上的应用
数论问题之余数问题-余数问题练习题含答案
七年级数学竞赛讲座数论的方法与技巧(含答案详解)
高中数学竞赛资料-数论部分 (1)
浅谈数学教学中的哲学思想
初中数学竞赛讲座之数论初步(一)
数论知识点之整除与余数
费马小定理数论的证明方法
数论入门
初等数论
高中数学竞赛数论
数论班100题手册
“4-6 初等数论初步”简介