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

?2011?三、计算题

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)。

证明：由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，解：设

1053571?17，故有解。

分别解 5x ? 3y = t 7t ? 15z = 17

得 x = ?t ? 3u，y = 2t ? 5u，u?Z，

t = 11 ? 15v，z = ?4 ? 7v，v?Z，

消去t得 x = ?11 ? 15v ? 3u，

y = 22 ? 30v ? 5u，

z = ?4 ? 7v， u，v?Z。

令u =0，v =-1得到：x =4，y =-8，z=3。即：

174?83??? 1053572、若3是质数p的平方剩余，问p是什么形式的质数？

3?解：∵ 由二次互反律???p???(?1)??p?12?p????， ?3??p??注意到p>3，p只能为p?1(mod 3)且????3?p?1(mod4)?1?

p??1(mod4)??1∴

?p?1(mod3)?3???p???1只能下列情况?p?1(mod4) ???d)?p??1(mo3 ?

p??1(mo4d)?∴ p?1(mod12)或p??1(mod12)。 3、判断不定方程x2+23y=17是否有解？

解：只要判断x2≡17(mod 23) 是否有解即可。 ∵ 17≡1(mod 4) ∴ ??17??23??6??2??3??3??17??2????????????????????????1 23???17??17??17??17??17??3??3?∴ x2≡17(mod 23)无解，即原方程无解。 三、论证题

1、试证对任何实数x,恒有〔x〕+〔x+〕=〔2x〕

12

证明：设x=[x]+α,0?α<1

①当0?α<

1211时, [x +]=[x], [2x]=2[x] ∴等式成立 2212②当?α< 1时, [x +]=[x]+1, [2x]=2[x]+1 ∴等式成立 故对任何实数x,恒有[x]+[x+]=[2x]。

2、证明：（1）当n为奇数时，3∣（2+1）；

n

12|（2+1）（2）当n为偶数时，3?。

证明：由2+1≡（-1）+1（mod 3）立得结论。 3、证明：（1）当3∣n（n为正整数）时，7∣（2-1）；

n

n

n

n

|（2+1） （2）无论n为任何正整数，7?。

证明：（1）设n=3m，则2-1=8-1≡0（mod 7），即：7∣（2-1）； （2）由于2≡1（mod 7）得 2+1≡2（mod 7），2

3m

3m+1

3m

n

m

n

n

+1≡3（mod 7），2

n

3m+2

+1≡5（mod 7）。

|（2+1） 故无论n为任何正整数，7?。

4、设m＞0，n＞0，且m为奇数，证明：（2-1，2+1）=1。 证明一：由m为奇数可知：2n+1︱2+1，又有2m-1︱2-1，

于是存在整数x,y使得：（2n+1）x=2+1, (2m-1)y=2-1。 从而（2n+1）x-(2m-1)y=2。这表明：

（2m-1，2n+1）︱2

由于2n+1，2m-1均为奇数可知：（2m-1，2n+1）=1。

证明二：设（2-1，2+1）=d，则存在s,t∈Z,使得2=sd+1, 2=td-1。由此得到：

2=(sd+1), 2=(td-1)

mn

n

mn

m

m

n

m

n

m

n

mnmn

mnmn

于是 2

mn

=pd + 1=qd – 1,p,q∈Z。所以：（q -p）d =2。

从而 d∣2，就有d =1或2。由因为m为奇数，所以d =1。

即（2-1，2+1）=1。

注：我们已证过：记Mn = 2n ? 1，对于正整数a，b，有(Ma, Mb) = M(a, b) 。

显然当a≠b，a,b为质数时，(Ma, Mb) =1。

m

n

初等数论练习题七

一、单项选择题

1、设a和b是正整数，则(A．1

[a,b][a,b],)=（ A ） ab B．a C．b D．(a,b)

2、176至545的正整数中，13的倍数的个数是（ B ） A．27

B．28 C．29

D．30

3、200!中末尾相继的0的个数是（ A ） A．49 B．50 C．51

D．52

4、从以下满足规定要求的整数中，能选取出模20的简化剩余系的是（ B ） A．2的倍数 B．3的倍数 C．4的倍数

D．5的倍数

5、设n是正整数，下列选项为既约分数的是（ A ） A．

21n?4n?12n?1n?1 B． C． D．

14n?32n?15n?23n?1二、填空题

1、314162被163除的余数是_1__。（欧拉定理） 2、同余方程3x≡5(mod13)的解是x≡5(mod13)。 3、(365)=1。 18474、［-π］＝-4。

5、为使n-1与3n的最大公因数达到最大的可能值，则整数n应满足条件n=3k+1,k∈Z。

6、如果一个正整数具有21个正因数，问这个正整数最小是26×32=576。 7、同余方程x3+x2-x-1≡0(mod 3)的解是x≡1,2(mod 3)。 三、计算题

1、求不定方程x ? 2y ? 3z = 41的所有正整数解。 解：分别解x ? 2y = t