下载文档原格式
数论
一 、欧拉定理
设1m >的整数，()()(),1,1m
a m a mod
m ϕ=≡则.
例1
设(1000
5x =
+，求
[]x 的末三位数.
解 由二项式定理，
()()()
()
2499
500
998349963998
2
3
3
100010001000
5235235
2323C C
⎤++
++⎥⎦
()
(500
1000
3
25
225mod +335， ()(500
1000
250025
25
212mod =≡≡()328y mod ≡，
(2552y mod ≡(2y mod ≡则
()28min y mod =，
所以
则 因为 所以
()()10010021125,31125mod mod ≡≡， 于是，有 ()()150050021125,31125mod mod ≡≡，
()
()500
3
2232125mod ≡，
又因为 ()150********mod ≡， ()
2255=(320y mod +≡ （2）p 为素数，则
()p a a mod p ≡.
例2 ,,,a b c d 为整数，证明
()44240/b d c d a a ++-. 证明
4240235=，
由于 所以
()()444403b d c d d b c a a a a a mod ++-=-≡.
即
443/()b d c d a a ++-.
由于奇数的4次方被16除余1，偶数的4次方被16除余0，故有
()()4444016b d c d d b c a a a a a mod ++-=-≡.
()
()3
8
9
333a a a a
a a mod ≡==≡≡，
同理
则
()19991999199903d a b c a b c mod
=++≡++≡.
即3/d .
从而
d 不是素数.
例4 设{}()2
1n
p n n -≥是给定的素数，证明：数列中有无穷多项
被p 整除.
证明 当2p =时，结论显然成立.
当
()()1221,21p p p mod
p ->=≡时，由于，所以，所以对任
}1,2,,1p -时，有.则1,x x --
()()
()11121p x x x x p -----+=.
取x p =代入，得
所以
()()1!1p mod p -≡-.
例5
()()1!1p p mod
p -≡-是素数，则.证明：若21p +为奇素数，
则
()()
()()2!1021p
p mod p +-≡+.
证明：()()
()()2
!1021p
p mod p +-≡+
()()()2!121p mod p ⇔≡-+.
而21p +为奇素数，有()()()2!121p mod p ≡-+.
四、中国剩余定理 12M
m m =下的解是唯一的k k M M +
+n 均有个连续正整数，
()
2n x n mod
p ≡- 证明： 设
12,,,n p p p n 为个互不相同的素数，由中国剩余定理
存在正整数解，设S 为一个正整数解，则1
2S S S n +++，，，满足要求.
例7 任给正整数n ，存在n 个连续正整数，使得其中每一个数都不
是幂数.
证明 设
12,,,n p p p n 为个互不相同的素数，由中国剩余定理，
同余方程组
存在正整数解00
00,12S S S S n +++则，，，满足要求.
例8
给定正整数n ，设
()f n 是使()
1f n k k =∑能被n 整除的最小正整数.证明：
当且仅当n 为2的幂时，有
()21f n n =-.
2212m m -=（证明）
2m n ≠当时，
令()21.m
n a a =为大于的奇数此时需证()12/1m a r r ++，即证存在()1
2
/,/1m r a r ++即可.
构造同余方程组
()()
1
021m x mod x mod a +⎧≡⎪⎨≡-⎪⎩
（1）
由中国剩余定理知，同余方程组（1）有正整数解()12r
r n ≤≤，则
()1
2
/,/1m r a r ++.从而有()1
2
/1m a r r ++，即()
12/2
m
r r a +，
()1/2
r r n +.
考虑r 的取值范围： 1,
,n a -均与(0a mod
≡使得
令(),11,1r r j i r n a mod
n =-≤≤-≡则有.
定义1：设
()(),1,1m a n a mod
n m a =≡则满足的最小正整数叫做
a n 对模的阶.
注：若a n r 对模的阶为，则
