§4 欧拉定理·费马定理及其对循环小数的应用欧拉定理及费马定理是数论中非常重要的两个定理，它们在数论中的应用非常广泛。

本节应用简化剩余系的理论，推出欧拉定理，再由欧拉定理，推出费马定理。

最后还要把欧拉定理应用于循环小数。

定理1（欧拉定理） 设()1,,1m a m >=，则()()1mod .m a m ϕ≡证 设()12,,,m r r r ϕ是模m 的一个简化剩余系，因(),1a m =，故()12,,,m ar ar ar ϕ也是模m 的一个简化剩余系. 于是，()()()()()()()()()()()()12121212mod ,mod ,1mod .mm m m m m ar ar ar r rr m a r r r r r r m a m ϕϕϕϕϕϕ≡≡≡推论（费马定理）若p 是质数，则对任意整数a ，总有()mod .p a a p ≡证 因p 为质数，故(),1a p =或.p a 若(),1,a p =则由()1p p ϕ=-及欧拉定理得 ()()11mod ,mod .p p ap a a p -≡≡若p a ，则显然有()mod .pa a p ≡以上两个定理对数论的应用是非常多的。

下面仅说明欧拉定理对无限循环小数的应用。

任何一个有理数都可以表示为ab，这里,a b 都为整数，且0a >。

由带余除法，存在整数(),0q r r b ≤<使得b aq r =+，故,0 1.a bq r r r b b b b b+==+≤< 故以下只讨论开区间()0,1中的分数与小数互化。

若对无限小数120.,n a a a （i a 是0,1,,9中的一个数码，1,2,,i =并且从任何一位以后不全是0）来说，存在非负整数s 及正整数t 使得，对任意正整数1n s ≥+，都有n n t a a +=，则该无限小数可以写为1212120.s s s s t s s s ta a a a a a a a a ++++++定义 若对无限小数120.,n a a a （i a 是0,1,,9中的一个数码，1,2,,i =并且从任何一位以后不全是0）来说，存在非负整数s 及正整数t 使得，对任意正整数1n s ≥+，都有n n t a a +=，则称这一无限小数为循环小数，并把该无限小数简写为 120.s a a a 1s a +.s t a +对于循环小数来说，满足上述性质的,s t 不唯一。

如对于循环小数0.3214139139139，可取4,3s t ==，则该循环小数可简写为0.3214139，也可以取5,6s t ==，则该循环小数可以简写为0.32141391391，等等。

如t 是最小的，则称12,,,s s s t a a a +++为循环节，而把t 称为循环节的长度；若最小的0s =，则称该循环小数为纯循环小数，否则称为混循环小数。

如循环小数0.3214139139139最小的3t =，其循环节是1,3,9。

最小的4s =，故该循环小数是混循环小数。

又如循环小数0.139087713908771390877最小的0s =，故该循环小数是纯循环小数。

定理2 有理数()()0,,1aa b a b b<<=可以表示为纯循环小数的充分必要条件是(),10 1.b =证 （ⅰ）若()()0,,1aa b a b b<<=可以表示为纯循环小数，设 0.ab=12a a ,t a则1212101010tt t t aa a a b--=++++0.12a a t a ,0.aq q b=+>故(),101.101t t a q a bq b =-=- 但(),1a b =，故()()()()101,101mod ,10,10,1, 1.t t t b b b b b -≡===注：也可根据101t b -及反证法证明(),10 1.b =（ⅱ）若(),101b =，则由欧拉定理，()()101mod .b b ϕ≡令(),t b ϕ=则t 为正整数，且10 1.t b -从而存在正整数q '使得101,10.t t bq a bq a a ''-==+令q q a '=，则()1110,01011010101101,110,.1010t t t t t t t t t a a b a qb a q b b b b a a a q a q b b b b -⎛⎫=+<=-<≤=-<- ⎪⎝⎭=+=+⋅ 由带余除法，11211232211110+,010,10,010,10,010,10,010,t t t t t t t t q q a a q q a a q q a a q q a a -----=≤<=+≤<=+≤<=+≤< 则1212110101010.t t t t t t q q a a a a ---=+++++易知q 为正整数，故12,,,t q q q 都为非负整数。

若1t q ≥，则10t q ≥，这与101t q <-矛盾。

故121210,101010,t t t t t q q a a a a ---==++++从而1210..10t t aaa a a bb=+⋅ 反复应用上式，即得 0.ab=12a a .t a定理 3 若a b是有理数，其中()()1110,,1,25,,101,1,a b a b b b b b αβ<<===>其中,αβ都为非负整数，但不全为零，则ab可以表示为循环小数，其中不循环的位数是()max ,.μαβ=证 我们只证明βα≥的情形，至于βα≥的情形，可类似证明。

若βα≥，则.μβ=故121010.a a a b b b βαμβ-==因()1,1,,a b b b =故()1, 1.a b =又()1,101,b =故()()11,21,,21.b b βα-==故1b 不整除2a βα-。

由带余除法，存在整数1,M a 使得11112,0.a b M a a b βα-=+<<因此1110.a aM b b μ=+ 易知()()()11111010,,2,2, 1.M a b a Mb b a b μμαμα--≤<=-==由定理2，可以把11a b 表示为循环小数：110.a b =1c .t c设()111009M m m m μμμ-=++≤≤则10.am m bμ=1c .t c下证不循环的位数不能小于μ。

假设ab还可以表示为 10.vam m b''=()1,,sc c v μ''< 则由定理2，11110100.,vvsa a a c cb b b '⎡⎤''-==⎢⎥'⎣⎦其中()1,10 1.b '=令1110,va a ab b ⎡⎤''=+⎢⎥⎣⎦则 110.v ab a b ''=上式右边可被55βμ=整除，而左边a 及1b '都与5互质，故510,55.v v μμ这与v μ>矛盾。

习题1. 如果今天是星期一，问从今天起再过101010天是星期几？ 解 由欧拉定理得()6101m o d 7.≡ 下求1010被6除所得的余数。

()()()10510551024223224mod 6.≡-=≡-=-=≡-≡故101064q =+，其中q 是一个正整数。

于是()()10106464442210101010103924mod 7.qq +==⋅≡≡=≡=因此，如果今天是星期一，那么从今天起再过101010天是星期五。

2. 求()28561237134+被111除的余数。

解一 因()1237150mod111≡故()5656282814147733123715025005833643411564646211646746343461016mod111.≡=≡=≡=≡=⋅≡⋅=⋅≡⋅≡()()()2828562814147733123713416345025005833643434115634461564211610770mod111.+≡+==≡≡≡≡⨯=⨯≡⨯≡⨯=解二 用模幂算法模幂算法的一个例子：求185被33除所得的余数。

解法如下。

因1829,9241,422,221,1201=⨯=⨯+=⨯=⨯=⨯+ 故()()()()()()()()()()210122122422294121218925555mod33,55525mod33,552531mod33,555315489520mod33,55204mod33.=⨯≡==≡=≡≡=⨯≡⨯=≡=≡≡ 因56228,28214,1427,7231,3211,1201,=⨯=⨯=⨯=⨯+=⨯+=⨯+故()()()()()()()()()()()()210123112273122147222814225628212371123711237150mod111,123711237112371505014mod111,123711237112371145032mod111,12371123713225mod111,12371123712570mod111,12371123717016mod111.=⨯≡=⨯≡⨯≡=⨯≡⨯≡=≡≡=≡≡=≡≡于是()()()282856281237134163450mod111.+≡+=又因()()()()()()()()()()210123112273122147222814250505050mod111,505050505014mod111,505050145032mod111,50503225mod111,50502570mod111,=⨯≡=⨯≡⨯≡=⨯≡⨯≡=≡≡=≡≡故()()2856123713470mod111.+≡3. （ⅰ）证明下列事实但不许用定里1的推论：若p 是质数，12,,,a h h h 是整数，则 ()()1212+m o d .pp p pa ah h h h h h p +++≡++（ⅱ）由（ⅰ）证明定理1的推论，然后再由定理1推论证明定理1.证明 （ⅰ）对a 数学归纳法。

当1a =时，结论显然成立。

假设结论对()11a a ->成立，下面由此证明结论对a 也成立。

由二项式定理及归纳假设得，()()()()()()()11212112122112112112112121+mod .pp p a a a ap p pa a a a a pp p p p a a a p h h h h h h h h h h p p h h h h h h h h h p h h h h h h h p --------⎛⎫+++≡+++++++ ⎪⎝⎭⎛⎫⎛⎫++++++++++ ⎪ ⎪-⎝⎭⎝⎭≡++++≡++（ⅱ）若a 为正整数，则在（ⅰ）中令121a h h h ===，得、()m o d .p a a p ≡ 若a 为负整数，令1a a =-，这里1a 为正整数，则 ()11mod .p p a a a a p =-≡-= 又因()00mod ,p p ≡故对任意整数a ，总有()m o d .p a a p ≡ 这就证明了费马定理。