mm?1m(m?1)m(m?1)?Z即得：m（1）当m为奇数时，由，故?ai??0(mod m)。 222i?1m（2）当m为偶数时，由（m,m+1）=1即得：?ai?i?1m(m?1)m?(mod m)。 22?（m）2、证明：若m＞2，a1, a2, ?, a?(m)是模m的任一简化剩余系，则

?ai?1i?0(modm).

证明：若a1, a2, ?, a?(m)是模m的一个简化剩余系，则m-a1, m-a2, ?, m-a?(m) 也是模m

?（m）的一个简化剩余系，于是：

?a??(m?a)(modm). 从而：2?aiii?1i?1i?1?(m)?（m）i?m?(m)(modm).

又由于m＞2，?(m)是偶数。故：

?（m）i?1?ai?m?（m）2?0(modm).

3、设m > 0是偶数，{a1, a2, ?, am}与{b1, b2, ?, bm}都是模m的完全剩余系，证明：{a1 ? b1, a2 ? b2, ?, am ? bm}不是模m的完全剩余系。

证明：因为{1, 2, ?, m}与{a1, a2, ?, am}都是模m的完全剩余系，所以

?ai??i?i?1i?1mmm(m?1)m?(mod m)。 (1) 22同理 ?bi?i?1mm(mod m)。 (2) 2如果{a1 ? b1, a2 ? b2, ?, am ? bm}是模m的完全剩余系，那么也有

?(ai?bi)?i?1mm(mod m)。 2联合上式与式(1)和式(2)，得到 0?mmm??(mod m)， 222这是不可能的，所以{a1 ? b1, a2 ? b2, ?, am ? bm}不能是模m的完全剩余系。 4、证明：（1）2730∣x13-x； （2）24∣x(x+2)(25x-1)；

（3）504∣x9-x3； （4）设质数p＞3，证明：6p∣xp-x。 证明：（1）因为2730=2×3×5×7×13，2,3,5，7,13两两互质，所以： 由x13-x=x (x12-1)≡0 (mod 2)知：2∣x13-x；13∣x13-x；

由x13-x=x (x12-1)=x(x2-1)(x2+1)(x8+x4+1)≡0 (mod 3)知：3∣x13-x； 由x13-x=x (x12-1)=x(x4-1)(x8+x4+1)≡0 (mod 5)知：5∣x13-x；

9

2

由x13-x=x (x12-1)=x(x6-1)(x6+1)≡0 (mod 7)知：7∣x13-x。 故有2730∣x13-x。 同理可证（2）、（3）、（4）。

初等数论练习题五

一、单项选择题

1、设x、y分别通过模m、n的完全剩余系，若（ C ）通过模mn的完全剩余系。 A. m、n都是质数，则my ? nx B. m≠n，则my ? nx C. （m，n）=1，则my ? nx D. （m，n）=1，则mx ? ny

2、1×3×5×…×2003×2005×2007×2009×2011标准分解式中11的幂指数是( A )。 A.100 B.101 C.99 D.102 3、n为正整数，若2n-1为质数，则n是( A )。

A.质数 B.合数 C.3 D.2k(k为正整数) 4、从100到500的自然数中，能被11整除的数的个数是( B )。 A.33 B.34 C.35 D.36

5、模100的最小非负简化剩余系中元素的个数是( C )。

A.100 B.10 C.40 D.4 二、填空题

1、同余方程ax+b≡0(modm)有解的充分必要条件是(a,m)∣b。

q2、高斯称反转定律是数论的酵母，反转定律是指设p与q是不相同的两个奇质数， ()?(?1)pp?1q?1?22(p)

q3、20122012被3除所得的余数为_1__。 4、设n是大于2的整数，则(-1)?(n)=__1__。 5、单位圆上的有理点的坐标是(?零的整数。

6、若3258×a恰好是一个正整数的平方，则a的最小值为362。

?72?7、已知2011是一素数，则??=_-1_。

2011??2aba2?b2,?a2?b2a2?ba?b)或(?,?222a?b222aba2?b2)，其中a与b是不全为

三、计算题

10

1、求32008×72009×132010的个位数字。

解：32008×72009×132010≡32008×（-3）2009×32010 ≡-32008+2009+2010 ≡-36027 ≡-3×（32）3013 ≡3(mod 10)。

2、求满足?(mn)=?(m)+?(n)的互质的正整数m和n的值。

解：由（m，n）=1知，?(mn)=?(m)?(n)。于是有：?(m)+?(n)= ?(m)?(n) 设?(m)=a， ?(n)=b，即有：a+b=ab。 显然a∣b，且b∣a，因此a=b。 于是由2a=a2 得a=2，即?(m)= ?(n)=2。 故 m=3,n=4或m=4,n=3。

3、甲物每斤5元，乙物每斤3元，丙物每三斤1元，现在用100元买这三样东西共100斤，问各买几斤?

解：设买甲物x斤，乙物y斤，丙物z斤，则

5x ? 3y ?z = 100， x ? y ? z = 100。

消去z，得到 7x ? 4y = 100。 (1) 显然x = 0，y = 25是方程(1)的解，因此，方程(1)的一般解是

13?x?4t ， t?Z ?y?25?7t?因为x＞0，y＞0，所以 0＜t ? 3。

即t可以取值t1 = 1，t2 = 2，t3 = 3。相应的x，y，z的值是

(x, y, z) = (4, 18, 78)，(8, 11, 81)，(12, 4, 84)。

四、证明题

1、已知2011是质数，则有2011|99????9。 ??2010个2011

证明：99=10-1≡0 (mod 2011)。 ???9???2010个2、设p是4n+1型的质数，证明若a是p的平方剩余，则p-a也是p的平方剩余。 证明：因为质数p=4n+1，a是p的平方剩余，所以

?p?a???a???1? ??p??=??p???p??=???????p?1?a??a?2???=(?1)?p??p??=1 ???? 即：p-a也是p的平方剩余。

3、已知p,q是两个不同的质数，且ap-1≡1 (mod q), aq-1≡1 (mod p), 证明：apq≡a (mod pq)。

11

证明：由p,q是两个不同的质数知（p，q）=1。于是由Fermat定理 ap≡a (mod p),

又由题设aq-1≡1 (mod p)得到：apq≡(aq)p≡ap (aq-1)p≡ap≡a (mod p)。 同理可证：apq≡a (mod q)。故：apq≡a (mod pq)。

4、证明：若m,n都是正整数，则?(mn)=（m,n）?([m,n])。

证明：易知mn与[m,n]有完全相同的质因数，设它们为pi (1?i?k)，则

?mn(1? ?（mn）111)(1?)?(1?) p1p2pk111)(1?)?(1?) p1p2pk?（[m,n]）?[m,n](1?又mn=（m,n）[m,n]

?（m,n)[m,n](1?故?（mn）111)(1?)?(1?)?(m,n)?([m,n])。 p1p2pk 类似的题：设m=m1m2，m1与m由相同的质因数，证明：?(m)=m2?(m1)。

初等数论练习题六

一、填空题

1、为了验明2011是质数，只需逐个验算质数2，3，5，…p都不能整除2011，此时，质数p至少是_43___。

2、最大公因数(4n+3,5n+2)的可能值是_1,7__。

|40!，即3α‖40!，则α=_18_。 3、设3α∣40!,而3α+1?4、形如3n+1的自然数中，构成模8的一个完全系的最小那些数是{1,4,7,10,13,16,19，22}。

5、不定方程x2+y2=z2,2|x, (x,y)=1, x,y,z>0的整数解是且仅是x = 2ab，y = a2 ? b2，z = a2 ? b2，其中a > b > 0，(a, b) = 1，a与b有不同的奇偶性。

6、21x≡9 (mod 43)的解是x≡25 (mod 43)。 7、??73?? = -1。 ?199?二、计算题 1、将

17写成三个既约分数之和，它们的分母分别是3，5和7。 10517xyz???，即35x ? 21y ? 15z = 17，因(35, 21) = 7，(7, 15) = 1，1?17，故解：设

105357有解。

12