别闹丶这是个认真的玩笑
范文一：初等数论第三版答案 初等数论答案
导读:就爱阅读网友为您分享以下“初等数论答案”的资讯，希望对您有所帮助，感谢您对92to.com的支持!
明:
?(m)
(?) g
2
? ?1 (mod m);
(?) x1x2Lx?(m) ? ?1 (mod m)。
5. 设p = 2n + 1是一个奇素数，证明:模p的全部二次非
1
剩余就是模p的全部原根。
6. 证明:
(?) 设p奇素数，则Mp = 2p ? 1的素因数必为2pk + 1型;
(?) 设n ? 0，则Fn =22+ 1的素因数必为2n + 1k + 1型。
n
第 2 节
第 1 节
1. 补足定理1的证明。
ww
w.
第 2 节
2
2. 证明连分数 是超越数。
2. 证明定理2。
3. 证明:有理数为代数整数的充要条件是这个有理数为整
数。
1. 证明例中的结论。
kh
1111
2!3!
10+10+10+L+10n!+L
第8章
课
3
da
后
答
1. 求模29的最小正原根。
2. 分别求模293和模2?293的原根。 3. 解同余方程:x12 ? 16 (mod 17)。
4. 设p和q = 4p + 1都是素数，证明:2是模q的一个原根。 5. 设m ? 3，g1和g2都是模m的原根，则g = g1g2不是模m的原根。 6. 设p是奇素数，证明:当且仅当p ?1/|n时，有
1n + 2n + L + (p ? 1)n ? 0 (mod p)。
3. 设ξ是一个超越数，α是一个非零的代数数，证明:ξ + α，ξ α，
4
第 3 节
13
w.com
ξ
都是超越数。 α
案网
1. 证明引理1。 2. 证明定理3中的F(
a
+ F(0)是整数。 b
第9章
第 1 节
5
2. 问:1999年10月1日是星期几,
第 2 节
2. 编一个有九个球队进行循环赛的程序表。
1. 利用例1中的加密方法，将“ICOMETODAY”加密。 知明文h与p分别与密文e与g对应，试求出密解公式:
并破译下面的密文:“IRQXREFRXLGXEPQVEP”。
第 4 节
1. 设一RSA的公开加密钥为n = 943，e = 9，试将明文P = 100加密成密文E。
w.
第 5 节
6
2. 设RSA(nA, eA) = RSA(33, 3)，RSA(nB, eB) = RSA(35,
5)，A的签证信息为M = 3，
试说明A向B发送签证M的传送和认证过程。
1. 设某数据库由四个文件组成:F1 = 4，F2 = 6，F3 = 10，F4 = 13。试设计一个
ww
对该数据库加密的方法，但要能取出个别的F(，同时不影响其他文件的保密。 i1 ? i ? 4)
2. 利用本节中的秘密共享方案，设计一个由三方共管文件M = 3的方法，要求:只要有两方提供他们所掌握的数据，就可以求出文件M，但是，仅由任何一方的数据，不能求出文件M。(提示:取p = 5，m1 = 8，m2 = 9，m3 = 11)
第 6 节
7
1. 设明文P的二进制表示是P = (p1p2p3p4p5p6p7p8)2，与P对应的密文是E是E = a1p1 + a2p2 + L + a8p8，如果这里的超增背包向量(a1, a2, a3, a4, a5, a6, a7, a8) = (5, 17, 43, 71,
144, 293, 626, 1280)，并且已知密文E = 1999，求明文P。
kh
da
课
后
2. 已知字母a，b，L，y，z，它们分别与整数00，01，L，24，25对应，又已
P ? a ′E + b ′ (mod 26)，
答
8
第 3 节
案网
1. 编一个有十个球队进行循环赛的程序表。
w.com
14
1. 问:1948年2月14日是星期几,
2. 给定超增背包向量(2, 3, 7, 13, 29, 59)，试设计一个背包型加密方法，将明文P = 51加密。(提示:取M = 118，k = 77)。
ww
w.
kh
9
15
da
课
后
答
w.
10
范文二：《初等数论》试卷及参考答案（与闵嗣鹤第三版配套）
《初等数论》试卷及参考答案【与(闵嗣鹤、严士健)第三版配套】
《初等数论》试卷 一、 单项选择题:(1分/题×20题=20分)
x,(设为实数，为的整数部分，则( ) xx,,
xxx,,，1xxx,,，1; ,(; ,(,,,,,,,,
xxx,,，1xxx,,，1,(; ,(( ,,,,,,,,
,(下列命题中不正确的是( )
,(整数的公因数中最大的称为最大公因数; aaa,,,？12n
,(整数的公倍数中最小的称为最小公倍数 aaa,,,？12n
,(整数与它的绝对值有相同的倍数 a
,(整数与它的绝对值有相同的约数 a
axbyc，,abc,,ab,,(设二元一次不定方程(其中是整数，且不全为零)有一整数解
xydab,,,,，则此方程的一切解可表为( ) ，，00
ab,( xxtyytt,,,，,,,,,0,1,2,;？00dd
ab,( xxtyytt,，,,,,,,,0,1,2,;？00dd
ba,( xxtyytt,，,,,,,,,0,1,2,;？00dd
ba,( xxtyytt,,,,,,,,,0,1,2,;？00dd
,(下列各组数中不构成勾股数的是( ) ,(,，,,，,,; ,(,，,,，,,; ,(,，,，,; ,(,，,,，,, ,(下列推导中不正确的是( )
abmabmaabbm,,,，,，mod,modmod;,( ，，，，，，11221212
abmabmaabbm,,,,mod,modmod;,( ，，，，，，11221212
abmaabam,,,modmod;,( ，，，，111212
22abmabm,,,modmod.,( ，，，，1111
,(模,,的一个简化剩余系是( )
0,1,2,,9;？1,2,3,,10;？,( ,(
1 / 14
《初等数论》试卷及参考答案【与(闵嗣鹤、严士健)第三版配套】
,,,,,5,4,3,2,1,0,1,2,3,4;1,3,7,9.,( ,(
abm,mod,(的充分必要条件是( ) ，，
mab,;abm,; ,( ,(
mab，;abm，.,( ,(
43fxxxx,，，，289fx,0mod5,(设，同余式的所有解为( ) ，，，，，，
x,1,1;x,14;,(或 ,(或
x,1,1mod5;,(或 ,(无解( ，，
naxxp是奇数若,mod,,0modp9、设f(x)=其中为f(x)的一个axaxa，，，？？，，，，i0n10
解，则:( )
,,,,,,,mod()0mod,1pfxp一定为的一个解A( ，，，，
,,,,,,,,mod,1,()0modpfxp一定为的一个解B( ，，，，0
,,当不整除时一定有解其中pfxfxpxxpxxp(),()0modmod,mod,,,C( ，，，，，，00,
,,若为的一个解则有xxpfxpxxp,,,mod()0mod,modD( ，，，，，，00,
n设其中为奇数fxaxaxaaapnp(),,0mod,,,，，，,,？？10(则同余式 ，，,10nin
fxp()0mod,的解数:( ) ，，
A(有时大于p但不大于n; B(可超过p C(等于p D(等于n
11(若2为模p的平方剩余，则p只能为下列质数中的 :( ) A(3 B(11 C(13 D(23
a,,12(若雅可比符号,1，则 ( ) ,,m,,
2同余式一定有解xam,mod,A( ，，
2当时同余式有解amxap,1,mod,,B(; ，，，，
2当奇数mpxap,,(,mod)时同余式有解C(; ，，
2 / 14
《初等数论》试卷及参考答案【与(闵嗣鹤、严士健)第三版配套】
2当奇数时同余式有解apxap,,(),modD(( ，，
2,若同余式有解则解数等于xaa,,,mod2,3,2,1,,13(( ) ，，，，
A( 4 B( 3 C( 2 D( 1 14( 模12的所有可能的指数为;( )
A(1，2，4 B(1，2，4，6，12 C(1，2，3，4，6，12 D(无法确定
15( 若模m的单根存在，下列数中，m可能等于: ( )
A( 2 B( 3 C( 4 D( 12 16(对于模5，下列式子成立的是: ( )
A( B( ind22,ind23,33
C( D( ind50,indindind1025,，3333
17(下列函数中不是可乘函数的是: ( )
A(茂陛鸟斯(mobius)函数w(a) ;
,aB( 欧拉函数; ，，
,xC(不超过x的质数的个数; ，，
,aD(除数函数; ，，
,xabab18( 若对模的指数是，>0，>0，则对模的指数是( ) xmam
babA( B( C( D(无法确定 a
faga19(，均为可乘函数，则( ) ，，，，
fa，，fagaA(为可乘函数; B(为可乘函数 ，，，，ga，，
faga，faga,C(为可乘函数; D(为可乘函数 ，，，，，，，，
,a20(设为茂陛乌斯函数，则有( )不成立 ，，
,11,,,,11,21,,,90,A( B( C( D( ，，，，，，，，二(填空题:(每小题1分，共10分)
!21( 3在45中的最高次n, ____________________;
22( 多元一次不定方程:，其中 ， ，…，，N均为整数，axaxaxN，，，,？aaa1122nn12n
n,2，有整数解的充分必要条件是___________________;
3 / 14
《初等数论》试卷及参考答案【与(闵嗣鹤、严士健)第三版配套】
a0,,abab,1,23(有理数，，，能表成纯循环小数的充分必要条件是，，b
_______________________;
xxm,modaxbm,mod0modm24( 设为一次同余式，的一个解，则它的所有,a，，，，，，0
解为_________________________; 25( 威尔生(wilson)定理:________________________________________;
503,,26( 勒让德符号=________________________________________; ,,1013,,
ap,1,27( 若，则是模的平方剩余的充分必要条件是_____________(欧拉判别条件); pa，，
28( 在模的简化剩余系中，原根的个数是_______________________; m
,,,,129( 设，为模的一个原根，则模的一个原根为_____________; gp2p
,48,30( _________________________________。 ，，
三(简答题:(5分,题×4题,20分) 31(命题“任意奇数的平方减1是8的倍数”对吗,说明理由。
am,1,32(“若，通过模的简化剩余系，则也通过模的简化剩余系”这命题是否正xmaxm，，
确,正确请证明，不正确请举反例。
33(求模17的简化剩余系中平方剩余与平方非剩余。
,,,k12Sa,a34(设为的标准分解式，记为的正因数的和，为的正因数的appp,？aaa，，，，12k
Sa,a个数，则,, ,, 为什么, ，，，，
四(计算题。(7分,题×4题,28分) 35( 求不定方程6x+93y=75的一切整数解。
x,1mod5,，，
,36( 解同余方程组 y,3mod6，，,
,z,2mod7，，,
2x37(解同余式?11(mod125)
38(求模13的所有原根。
五、证明题:(7分/题×2题=14分)
22239、试证: ，(x，y)=1 y是偶数的整数解可写成: xyz，,2
2222zab,，2yab,2 xab,,,(2)
4 / 14
《初等数论》试卷及参考答案【与(闵嗣鹤、严士健)第三版配套】
ab,,0ab,1,这里，，并且一为奇数，一为偶数。 ，，
40、设a为正整数，试证:
a ,,()(),,da,,ddada||
其中表示展布在a的一切正因数上的和式。 ,da|
六、应用题:(8分)
41、求30～中末尾0的个数。
参考答案:一(单项选择:ABCDD;DACCB;DCAAD;BCBAB。
mxtt，,,,,0,1,2,？aaaN,,,|？b,101,二(填空题:21(21;22(;23(;24(;，，，，012nam,，，
p,1,0mod,pp25(～+1为素数;26(1; ，，，，
p,1,2ap,1mod,,m;28(;29(与中的单数;30(16 27(ggp，，，，，，，
2211m，,三(简答题:31(答:命题正确。 ，， 211211mm，,,，，，，？，，，，，，，，，，
,,，,，22241mmmmmm，1 而必为2的倍数。 ，，，，，，
86页
32(正确(证明见教材。 P47
2p,1,,2233(在摸的简化剩余系中与同余的数是数的平方剩余，pp1,2,,？,,2,,
122222222，， 11,24,39,416,,,,58,62,715,813,,,,pp,,,17,18，，2
故1，2，4，8，9，13，15，16为摸17的平方剩余，而3，5，6，7，10，11，12，14为摸17
的平方非剩余。
,，1kkip,12,i34( ？sappp,，，，，,1，，，，,,iiip,1ii,,11i
,,,,a,，，，111？ ，，，，，，，，12k
k,iffpfp,,，，1？fa证明:若为可乘函数，则( ，，，，，，，，，，,,ii|ai,1,
faafa,,.1 分别令，它们为可乘函数，即得出。 ，，，，
5 / 14
《初等数论》试卷及参考答案【与(闵嗣鹤、严士健)第三版配套】
四(计算题
6,933|75,35(解:因为，故原不定方程有解。 ，，
23125xy，,2311xy，, 又原方程即 ，而易见方程有解
'' 。所以原方程的一个解是 xy,,,16,1xy,,,400,250000
所以，原方程的一切整数解是:( )
xt,，40031 t是整数
rt,,,252
36(解:因为模5，6，7两两互质，由孙子定理得所给同余方程组关于模
5×6×7,210有唯一解，分别解同余方程:
421mod5x,351mod6x,301mod7x,，，，得 ，，，，，，
x,3mod5x,,1mod6x,4mod7， ， ，，，，，，
因此所给同余方程组的解是:
x,,,，,,,，,,423135133042mod210 ，，，，
x,,26151mod210即: ，，
2xx,,11mod51mod5得37(解:从同余方程， ，，，，
222 ， 再从得1511mod5,1010mod5，,,tt，，，，，，11
2因此于是tt,，,1mod5,16mod5 ， ，，，，11
22223 是 ,,，,11mod5,6511mod5的解又从t，，，，，，2
330025mod5,121mod5tt,,,,因此 得 ，，，，22
2tx,,，,,2mod5,65256所以即 是所给方程的一个解，于是所解为: ，，2
x,,56mod125 解毕。 ，，
2,131223,,,，38(解: 为其质因数 gg,,2,3，，12
,,1313，，，，,, ，故g为模13的原根的主要条件是: 6,423
6 / 14
《初等数论》试卷及参考答案【与(闵嗣鹤、严士健)第三版配套】
64g,1mod13g,1mod13 ， ，，，，,,
用 g=1，2，……12逐一验证，得:2，6，7，11为模13的原根，
,124, 因为，故模13原根只有4个，即为所求。 ，，
五、证明题:
39(证明:易验证所给的解为原方程的解，因y为偶数，原方程可化为:
2zxzxr，,,, ,,,,222,,
zxzxzxzx，,，,,,,, 但 ,|,,z,,,,2222,,,,
zxzxzxzx，,，,,,,, ,|,,x,,,,2222,,,,
zx，zx, 而，所以(，)=1 22
由书中引理，我们可假设
zx，zx,22a =， =b 22
显然>b， (，b)=1， 于是 aa
2222aabab X=,b， z=+ ，y=2
因子为奇数，所以，b一定是一为奇，一为偶，证毕 a
40(证明:假定 ，---， 为的所有正约数，那末 dda1k
aa ，---，也是的所有正约数，于是 add1k
a ,()d=,() ,,ddada
再因为在的完全剩余系中任一数的最大公约数 aa
必定是 ，---， 中某一个数，而完全剩余系中与的最 dda1k
m,() 大公约数为的数有 ，所以: didi
m,() = m 证毕 ,dda
7 / 14
《初等数论》试卷及参考答案【与(闵嗣鹤、严士健)第三版配套】 六(应用题:
303030，，，，，，41(解:5在30～中的最高次幂=++ 23,,,,,,555，，，，，，
=6+1+0=7
3030303030，，，，，，，，，， 2在30～的最高次幂=++++ 2345,,,,,,,,,,22222，，，，，，，，，，
=15+7+3+1+0=26
10=2×5，故 30～的末尾有7个零。
2007年4月广东省高等教教育育自学考试
初等数论试卷
一、 单项选择题。(本大题共15小题，每小题2分，共30分) 1(-36，420，48三个数的公因数是( )
A(?1，?3，?4，?5，?6，?12 B. ?1,?2,?3,?4,?6,?,12 C. ?2,?3,?4,?6 D1,2,3,4,5,6,12
?Zpab2.设a,b(整数集)，p是素数，且。则( )
A a,b中恰有一个是p的倍数 B.a,b中没有p的倍数 C.a,b中必有一个是p 的倍数 D. a,b都是p的倍数 3.设a,b是非零整数,d=(a,b),则下列成立的是( )
轾轾ababab犏犏,=,=abA B. 犏犏ddddd臌臌
轾ab轾ababab犏犏,=,=C. D. 22犏犏dddddd臌臌
+4. 则对于任意(正整数集)( ) 设且abcvZaubv,,,1,?=dZ?
(,)adbdd=(,)adbdabd=A. B.
轾(,)adbdab=adbdd,=C. D. 犏臌
5.对任意实数,必有( ) a
轾轾轾-=-+aa1-=-aaaA. B. {}犏犏犏臌臌臌
轾轾-=-aa-=-aaC. D. {}{}犏犏臌臌
6.下列不定方程中,有整数解的是( )
8 / 14
《初等数论》试卷及参考答案【与(闵嗣鹤、严士健)第三版配套】
27753348xyz++=27756572xyz++=A. B.
42701433xyz-+=100204532xyz++=C. D.
+7.设a,b则( ) 挝ZmZabm,,(mod)
A.(a,b)=(a,m) B.(a,b)=(b,m)
C.(a,m)=(m,b) D.(a-b,m)=(a,m)
8.下列集合中,是模15的简化剩余系的是( )
1,2,3,5,7,8,11,131,2,37,8A. B. {}{}
1,4,8,7,11,13,14--29,14,2,2,19,,19,7,8C. D. {}{}
9.下列同余式中成立的是( )
4820A. B. 361(mod49)o271(mod25)o
7241C. D. 44(mod72)o351(mod41)o
axbmo(mod)10.设同余式有解,则下述断语中正确的是( ) A. 该同余式有模m的m-1个解
B. 在模m的一组完全剩余系中,有(b,m)个数满足该同余式
C. 在模m的一组完全剩余系中,有(a,m)个数满足该同余式
D. 在模m的一组完全剩余系中,有(ab,m)个数满足该同余式
11.设素数p>2,a,b分别是模p的平方剩余和平方非剩余,则下列成的是( )
2abA.ab是模p的平方非剩余 B.是模p的平方非剩余 222ababC是模p的平方剩余 D. 是模p的平方非剩余 12.设对模m的指数为k.,则( )
kmmkA. B.
kakmj()C. D,
13.若模m的原根存在,则m可能是( )
A.15的倍数 B.16的倍数
B.81的2倍 D.42的倍数
bx14.若x对模m的指数是ab,a>0,b>0,则对模m的指数是( )
abA. B.b m
9 / 14
《初等数论》试卷及参考答案【与(闵嗣鹤、严士健)第三版配套】 C. D.a ab-
tcm=j()15.设g 是模m的一个原根, .K是模c的一个非负完全剩余系,则L= 是gtK,?{}( )
A.模m的一个完全剩余系 B模m的一个简化全剩余系 C模c的一个完全剩余系 D模c的一个简化全剩余系 二. 填空题(本大题共10，每小题2分，共2分)
35345322642轾16.设则abc,,,= ab=23511,25713,创?创 c=35713创 犏臌
轾禳镲aa镲犏mr==,17.若a,b,是两个整数,b>0,设,则用m,r表达的b除a的带余式是 睚犏镲bb镲臌铪
.
100!18. 的标准分解中7的指数为 . 32!
a(0,(,)1)<=abab19.有理数能表示成纯循环小数的充分必要条件是>
.
aaa12kmppp=Lppp,,Lj()m=20.设,是m的互不相同的素数,则 1212kk
.
abacmo(mod)21.设a,b,c,m都是整数,,则当 时, bcmo(mod).
aaa212kmppp=Lp(,)1am=22.设,为互异的奇素数(i=1,2….,k), ,则同余式xamo(mod)12ik
有解时,解数为 .
23.设m是偶数,则模m有原根的充分必要条件是 .
k24.设a对模m的指数为t,则成立的充分必要条件是 . amo1(mod)
aaa,,,Lindaaa(,,,)Lo(mod())jm25(若是与m互素的t个整数，则 12t12t
三、计算题。(本大题共4题，第26，27小题各5分，第28，29小题各7分，共24分) 26(解不定方程 12357531.xy+=的整数解
27.求3对模52的指数.
10 / 14
《初等数论》试卷及参考答案【与(闵嗣鹤、严士健)第三版配套】
ì?xo2(mod3)???28.解同余方程组 xo3(mod4)í??xo3(mod5)???
29(对哪些奇素p,3是模p的二次剩余?
四、应用题(本题10分)
2003100199930(今天是星期三，试求经过天后是星期几, t=+(20012)五、证明题(本大题共2题，每小题8分，共30分) 31(求证3是模17的原根.
232.已知383是素数，求证。 xo219(mod383)有解
2007年4月广东省高等教教育育自学考试
初等数论试题答案及评分参考 一、 单项选择题
—5BCDAB 6—10ACDBC 1
11—15ADCDB
二、填空题
45652316. 23571113创创
轾禳镲aa镲犏abbabmbr=+=+g()或17. 睚犏镲bb镲臌铪
18.12
t19.使得。 101(mod)ob成立(,10)1b=或存在一个正整数t,
111aaaaaa---1111112kk()()()pppppp---L20(或 m---L(1)(1)(1)kk1122ppp12k
21(a,m)=1
k222.
a23.m=2,4或，其中为正整数，p 为素数 2pa
tk24(
indaidnaidna+++L25( 12t
三、计算题
353126(解:(123，57)=，所以方程有整数解。
11 / 14
《初等数论》试卷及参考答案【与(闵嗣鹤、严士健)第三版配套】
4119177+=y化简方程得 . (1分)
411923=?解得
19361=?
1193619(41192)6=-?--创于是
=?+ 41(6)1913
41(6177)1916177177??创= 故
xy=-? 6177,13177 知方程有特解 (3分) 00
ì?xt=-?617719?t=0,1,2,北L 一般解为()(5分) í?yt=?1317741??
j()5224=27、解:，24的正因数为
1，2，3，4，6，8，12，24 (2分)
1234依次检验: 3339327329mod52)汉汉，，，(
6 (4分) 31(mod52)o
故3对模52的指数是6 (5分)
mmmm====3,4,5,6028、 解: 123
MMM===20,15,12 123
'''MMM===2,3,3 而 (3分) 123
故此同余组的解为
x捍220231533123(mod60)?创+创
o23(mod60) (7分)
p?529、解:显然，由二次互反律，有
3111---pp骣骣骣?3pp鼢 珑 222鼢 (1)(1) =-=- (1分) 珑 鼢 珑 鼢 珑 p33桫桫桫
骣p1,如p1(mod3)o??? 由于= ?{?- 1，如p2(mod3)???3桫
12 / 14
《初等数论》试卷及参考答案【与(闵嗣鹤、严士健)第三版配套】
1p-1,如 p1(mod4)o2 (3分) (1)- {1，如 p3(mod4)-
p-1骣骣3p鼢珑2鼢1(1)所以 =?- 珑鼢珑鼢珑p3桫桫
po1(mod3)p汉21(mod3)- 或 (5分) ??{{po1(mod4)p汉31(mod4)-
酆p 1(mod12)
p罕(mod12)所以只有当时，3是模p的二次剩余 (7分)
四、应用题
30、解: 要求模7的余数 t
2004(mod7),125(mod7)汉
66 由欧拉定理 (2分) 41(mod7),51(mod7)汉
20032003333655? 于是 (5分) 20044442(mod7)汉春
10010061644? (7分) 1255552(mod7)?春
1999663331? 于是 (9分) t?4444(mod7)春
于是再过天就是星期日 (10分) t
五 证明题
431、证:求得 ，其不同素因数只有2 (2分) j(17)162==
j(17) =8 (4分) 2
j(17)8233161(mod17)=汗 而 (6分)
所以3是模17的一个原根 (8分)
219373= 32、证:，于是
骣骣骣219373鼢 珑 鼢 = (1分) 珑 鼢 珑 鼢 珑 383383383桫桫桫
由二次互转律
313831--骣骣骣?3383383鼢 珑 22鼢 (1) =-=- 珑 鼢 珑 鼢 珑 38332桫桫桫
13 / 14
《初等数论》试卷及参考答案【与(闵嗣鹤、严士健)第三版配套】
骣骣21-鼢珑鼢 (4分) =-=-=--=(1)1珑鼢珑鼢珑33桫桫
2骣骣骣骣骣7338318232??鼢鼢?珑珑?鼢鼢 ====?珑珑?鼢鼢?珑珑?鼢鼢珑珑?38373737373桫桫桫桫桫
2731-8=-=(1)1 (7分) 骣2192???所以 =1 故同余方程 有解 (8分) xo219(mod383)?????383桫
14 / 14
范文三：初等数论
初等数论 本讲内容:
?数 论基本性质
?同 余及同余方程
?【 大数取余】
?【 费马定理】
?【 快速幂模运算】
数论主要讨论自然数、整数等一系列数字之间的关系。 数论四大定理
?费马小定理:a 是一个整数, p 是一个质数, a 、 p 互素, 则 a^p≡ a(mod p)
?威尔逊定理:p 是一个质数,则 (p-1)! ≡ -1(mod p) ?欧拉定理:对于互质的整数 a 和 n ,有 a^φ(n) ≡ 1 (mod n) 。欧拉函数 φ(n ) 表示与 n 互素且不超过 n 的 正整数的个数
?还有一个呢?(China reminder theory)
1、整除的概念
2、公约数
3、公倍数
4、欧几里得算法(辗转相除法)
5、扩展欧几里得算法
定义:设 a 和 b 不完全为 0,则存在整数 x 和 y, 使得 xa+yb=gcd(a,b)。
若 gcd(a, b) = d, 则必定存在整数 x, y使得
ax + by = d
由于
ax + by = d
bx0 + (a%b)y0 = d (经过一次辗转:a=b,b=a%b)
在计算机中
a%b = a – (a/b) * b
所以
bx0 + (a%b)y0 = bx0 + [a – (a/b) * b]y0
= a y0 + b(x0 – (a/b) y0)
= ax + by
对照 a, b系数,可由不定方程
bx0 + (a%b)y0 = d
的解 x0 ,y0,得 ax + by = d的解
x = y0 , y = x0 – (a/b) y0
而初始条件为
ax + 0*y = d = a
明显,这个不定方程的一组解为
x = 1, y = 0
5.1 【求解 x , y 的方法的理解】 :
设 a>b。 1、 显然当 b=0, gcd (a , b ) =a。 此时 x=1, y=0;
2、 ab<>0 时 设 ax1+by1=gcd(a,b);
bx2+(a mod b)y2=gcd(b,a mod b); 根据欧几里德原理有 gcd(a,b)=gcd(b,a mod b); 则 :ax1+by1=bx2+(a mod b)y2; 即 :ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;
根据恒等定理得:x1=y2; y1=x2-(a/b)*y2;
这样我们就得到了求解 x1,y1 的方法:x1, y1 的值基于 x2, y2.
上面的思想是以递归定义的,因为 gcd 不断的递归求解一定 会有个时候 b=0,所以递归可以结束。
5.2 【使用扩展欧几里德算法解决不定方程的办法】 :
?利用扩展欧几里得算法,很容易求得诸如 ax+by=c (1)这样二元一次不定方程的整数解问题。
?设 a,b 的最大公约数为 d=(a,b ) ,则 a=a1d, b=b1d, (a1,b1)=1,因此 (1)可表示为:
d(a1x+b1y) = c
?于是,当且仅当 d|c时 (1)方有整数解
?显然, 若 x0,y0为 (1)的解, 那么对任意整数 t 有 x = x0-bt, y = y0 + at 均为该方程的解
?因此,可设计一个求解出特解的算法,然后利用这条性质 得到该方程的通解
?步骤如下:
?求解 a 、 b 的最大公约数 d=(a,b),若 d 不被 c 整除 则方程无整数解,否则,将方程两边同时除以 d ,得到 : a0x+b0y=c0
?使用扩展欧几里得算法计算上述方程的解 x0,y0,求 得特解 x1=x0c0, y1=y0c0。
?代入通解得 x=x0c0-a0t, y=y0c0+b0t
POJ 1061 青蛙的约会
两只青蛙它们约定各自朝西跳, 直到碰面为止。 可是它们出发之 前忘记了一件很重要的事情, 既没有问清楚对方的特征, 也没有 约定见面的具体位置。
不过青蛙们都是很乐观的, 它们觉得只要一直朝着某个方向跳下 去, 总能碰到对方的。 但是除非这两只青蛙在同一时间跳到同一 点上, 不然是永远都不可能碰面的。 为了帮助这两只乐观的青蛙, 你被要求写一个程序来判断这两只青蛙是否能够碰面, 会在什么 时候碰面。
我们把这两只青蛙分别叫做青蛙 A 和青蛙 B ,并且规定纬度 线上东经 0度处为原点,由东往西为正方向,单位长度 1米, 这样我们就得到了一条首尾相接的数轴。设青蛙 A 的出发点 坐标是 x , 青蛙 B 的出发点坐标是 y 。 青蛙 A 一次能跳 m 米, 青蛙 B 一次能跳 n 米,两只青蛙跳一次所花费的时间相同。 纬度线总长 L 米。 现在要你求出它们跳了几次以后才会碰面。
思路:
设两只青蛙跳了 t 步
A 的坐标 x+mt, B 的坐标 y+nt
相遇的充要条件:
x+mt-y-nt= pL ( p Z) 即 (n-m)*t+Lp=x-y (L>0)
问题转化为:
求满足 A*t+Lp=B 的最小 t (t>0)
即求 一次同余方程
A*t = B (mod L) 的最小正整数解(穷举? )
解 ax = b (mod n)方程
等价于存在 y ,使得 ax-ny=b。记 d=gcd(a,n), a=d*a`, n=d*n`,那 么必有 d|b。
求解 a`x-n`y=b/d。
x 不 是 唯 一 的 , 但 x 的 所 有 解 相 差 n`的 整 数 倍 x,x+n/d,x+2*n/d+… +x+(d-1)*n/d
扩展欧几里得算法:
# include __int64 gcd(__int64 a,__int64 b) { if(b==0) return a; return gcd(b,a%b); } void exgcd(__int64 a,__int64 b,__int64 &m,__int64 &n) { if(b==0) { m=1; n=0; return ; } exgcd(b,a%b,m,n); __int64 t; t=m; m=n; n=t-a/b*n; } int main() { __int64 x,y,m,n,l,a,b,c,k1,k2,r,t; while(scanf( { a=n-m; b=l; c=x-y; r=gcd(a,b); if(c%r) { printf( continue; } a/=r; b/=r; c/=r; exgcd(a,b,k1,k2); t=c*k1/b; k1=c*k1-t*b; if(k1<> k1+=b; printf( } return 0; } 5.3【同余式】 若 a, b为整数, m 为一个常整数,则当 m|(a - b) 时,我们称 a , b 对模 m 同余,记作 a ≡ b(mod m) 5.4 【同余方程】 a,b 都是整数, m 是正整数,形如 ax ≡ b(mod m) ,且 x 是未 知整数的同余式称为一元线性同余方程。设 gcd(a,b)=d,如果 d|b,则方程恰有 d 个 mod m不同余的解,否则方程无解。 设 a0=a/d,m0=m/d;现在我们又回到了之前学的扩展欧几里得 算法。由于此时 gcd(a0,m0)=1,因此可以运用扩展欧几里得算 法算出 a0x+m0y=b/d的解 x, 虽然 x 不唯一, 但都属于同一个 模 m 剩余系,方程共有 d 个模 m 剩余类满足要求,即: X,x+m0,x+2m0,…… ,x+(d-1)m0. 求方程所有解的算法: int solve (int a,int b,int m) { Ex_gcd(a,m,d,x,y); if(b%d) return -1;//代表无解 x=x*(b/d)%m; for(int i=1;i<> ans[i]=(x+(i-1)*m/d)%m; } 5.5 【中国剩余定理】 学习这个之前,我们先看一道题目: POJ 1006 Biorhythms 这是一道中国剩余定理的典型应用。 根据题意,可得同余方程组:X=p(mod 23) X=e(mod 28) X=i(mod 33) 因为 23,28,33都是两两互素的,即满足中国剩余定理的条件, 不过值得注意的是题目要求的是大于 d 的最小整数解。 根 据 中 国 剩 余 定 理 , 给 定 两 两 互 素 的 正 整 数 m[1],m[2],m[3]........m[r],任何小于 M=m [1] * m [2] * m [3] *.......m [r]的非负整数 N 均可由 M%m[i]唯一确定。令 Mi=M/m[i],因为 m[1],m[2],m[3]........, m[r]两两互素,因此 gcd (Mi , m[i]) ==1,即 Mi* Pi==1(mod m[i]), 同余方程组:x=a [1](mod m[1]); x=a [2](mod m[2]); x=a [3](mod m[3]); ..................... x=a [r](mod m[r]); 有模 M 的唯一解; 容易验证 a[1]*M1*P1+a[2]*M2*P2+.............a[r]*Mr*Pr就是 同余方程组的解。 代码 : 二、素数: 定义:设整数 n ≠ 0,±1. 如果除了显然因数±1,±n 以外, n 没有其他因数,那么, n 叫做素数(或质数 不可约数) ,否则, n 叫做合数 . 规定:若没有特殊说明, 素数总是指正整数, 通常写成 p 或 p1, p2,…, pn 。 1. 算术基本定理 因为每一个大于 1的正整数 n 都可以唯一的被分解成素数的乘 积,在乘积中的素因子按照非降序排列。即正整数 n 的分解式 n=P1^a1*P2^a2*……Pk^ak, 其 中 P1,P2……Pk 是 素 数 , P1<><……pk ,且="" a1,a2,……ak=""> 设 D(n)为 n 的正因子个数, 则 D(n)=(a1+1) *(a2+1)……(ak+1); Q (n ) 为 n 的 所 有 因 子 之 和 , Q(n)=[P1^(a1+1)/(P1-1)]*[P2^(a2+1)/(P2-1)]……[Pk^(ak+1)/(Pk -1)]; 2、 【素数定理】 :(1) 、一个小于整实数 x 的素数个数 P(x)=x/(lnx); (ln 以 10为底) ; (2) 、令 F(n)是第 n 个素数,其中 n 是正整数,那么 F(n)=n*ln(n);(由(1)可以推出) ; 再看一题: http://acm.hdu.edu.cn/showproblem.php?pid=1452 题目要求 2004的 X 次方取余 29,即(2004^X) %29。因为每一 个大于 1的正整数 n 都可以唯一的被分解成素数的乘积, 在乘积 中 的 素 因 子 按 照 非 降 序 排 列 。 即 正 整 数 n 的 分 解 式 n=P1^a1*P2^a2*……Pk^ak, 其 中 P1,P2……Pk 是 素 数 , P1<><……pk ,且="" a1,a2,……ak=""> 因 为 2004可 以 被 分 解 成 2004=2^2*3*167, 所 以 2004^X=(2^2*3*167)^X,即 2004^X=2^(2*X)*3^X*167^X; 所以 S=[2^(2*X-1) /(2-1)]*[(3^X-1)/(3-1)]*[(167^X-1)/(167-1)]=R /332, 其中R=2^(2*X-1) *(3^X-1)*(167^X-1); 因为X很大,所以根据费马小定理:对于任意素数P,任意整数 a,有a^(P-1)modP=1;所以a^28mod29 =1; 因此a^bmod29=a^(bmod28)mod29,所 以直接将X取余28,这样,X再大也没有关系,同时,解题时 运用了快速模取幂运算, 这样在时间复杂度上也有保障, 运行X =1000000000是毫无压力的! ! ! ! 最后,再考虑 S=(R/332) mod29,即 R+29k=332S(k 为满足等 式 的 任 意 整 数 ) , 而 9*332-103*29=1, 所 以 9*(R+29k) =9*332S=S+103*29S,所以 332关于 29的逆元是 9,所以 (R*9)mod29=Smod29。至此,此题已经解出。 代码 : 附录: 乘法逆元: 如果 gcd(a, b)=d,则存在 m , n ,使得 d = ma + nb,称呼这种关 系为 a 、 b 组合整数 d , m , n 称为组合系数。 当 d=1时, 有 ma + nb = 1 , 此时可以看出 m 是 a 模 b 的乘法逆元, n 是 b 模 a 的乘 法逆元。 为了证明上面的结论, 我们把上述计算中 xi 、 yi 看成 ti 的迭代初 始值,考察一组数 (t1, t2, t3) ,用归纳法证明:当通过扩展欧几 里德算法计算后,每一行都满足 a ×t1 + b×t2 = t3 第一行:1 ×a + 0 ×b = a成立 第二行:0 ×a + 1 ×b = b成立 假设前 k 行都成立,考察第 k+1行 对于 k-1行和 k 行有 t1(k-1) t2(k-1) t3(k-1) ; t1(k) t2(k) t3(k) 分别满足: t1(k-1) ×a + t2(k-1) ×b = t3(k-1) t1(k) ×a + t2(k) ×b = t3(k) 根据扩展欧几里德算法,假设 t3(k-1) = j t3(k) + r 则:t3(k+1) = r t2(k+1) = t2(k-1) - j ×t2(k) t1(k+1) = t1(k-1) - j ×t1(k) 则 t1(k+1) ×a + t2(k+1) ×b =t1(k-1) ×a - j ×t1(k) ×a +t2(k-1) ×b - j ×t2(k) ×b= t3(k-1) - j t3(k) = r = t3(k+1) 得证 因此, 当最终 t3迭代计算到 1时, 有 t1×a + t2 ×b = 1, 显然, t1是 a 模 b 的乘法逆元, t2是 b 模 a 的乘法逆元。 c 语言实现 //扩展的欧几里德算法求乘法逆元 #include int ExtendedEuclid( int f,int d ,int *result); int main() { int x,y,z; z = 0; printf( scanf( if(ExtendedEuclid(x,y,&z)) printf( else printf( return 0; } int ExtendedEuclid( int f,int d ,int *result) { int x1,x2,x3,y1,y2,y3,t1,t2,t3,q; x1 = y2 = 1; x2 = y1 = 0; x3 = ( f>=d )?f:d; y3 = ( f>=d )?d:f; while( 1 ) { if ( y3 == 0 ) { *result = x3; /* 两个数不互素则 result 为两个数的最大公 约数,此时返回值为零 */ return 0; } if ( y3 == 1 ) { *result = y2; /* 两个数互素则 resutl 为其乘法逆元,此时返回值 为 1 */ return 1; } q = x3/y3; t1 = x1 - q*y1; t2 = x2 - q*y2; t3 = x3 - q*y3; x1 = y1; x2 = y2; x3 = y3; y1 = t1; y2 = t2; y3 = t3; } } 练习题(POJ ) : 1023 The Fun Number System 数论 1091 跳蚤 数论 1152 An Easy Problem! 数论 2191 Mersenne Composite Numbers 数论 2381 Random Gap 数论 2417 Discrete Logging 数论 1510 Hares and Foxes 数论 1641 Rational Approximation 数论 1730 Perfect Pth Powers 数论 1777 Vivian's Problem 数论 2061 Pseudo-random Numbers 数论 1014 Dividing 数论 /DP?/组合数学 ->母函数 ? 1606 Jugs 数论 /搜索 1995 Raising Modulo Numbers 数论 ->大数的幂求余 2115 C Looooops 数论 ->解模线性方程 1288 Sly Number 数论 ->解模线性方程组 1395 Cog-Wheels 数学 ->解正系数的线性方程组 第一章 整数的唯一分解定理 第一节 整除性 教学重点：应用带余数除法 定义1 设a ，b 是整数，b ≠ 0，如果存在整数c ，使得 a = bc 成立，则称a 被b 整除，a 是b 的倍数，b 是a 的约数（因数或除数），并且使用记号b ∣a ；如果不存在整数c 使得a = bc 成立，则称a 不被b 整除，记为b /|a . 如果a = bc 里的c 不存在，我们就说b 不能整除a 或a 不被b 整除，记作b /|a . 定理1 （传递性）若a 是b 的倍数，b 是c 的倍数，则a 是c 的倍数， 也就是b |a,c|b?c|a. 证 b |a,c|b就是说存在两个整数a 1，b 1使得 a =a 1b , b =b 1c 成立 因此 a =(a 1b 1) c , 故c|a 但是a 1b 1是一个整数， 定理2 若a ，b 都是m 的倍数，则a ±b 也是m 的倍数. 证 a ，b 是m 的倍数的意义就是存在两个整数a 1 , b 1，使得 a =a 1m , b =b 1m . 因此 a ±b =(a 1±b 1) m , 但a 1±b 1是整数，故a ±b 是m 的倍数 . 定理3 若a 1, a 2, , a n 都是m 的倍数，q 1, q 2, , q n 是任意个整数， 则q 1a 1+q 2a 2+ +q n a n 是m 的倍数. 注：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=""> a (ⅴi) b ∣a ，a ≠ 0 ? ∣a . b 定理4(带余数除法) 设a 与b 是两个整数，b ≠ 0，则存在唯一的两个整数q 和r ，使得 a = bq + r ，0 ≤ r < |b="" |.=""> 证明 存在性 若b ∣a ，a = bq ，q ∈Z ，可取r = 0. 若b /|a ，考虑集合 A = { a + kb ；k ∈Z }, 其中Z 表示所有整数的集合. 在集合A 中有无限多个正整数，设最小的正整数是r = a + k 0b ，则必有 0 < r="">< |b="" |，=""> 否则就有r ≥ |b |. 因为b /所以r ≠ |b |. 于是r > |b |，即a + k 0b > |b |，a + k 0b - |b | > |a ， 0，这样，在集合A 中，又有正整数a + k 0b - |b | < r="" ，这与r="" 的最小性矛盾.="" 所以式(2)必定成立.="" 取q="-" k0知式(1)成立.=""> 唯一性 假设有两对整数q '，r '与q ''，r ''都使得式(1)成立，即 a = q ''b + r '' = q 'b + r '，0 ≤ r ', r '' < |b=""> 则 (q '' - q ') b = r ' - r ''，|r ' - r ''| < |b="" |，=""> 因此r ' - r '' = 0，r ' = r ''，再由式(3)得出q ' = q ''，唯一性得证. 证毕 3、定义2 称式(1)中的q 是a 被b 除的不完全商，r 是a 被b 除的余数，也叫最小非负剩余，记作b =r . 第二节 最大公因数与辗转相除法 第三节 最小公倍数 教学目的：1、掌握最大公因数与最小公倍数性质； 2、掌握辗转相除法； 3、会求最大公因数与最小公倍数. 教学重点：最大公因数与最小公倍数性质 教学难点：辗转相除法 一、最大公因数 定义 设a 1, a 2, , a n 是（ n n ≥2) 个整数若整数. d 是它们之中每一个的因数，那么d 就叫作a 1, a 2, , a n 的一个公因数. 整数a 1, a 2, , a k 的公共约数称为a 1, a 2, , a k 的公约数. 不全为零的整数a 1, a 2, , a k 的公约数中最大的一个叫做a 1, a 2, , a k 的最大公约数（或最大公因数）， 记为(a 1, a 2, , a k ). 如果(a 1, a 2, , a k ) = 1，则称a 1, a 2, , a k 是互素的（或互质的）；如果 (a i , a j) = 1，1 ≤ i , j ≤ k ，i ≠ j， 则称a 1, a 2, , a k 是两两互素的（或两两互质的）. 显然，a 1, a 2, , a k 两两互素可以推出(a 1, a 2, , a k ) = 1，反之则不然，例如(2, 6, 15) = 1，但(2, 6) = 2. 定理1 若a 1, a 2, , a n 是任意n 个不全为零的整数，则 （i ）a 1, a 2, , a n 与a 1, a 2, a n 的公因数相同；（ii ）(a 1, a 2, , a n ）=a 1, a 2, a n ）. 证 设d 是a 1, a 2, , a n 的任一公因数由定义. d a i , i =1,2, , n , 因而d a i , i =1, 2, , n , 故d 是a 1, a 2, a n 的一个公因数， a 1, a 2, a n 的任一个公因数都是，a 1, a 2, a n 的一个公因数. 故a 1, a 2, a n 与a 1, a 2, a n 有相同的公因数. 定理2 若b 是任一正整数，则（i ）0与b 的公因数就是b 的因数， 反之，b 的因数也就是0与b 的公因数 . (ii) (0,b)=b . 证 显然0与b 的公因数是b 的公因数 . 由于任何非零整数都是0的因数， 故b 的因数也就是0，b 的公因数，于是（i ）得证. 其次，我们立刻知道b 的最大因数是b ；而0，b 的最大公因数是b 的最大公因数，故（0，b ）=b. 推论2.1 若b 是任一非零整数，则（0，b ）= b . 定理3 设a , b , c 是任意三个不全为零的整数，且a =bq +c , 因而（a , b ) =(b , c ). 其中q 是非零整数，则a , b 与b , c 有相同的公因数， 定理4 若a , b 是任意两个整数，则(a , b ) 就是 a = bq 1 + r 1， 0 < r="" 1="">< |b=""> b = r 1q 2 + r 2， 0 < r="" 2="">< r="" 1=""> r k - 1 = r k q k + 1 + r k + 1，0 < r="" k="" +="" 1="">< r="" k="" ，=""> r n - 2 = r n - 1q n + r n ， 0 < r="" n="">< r="" n-1=""> r n - 1 = r n q n + 1 . 中的最后一个不等于零的余数，即得(a , b ) =r n 推论4.1 a , b 的公因数与(a , b ) 的因数相同. 例（1） a =-1859, b =1573由定理得 （-1859，1573）=（1859,1573）. 1859=1?1573+286 1573=5?286+143 286=2?143 所以（-1859，1573）=（1859,1573）=143. 例（2） a =169, b =121由定理得 169=1?121+48 121=2?48+25 48=1?25+3 25=1?23+2 23=11?2+1 2=2?1 所以（169,121）=1. 定理5 设a , b 是任意两个不全为零的整数， （i ）若m 是任一正整数，则(am,bm)=(a,b)m. a b (a , b ) (ii)若δ是a,b 的任一公因数，则（）=, δδδ 特别地, (a b , ) = 1. (a , b ) (a , b ) 定理6 若a 1, a 2, , a n 是n 个整数，则(a 1, a 2, , a n ) =d n . 二、最小公倍数 1、定义 整数a 1, a 2, , a k 的公共倍数称为a 1, a 2, , a k 的公倍数. a 1, a 2, , a k 的正公倍数中的最小的一个叫做a 1, a 2, , a k 的最小公倍数，记为[a 1, a 2, , a k ]. 2、定理1 下面的等式成立： (ⅰ) [a , 1] = |a |，[a , a ] = |a |； (ⅱ) [a , b ] = [b , a ]； (ⅲ) [a 1, a 2, , a k ] = [|a 1|, |a 2| , |a k |]； (ⅳ) 若a ∣b ，则[a , b ] = |b |. 3、定理2 对任意的正整数a ，b ，有 [a , b ] =ab . (a , b ) 证明：设m 是a 和b 的一个公倍数，那么存在整数k 1，k 2，使得m = ak 1，m = bk 2，因此 ak 1 = bk 2 . (1) 于是 a b k 1=k 2. (a , b ) (a , b ) 由于(a b , ) = 1，所以 (a , b ) (a , b ) b |k 1，即k 1=b t ， (a , b ) (a , b ) 其中t 是某个整数. 将上式代入式(1)得到 m =ab t . (2) (a , b ) 另一方面，对于任意的整数t ，由式(2)所确定的m 显然是a 与b 的公倍数，因此a 与b 的公倍数必是式(2)中的形式，其中t 是整数. 当t = 1时，得到最小公倍数 [a , b ] =ab . (a , b ) 推论1 两个整数的任何公倍数可以被它们的最小公倍数整除. 证明 由式(2)可得证. 这个推论说明：两个整数的最小公倍数不但是最小的正倍数，而且是另外的公倍数的约数. 推论2 设m ，a ，b 是正整数，则[ma , mb ] = m [a , b ]. 证明 由定理2及前面的定理2的推论得到 m 2ab m 2ab mab ==[ma , mb ] == m [a , b ]. (ma , mb ) m (a , b ) (a , b ) 证毕 4、定理3 对于任意的n 个整数a 1, a 2, , a n ，记 [a 1, a 2] = m 2，[m 2, a 3] = m 3， ，[m n -2, a n -1] = m n -1，[m n -1, a n ] = m n ， 则 [a 1, a 2, , a n ] = m n . 证明：我们有 m n = [m n -1, a n ] ? m n -1∣m n ，a n ∣m n ， m n -1 = [m n -2, a n -1] ? m n -2∣m n -1∣m n ，a n ∣m n ，a n -1∣m n -1∣m n ， m n -2 = [m n -3, a n -2] ? m n -3∣m n -2∣m n ，a n ∣m n ，a n -1∣m n ，a n -2∣m n ， m 2 = [a 1, a 2] ? a n ∣m n ， ，a 2∣m n ，a 1∣m n ， 即m n 是a 1, a 2, , a n 的一个公倍数. 另一方面，对于a 1, a 2, , a n 的任何公倍数m ，由定理2的推论及m 2, , m n 的定义，得 m 2∣m ，m 3∣m ， ，m n ∣m . 即m n 是a 1, a 2, , a n 最小的正的公倍数. 证毕 推论 若m 是整数a 1, a 2, , a n 的公倍数，则[a 1, a 2, , a n ]∣m . 定理4 整数a 1, a 2, , a n 两两互素，即 (a i , a j ) = 1，1 ≤ i , j ≤ n ，i ≠ j 的充要条件是 [a 1, a 2, , a n ] = a 1a 2 a n . (3) 证明：必要性 因为(a 1, a 2) = 1，由定理2得到 [a 1, a 2] =a 1a 2= a 1a 2 . (a 1, a 2) 由(a 1, a 3) = (a 2, a 3) = 1及前面的定理4推论得到 (a 1a 2, a 3) = 1， 由此及定理3得到 [a 1, a 2, a 3] = [[a 1, a 2], a 3] = [a 1a 2, a 3] = a 1a 2a 3 . 如此继续下去，就得到式(3). 充分性 用归纳法证明. 当n = 2时，式(3)成为[a 1, a 2] = a 1a 2. 由定理2 a 1a 2 = [a 1, a 2] = 即当n = 2时，充分性成立. 假设充分性当n = k 时成立，即 [a 1, a 2, , a k ] = a 1a 2 a k ? (a i , a j ) = 1，1 ≤ i , j ≤ k ，i ≠ j . 对于整数a 1, a 2, , a k , a k + 1，使用定理3中的记号，由定理3可知 [a 1, a 2, , a k , a k + 1] = [m k , a k + 1]. (4) 其中m k = [a 1, a 2, , a k ].因此，如果 a 1a 2? (a 1, a 2) = 1， (a 1, a 2) [a 1, a 2, , a k , a k + 1] = a 1a 2 a k a k + 1， 那么，由此及式(4)得到 [a 1, a 2, , a k , a k + 1] = [m k , a k + 1] = 即 m k = a 1a 2 a k ， (m k , a k +1) m k a k +1= a 1a 2 a k a k + 1， (m k , a k +1) 显然m k ≤ a1a 2 a k ，(m k , a k + 1) ≥ 1.所以若使上式成立，必是 (m k , a k + 1) = 1， (5) 并且 m k = a 1a 2 a k . (6) 由式(6)与式(5)推出 (a i , a k + 1) = 1，1 ≤ i ≤ k ； (7) 由式(6)及归纳假设推出 (a i , a j ) = 1，1 ≤ i , j ≤ k ，i ≠ j . (8) 综合式(7)与式(8)，可知当n = k + 1时，充分性成立. 由归纳法证明了充分性. 证毕 三、辗转相除法 本节要介绍一个计算最大公约数的算法——辗转相除法，又称Euclid 算法. 它是数论中的一个重要方法，在其他数学分支中也有广泛的应用. 1、定义1 下面的一组带余数除法，称为辗转相除法. 设a 和b 是整数，b ≠ 0，依次做带余数除法： a = bq 1 + r 1， 0 < r="" 1="">< |b=""> b = r 1q 2 + r 2， 0 < r="" 2="">< r="" 1=""> r k - 1 = r k q k + 1 + r k + 1，0 < r="" k="" +="" 1="">< r="" k="" ，=""> r n - 2 = r n - 1q n + r n ， 0 < r="" n="">< r="" n-1=""> r n - 1 = r n q n + 1 . 由于b 是固定的，而且 |b | > r 1 > r 2 > ， 所以式(1)中只包含有限个等式. 下面，我们要对式(1)所包含的等式的个数，即要做的带余数除法的次数进行估计. 2、引理1 用下面的方式定义Fibonacci 数列{F n }： F 1 = F 2 = 1，F n = F n - 1 + F n - 2，n ≥ 3， 那么对于任意的整数n ≥ 3，有 F n > α n - 2， (2) 其中α =1+5. 2 证明：容易验证 α 2 = α + 1. 当n = 3时，由 F 3 = 2 >1+= α 2 可知式(2)成立. 假设式(2)对于所有的整数k ≤ n （n ≥ 3）成立，即 F k > α k - 2，k ≤ n ， 则 F n + 1 = F n + F n - 1 > α n - 2 + α n - 3 = α n - 3(α + 1) = α n - 3α 2 = α n- 1， 即当k = n + 1时式(2)也成立. 由归纳法知式(2)对一切n ≥ 3成立. 证毕. 定理1 若a,b 是任意两个正整数，则 Q k a -P k b =(-1) 其中 k -1r k , k =1, , n ; Q 0=0, Q 1=1, Q k =q k Q k -1+Q k -2, 其中k=2, ,n. 推论1.1 若a,b 是任意两个不全为零的整数，则存在两个整数 s,t 使得as+bt=(a,b).P 0=1, P 1=q 1, P k =q k P k -1+P k -2, 定理2 若a,b,c 是三个整数，且(a,c)=1.则 （i ）ab,c 与b,c 有相同的公因数， （ii ） (ab,c)=(b,c), 上面假定了b , c 至少有一不为零. 推论2.1 若（a,c)=1,cab , 则c b . 推论2.2 设a 1, a 2, , a n 及b 1, b 2, , b m 是任意两组整数. 若前一组中任意整数与后一组中任意整数互质， 则a 1, a 2, , a n 与b 1, b 2, , b m 互质. 例2 用辗转相除法求(125, 17)，以及x ，y ，使得 125x + 17y = (125, 17). 解：做辗转相除法： 125 = 7?17 + 6，q 1 = 7，r 1 = 6， 17 = 2?6 + 5， q 2 = 2，r 2 = 5， 6 = 1?5 + 1， q 3 = 1，r 3 = 1， 5 = 5?1， q 4 = 5. 由定理4，(125, 17) = r 3 = 1. 利用定理2计算（n = 3） P 0 = 1，P 1 = 7，P 2 = 2?7 + 1 = 15，P 3 = 1?15 + 7 = 22， Q 0 = 0，Q 1 = 1，Q 2 = 2?1 + 0 = 2，Q 3 = 1?2 + 1 = 3， 取x = (-1) 3 - 1Q 3 = 3，y = (-1) 3P 3 = -22，则 125?3 + 17?(-22) = (125, 17) = 1. 例3 求(12345, 678). 解：(12345, 678) = (12345, 339) = (12006, 339) = (6003, 339) = (5664, 339) = (177, 339) = (177, 162) = (177, 81) = (96, 81) = (3, 81) = 3. 例4 在m 个盒子中放若干个硬币，然后以下述方式往这些盒子里继续放硬币：每一次在n （n < m="" ）个盒子中各放一个硬币.="" 证明：若(m="" ,="" n="" )=""> 解：由于(m , n ) = 1，所以存在整数x ，y ，使得mx + ny = 1. 因此对于任意的自然数k ，有 1 + m (-x + kn ) = n (km + y ) ， 这样，当k 充分大时，总可找出正整数x 0，y 0，使得 1 + mx 0 = ny 0 . 上式说明，如果放y 0次（每次放n 个），那么在使m 个盒子中各放x 0个后，还多出一个硬币. 把这个硬币放入含硬币最少的盒子中（这是可以做到的），就使它与含有最多硬币的盒子所含硬币数量之差减少1. 因此经过若干次放硬币后，必可使所有盒子中的硬币数目相同. 四、小结. 第四节 素数、整数的唯一分解定理 教学目的：1、掌握素数的一系列性质； 2、理解并掌握唯一分解定理. 教学重点：素数的性质及唯一分解定理的证明及应用 教学难点：唯一分解定理的证明及应用 教学课时：4课时 教学过程 一、素数 1、定义 大于1的整数，如果只有平凡因子，就叫素数，否则叫合数. 2、定理1 设a 是任意大于1的整数，则a 除1以外的最小正因子p 是素数，并且当a 是合数时，则p ≤a . 3、定理2 设p 是素数，a 是任意整数，则p |a 或(p , a ) =1. 4、定理3 设p 是素数，p|ab , 则p|a或p|b. 5、定理4 素数有无穷多个. 6、定理2 形如4n-1型的素数有无穷多个. 例1 写出不超过100的所有的素数。 解 将不超过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 按以下步骤进行： (ⅰ) 删去1，剩下的后面的第一个数是2，2是素数； (ⅱ) 删去2后面的被2整除的数，剩下的2后面的第一个数是3，3是素数； (ⅲ) 再删去3后面的被3整除的数，剩下的3后面的第一个数是5，5是素数； (ⅳ) 再删去5后面的被5整除的数，剩下的5后面的第一个数是7，7是素数； 照以上步骤可以依次得到素数2, 3, 5, 7, 11, . 由引理1可知，不超过100的合数必有一个不超过10的素约数，因此在删去7后面被7整除的数以后，就得到了不超过100的全部素数. 例1中所使用的寻找素数的方法，称为Eratosthenes 筛法. 它可以用来求出不超过任何固定整数的所有素数. 在理论上这是可行的；但在实际应用中，这种方法需要大量的计算时间，是不可取的. 曾经有人希望找到一个表示素数的方便的公式，例如，是否存在一个不是常数的整系数多项式f(x)，当x ≥x 0时，f(x)都表示素数？ 7、定理3 对于任意给定的整数x 0，不存在整系数多项式 f (x ) =∑a i x i ，其中 a n ≠0, n >0, i =0n 使得当x ≥x 0时，f(x)都表示素数. 二、整数唯一分解定理（算术基本定理） 1、引理1 任何大于1的正整数n 可以写成素数之积，即 n = p 1p 2 p m ， (1) 其中p i （1 ≤ i ≤ m ）是素数. 证明：当n = 2时，结论显然成立. 假设对于2 ≤ n ≤ k ，式(1)成立，我们来证明式(1)对于n = k + 1也成立，从而由归纳法推出式(1)对任何大于1的整数n 成立. 如果k + 1是素数，式(1)显然成立. 如果k + 1是合数，则存在素数p 与整数d ，使得k + 1 = pd . 由于2 ≤ d ≤ k ，由归纳假定知存在素数q 1, q 2, , q l ，使得d = q 1q 2 q l ，从而k + 1 = pq 1q 2 q l . 证毕 2、定理1(算术基本定理) 任何大于1的整数n 可以唯一地表示成 α1α2k n =p 1p 2 p αk ， (2) 其中p 1, p 2, , p k 是素数，p 1 < p="" 2=""><>< p="" k="" ，α1,="" α2,="" ,="" αk=""> 证明 由引理1，任何大于1的整数n 可以表示成式(2)的形式，因此，只需 证明表示式(2)的唯一性. 假设p i （1 ≤ i ≤ k ）与q j （1 ≤ j ≤ l ）都是素数， p 1 ≤ p 2 ≤ ≤ p k ，q 1 ≤ q 2 ≤ ≤ q l ， (3) 并且 n = p 1p 2 p k = q 1q 2 q l ， (4) 则必有某个q j （1 ≤ j ≤ l ），使得p 1∣q j ，所以p 1 = q j ；又有某个p i （1 ≤ i ≤ k ），使得q 1∣p i ，所以q 1 = pi . 于是，由式(3)可知p 1 = q 1，从而由式(4)得到 p 2 p k = q 2 q l . 重复上述这一过程，得到 k = l ，p i = q i ，1 ≤ i ≤ k . 证毕 3、定义1 使用定理1中的记号，称 α1α2k n =p 1p 2 p αk 是n 的标准分解式，其中p i （1 ≤ i ≤ k ）是素数，p 1 < p="" 2=""><>< p="" k="" ，α="" i（1="" ≤="" i="" ≤="" k=""> 推论1 使用式(2)中的记号，有 (ⅰ) n 的正因数d 必有形式 γk γ1γ2 d =p 1，γi ∈Z ，0 ≤ γi ≤ α i，1 ≤ i ≤ k ； p 2 p k (ⅱ) n 的正倍数m 必有形式 βk β2 m =p 1β1p 2M ，M ∈N ，βi ∈N ，βi ≥ α i，1 ≤ i ≤ k . p k 推论2 设正整数a 与b 的标准分解式是 γl βk δ1α1γ1β1δs k a =p 1 p αq q ，b =p p 111 r s ， k l k r 其中p i （1 ≤ i ≤ k ），q i （1 ≤ i ≤ l ）与r i （1 ≤ i ≤ s ）是两两不相同的素数，αi ，βi λk λ1（1 ≤ i ≤ k ），γ（与δ（都是非负整数，则(a , b ) =p 1， λi p k i 1 ≤ i ≤ l ）i 1 ≤ i ≤ s ） = min{αi , δi }，1 ≤ i ≤ k ， μk β1 [a , b ] =p 1μ1 p k q 1 q l βl r 1γ1 r s γs ，μi = max{αi , δi }，1 ≤ i ≤ k . 为了方便，推论2常叙述为下面的形式： 推论2 ' 设正整数a 与b 的标准分解式是 βk α1α2β1β1k a =p 1p 2 p αk ，b =p 1p 2 p k ， 其中p 1, p 2, , p k 是互不相同的素数，αi ，βi （1 ≤ i ≤ k ）都是非负整数，则 λk λ1 (a , b ) =p 1λ1p 2 p k ，λi =min{αi , βi }，1≤i ≤k ， . μk μ1μ1 [a , b ]=p 1p 2 p k ，μi =max{αi , βi }，1≤i ≤k 推论3 设a ，b ，c ，n 是正整数， ab = c n ，(a , b ) = 1， (5) 则存在正整数u ，v ，使得 a = u n ，b = v n ，c = uv ，(u , v ) = 1. γk γ1γ1 证明: 设c =p 1，其中p 1, p 2, , p k 是互不相同的素数，γi （1 ≤ i ≤ k ）p 2 p k 是正整数. 又设 βk α1α2β1β1k a =p 1p 2 p α，b =p p p 12k k ， 其中αI ，βi （1 ≤ i ≤ k ）都是非负整数. 由式(5)及推论2 '可知 min{αi , βi } = 0，αi + βi = n γi ，1 ≤ i ≤ k ， 因此，对于每个i （1 ≤ i ≤ k ），等式 αi = n γi ，βi = 0与αi = 0，βi = n γi 有且只有一个成立. 这就证明了推论. 证毕 例1 写出51480的标准分解式. 解: 我们有 51480 = 2?25740 = 22?12870 = 23?6435 = 23?5?1287 = 23?5?3?429 = 23?5?32?143 = 23?32?5?11?13. 例2 设a ，b ，c 是整数，证明： (ⅰ) (a , b )[a , b ] = ab ； (ⅱ) (a , [b , c ]) = [(a , b ), (a , c )]. 解：为了叙述方便，不妨假定a ，b ，c 是正整数. (ⅰ) 设 βk α1α2β1β1k a =p 1p 2 p αk ，b =p 1p 2 p k ， 其中p 1, p 2, , p k 是互不相同的素数，αi ，βi （1 ≤ i ≤ k ）都是非负整数. 由定理1推论2 '，有 λk λ1λ1 (a , b ) =p 1p 2 p k ，λi =m in{αi , βi }，1≤i ≤k ， μ1 μ1 μk [a , b ]=p 1p 2 p k ，μi =m ax{αi , βi }，1≤i ≤k 。 由此知 (a , b )[a , b ] =∏p i λi +μi =∏p i min{αi , βi }+max{αi , βi }=∏p i αi +βi =ab ； i =1 i =1 i =1 k k k (ⅱ) 设 a =∏p i αi ，b =∏p i βi ，c =∏p i γi ， i =1 i =1 i =1 k k k 其中p 1, p 2, , p k 是互不相同的素数，αi ，βi ，γi （1 ≤ i ≤ k ）都是非负整数. 由定理1推论2 '，有 (a , [b , c ])=∏p i λi ，[(a , b ), (a , c )]=∏p i μi ， i =1 i =1 k k 其中，对于1 ≤ i ≤ k ，有 λi = min{αi , max{βi , γi }}， μi = max{min{αi , βi }, min{αi , γi }}， 不妨设βi ≤ γi ，则 min{αi , βi } ≤ min{αi , γi }， 所以 μi = min{αi , γi } = λi ， 即(a , [b , c ]) = [(a , b ), (a , c )]. 注：利用定理1可以容易地处理许多像例2这样的问题. 2、引理 设a >0, b >0, s >1，则(s a -1, s b -1) =s (a , b ) -1. 证明：不妨设a >b ，由辗转相除法得 a = bq 1 + r 1， 0 < r="" 1="">< |b="" |，="" b="r" 1q="" 2="" +="" r="" 2，="" 0="">< r="" 2="">< r="" 1=""> r n - 2 = r n - 1q n + r n ， 0 < r="" n="">< r="" n-1=""> r n - 1 = r n q n + 1 ， 其中r n =(a , b ) . 因此 s -1b r 1 s -1=s (s -1) +s -1， b s -1 a r 1 bq 1 r 1q 2s -1r 1r 2r 2b s -1=s (s -1) +s -1， r 1 s -1 …………… s r n -2 r n -1q n s -1r n -1r n r n -1=s (s -1) +s -1， r n -1 s -1 r n q n +1s -1r n r n -1 s -1=r n (s -1) . s -1 ?r ? 3、引理2 设r 是素数，则r | i ??，其中1≤i ≤r -1. ??4、引理3 设r 是素数，则r |2r -2. 5、定理1 设p 是一个奇素数，q 是M p 的一个素因子，则q 形如 q =2kp +1. 证明：由引理3知q |2q -1-1，又由q |2p -1，从而有引理1知q |2(p , q -1) -1，从而(p , q -1) >1，故p |q -1. 又q -1为偶数，进而得证定理1. 7、定理2 m ≠n ，则(F m , F n ) =1. 证明：不是一般性，设m >n ≥0，m =n +k , k >0，设l =(F n , F n +k ) . 又 F n |F n +k -2，故l |2，因F n 为奇数，故l =1. 函数[x ], {x }及其在数论中的一个应用 函数[x ]与{x }是对于一切实数都有定义的函数，函数[x ]的值等于不大于x 的最大整数；函数{x }的值是x -[x ]. 我们把[x ]叫做x 的整数部分，{x }叫做x 的小数部分. 例 [π]=3, [e ]=2, [-π]=-4, ??=0, ?-?=-1; ?3??5? ?3?2 ?-?=, { π}=0.14159 , =0.414 , ?5?5 {-π}=1-0.14159 =0.85840 . ?2??3? 有定义我们可以得出以下结论： I x =[x ]+{x }. II [x ]≤x ≤[x ]+1, x -1<[x ]≤x="" ,0≤{x=""><1. iii="" [n="" +x="" ]="n" +[x="" ],="" n=""> IV [x ]+[y ]≤[x +y ], {x }+{y }≥{x +y }. V [-x ]=? ???-[x ]-1, 当x 不是整数时，? ? ??-[x ], 当x 是整数时?? (带余数除法)若a , b 是两个整数，b >0, 则 VI ?a ??a ??a ? a =b ??+b ??,0≤b ??≤b -1. ?b ??b ??b ? 若a , b 是任意两个正整数，则不大于a 而为b 的倍数VII 定理 在n ! 的标准分解式中质因数P (p ≤n )的指数 ∞ ?n ??n ??n ?h =??+?2?+ =∑?r ?. r =1?p ??p ??p ? ?a ? 的正整数的个数是??. ?b ? ?n ? 注意：若P s >n , 则?s ?=0, 故上式只有有限项不为零，因此有意义. ?p ? 证 设想把2, n , 都分解成标准分解式，则由算数基本定理， h 就是这n -1个分解式中p 的指数之和，设其中p 的指数是r 的有n r 个（1≤r ），则 h =n 1+2n 2+ =n 1+n 2+n 3+ + n 2+n 3+ + n 3+ + =N 1+N 2+N 3+ , 其中N r =n r +n r +1+ 恰好是2, , n 这n -1个数中?n ?能被p 除尽的个数，但由VII ，N r =?r ?, 故 ?p ? r ?n ??n ? h =??+?2?+ . ?p ??p ? ?∑??p r ??? ∞ ?n ? 推论1 n ! =∏p r =1 p ≤n , 其中∏表示展布在不超过n 的一切质数上的积式. p ≤n 推论2 贾宪数 n ! 是整数（0<><> k !(n -k )! 证 由IV 及n =(n -k ) +k , ?n ??n -k ??k ??p r ?≥?p r ?+?p r ?, ?????? ?n ?∞?n -k ?∞?k ?∑?p r ?≥∑?p r ?+∑?p r ?. r =1??r =1??r =1??故 ∞ ∏p p ≤n ∑ ?n -k ?∞?k ???+???p ??r =1??p ??r =1? ∞ ∑ ∏p p ≤n ∑ ?n ? ???p ??r =1? ∞ . 由推论1即得k !(n -k )!, 故得证. 推论3 若f (x ) 是一n 次整系数多项式，f (k ) 是它 f (k ) (x ) 的k 阶导数(k ≤n ), 则是一n -k 次整系数多项式. k ! 一次不定方程的整数解的问题 摘要:不定方程是初等数论中一个重要课题, 不仅是数学竞赛, 甚至在中考卷中 也常常出现,对于不定方程,我们通常只求正整数解,有时还可以解决计数、求 最值是的等方面的问题。 二元一次不定方程是最简单的不定方程, 一些复杂的不 定方程一般转化为二元一次不定方程进行求解。 关键词:不定方程;整数解;方法; 不定方程是指未知数的个数多于方程的个数, 其解受到某种限制 (如正整数 解) 的方程组。 其特点往往有无穷多个解, 不能唯一确定。 对于一般的不定方程, 除个别情况外, 没有统一的解法, 本文将针对不同的一次不定方程, 采用不同的 解法。 重要定理:设 a 、 b 、 c 、 d 为整数,则不定方程 ax by c +=有: 定理 1:若(a , b ) =d,且 d 不能整除 c ,则不定方程 ax by c +=没有整数解; 定理 2:若(x 0, , y 0)是不定方程 ax by c +=的一组整数解(称为特解) ,则 ???-=+=at y y bt x x 00(t 为整数)是方程的全部整数解(称为通解) 。 (其中(a , b ) =d, 且 d 能整除 c ) 。 定理 3:若(x 0, , y 0)是不定方程 1=+by ax , (a , b ) =1的特解,则(cx 0, , cy 0) 是方程 ax by c +=的一个特解。 求整系数不定方程 ax by c +=的正整数解,通常有以下步骤: (1)判断有无整数解; (2)求出一个特解; (3)写出通解; (4)有整数 t 同时满足的条件(不等式组) ,代入命题(2)中的表达式,写出 不定方程的正整数解。 解不定方程(组) ,需要根据方程(组)的特点,并灵活运用以下知识和方 法: (1)分离整系数法(2)穷举法(3)因式分解法(4)整数的整除性 (6)奇偶分析(7)不等式分析 例:求下列不定方程的整数解(1) 862=+y x (2) 13105=+y x 解:(1) 原方程变形为:43=+y x , 观察得到 ???==11y x 是 43=+y x 的一组整数解 (特 解) ,根据定理 2, ?? ?-=+=t y t x 131(t 是整数)是原方程的所有整数解。 (2)因为(5,10) =5,但 5不能整除 13,则根据定理 1,原方程无整数解。 【分析】 先判断方程是否有整数解, 多于系数不大的题目优先选用观察法寻找特 解,求出的 特解不同,同一个补丁方程的解得形式可以不同,但它们所包含的 全部解是一样的。 例:求不定方程 213197=+y x 的所有整数解。 因为(7,19) =1,根据定理 2,原方程有整数解。 由原方程可得 75323075314210719213y y y y y x -+-=-+-=-= 由此可观察出一组特解为 2, 2500==y x 所以方程的通解为 ???-=+=t y t x 721925(t 是整数) 其中 ???>->+07201925t t 则 7219 25<-t ,则="" t="-1,0" 代入通解后可得原方程的正整数解为="" ???="=96y" x="" 或="" ???="=225y"> 【分析】 根据定理 2解这类方程, 若未知数的系数较大容易观察出一组整数解时, 可用一个未知数去表示另一个未知数, 再利用整数的知识, 这是解二元一次不等 式的基本方法,称为分离整系数法,这样就容易找出一组整数解来。 例:大客车能容 54人,小客车能容纳 36人,现有 378人要乘车,问需要大、小 客车各几辆才能使每一人都能上车且各车都正好坐满? 解:设需要大客车 x 辆,小客车 y 辆,根据题意可列方程 3783654=+y x ,即 2123=+y x 又(3,2) =1,根据定理 2,原方程有整数解,易知 ?? ?==91y x 是一个特解, 通解为 ???-=+=t y t x 9921(t 为整数)由题意可知 ???>->+099021t t 解得 t=0,1,2,3 相应地 ???==???==???==???==07356391y x y x y x y x 例:某人的生日月份数乘以 31,生日的日期乘以 12,相加后得 347,求此人的 生日。 解:设此人生日的月份数为 x ,日期数为 y ,根据题意可列方程 3471231=+y x 因为 x y 3134712-=, ) 整除(x 31-34712 ) 12(mod711) 12(mod31347x x ≡≡ 则 512+=t x (t 是整数) 12512112 1≤+≤≤≤t x 则 t=0, X=5,把 x=5代入原方程得:y=16 【分析】 求出通解后, 要利用隐含条件求出符合题意的解, 其中此方法运用了同 余的知识。 例:我国古代数学家张建丘所著《算经》中的“百钱买百鸡”问题 :鸡翁一,值 钱五;鸡母一,值钱三;鸡雏一,值钱一,百钱买百鸡,问鸡翁、鸡母、鸡雏各 几何? 解:设鸡翁、鸡母、鸡雏的只数分别为 x , y , z ?????=++=++1003135100z y x z y x 得 200814=+y x ,即 10047=+y x (方法一)特解:???==184y x 通解:???-=+=t y t x 71844(t 是整数) 解得 t=0,1,2 相应地,原方程有三组解: ?????===?????==-?????===844 128111878184z y x z y x z y x (方法二) 令 147=+y x ,其特解为 ???-==53y x ,所以 ???-==500300y x 是 10047=+y x 的特解。 通解为 ?? ?--=+=t y t x 75004300(t 为整数) (方法三) x y 71004-=,所以 ) 4(mod 7100x =,即 ) 4(mod 30x = 所以 t x 44+=(t 为整数)把 t x 44+=代入得 t y 718-= ???-=+=t y t x 71844 【分析】充分挖掘题目隐含条件,进而求整数解。 小结: 以上介绍了初中数学竞赛中一次不定方程的基本解法、解题技巧以及应用, 解不定方程的基本方法是分离整系数法, 要熟练掌握, 在具体的应用问题上, 能 将实际问题转化为不定方程的问题, 并根据题意挖掘题目的隐含条件, 也就是未 知数的取值范围。 参考文献: [1]闵嗣鹤,严士健 . 初等数论 [M].北京 . 高等教育出版社 ,2003. [2]潘承洞,潘承彪 . 初等数论 [M].北京 . 北京大学出版社 ,1991:103-137. [3]黄友初 , 等 . 培养大学生学习兴趣之我见 [J].温州大学学报 ,2004,(2):42-45 [4]张清利,王培根; n 元一次不定方程的解法 [J];北京广播电视大学学 报 ,2004.4. [5]梅章骏; 从一组有趣的数字规律到一类同余方程的解 [J]; 安徽教育学院学报 (自然科学版) ; 1999.4 [6]金永容;欧拉函数表示式的一种新算法 [J];安徽教育学院学报; 2003,3. 转载请注明出处范文大全网 » 初等数论第三版答案初等数论答范文四：初等数论
范文五：初等数论
