9．解同余式3x ? 8 (mod 10)。

解：因为（3,10）=1,1|8，所以同余式有解，并且只有一个解。由3x?10y?8得一个解?所以同余式的解为x?6(mod10)。 10．解同余式组：

?x0?6

，y?1?0

?x?1(mod2)??x?1(mod3)。 ?x?1(mod5)?解：因为2，3，5两两互质，所以由孙子定理该同余式组有一个解。由孙子定理可得该同余式组的解为x ? 1(mod 30)。 11．解同余式28x ? 21 (mod 35)。

解 因为（28，35） = 7，而7|21，所以同余式28x ? 21(mod 35)有解，且有7个解。同余式28x ? 21(mod 35)等价于4x ? 3(mod 5)，解4x ? 3(mod 5)得x ? 2(mod 5)，故同余式28x ? 21(mod 35)的7个解为x ? 2，7，12，17，22，27，32(mod 35)。 12．解同余式组：

?x?1(mod3)。 ??x?2(mod7)解：由x?1(mod3)得x?1?3t1,t1?Z，将其代入x?2(mod7)得

1?3t1?2(mod7)，即3t1?1(mod7)，解得t1?5(mod7)，所以

t1?5?7t2,t2?Z，于是x?1?3t1?1?3(5?7t2)?16?21t2,t2?Z。所以同余式组的解

为x?16(mod21)。

初等数论第四次作业参考答案

证明题

1．证明：若a?b(modm)，c?d(modm)，则a?c?b?d(modm)。

m)，c?d(modm)得m|(a?b)，m|(c?d)，由整除的性质得证明：由a?b(modm|[(a?b)?(c?d)]，即m|[(a?c)?(b?d)]，所以a?c?b?d(modm)。

2．证明：设m, n为整数，求证m+n, m-n与mn中一定有一个是3的倍数。 证明：若m或n为3的倍数，则mn是3的倍数；

若m是3的倍数加1，n是3的倍数加1，则m-n是3的倍数；

若m是3的倍数加1，n是3的倍数加2，则m+n是3的倍数； 若m是3的倍数加2，n是3的倍数加1，则m+n是3的倍数；

若m是3的倍数加2，n是3的倍数加2，则m-n是3的倍数，结论成立。 3．证明：若a|c，b|d，则ab|cd。

证明：由a|c，b|d知存在整数p，q使得c?ap，d?bq，所以cd?apbq?abpq， 因为pq为整数，所以由整除的定义知ab|cd。 4．证明：若n为自然数，求证9n+1?8n+9(mod 64)。

证明：因为9?1(mod 8)，所以9k?1(mod 8)，k=2，3，…，n-1，于是 9n-1+…+92+9+1?n(mod 8)，所以9(9n-1+…+92+9+1)? n(mod 8)，

从而9?(9-1)?(9n-1+…+92+9+1)? 8n(mod 64)，即9(9n-1) ? 8n(mod 64)，所以 9n+1?8n+9(mod 64)。

5．若p为奇质数，证明2p | (22p-1–2)。

证明：因为p为质数，所以?(p)=p-1，又p为奇质数，所以(2，p)=1，于是由欧拉定理得2p-1?1(mod p)，两边平方得22p-2?1(mod p)，再由同余的性质有2?22p-2?2(mod 2p)，即：22p-1?2(mod 2p)。所以2p|(22p-1-2)。

6．证明：整数a，b对模m同余的充分与必要条件是m|(a?b)。

证明：设a?mq1?r，则r1?r2，因1，b?mq2?r2，0?r1，r2?m。若a≡b（mod m）此a?b?m(q1?q2)，即m｜a－b。 反之，若m｜a－b，则m|mq(1q?2)?(r1r?2)即a≡b（mod m）。

7．设a是大于1的整数，证明a4?4是合数。 证明：a?4?(a)?4a?4?4a

42222，因此m|r1?r2，但故rr1?r2?m，1?r2，

?(a2?2)2?4a2?(a?2?2a)(a?2?2a)22

22由于a?1且是整数，所以a?2?2a?1,a?2?2a?1，且均为整数，故当a是大于1

的整数时，a?4是合数。

4

8．设m为整数，证明：2|(m2?m?2)。

证明：因为m2?m?m(m?1)是两个连续整数的积，所以2|(m2?m)。 又2|2，所以由整除的性质知2|(m2?m?2)。

9．设p是质数，a与b是任二整数。证明：(a?b)p?ap?bp(modp)。 证明：因为p是质数，a与b是整数，所以ap?a(modp)，bp?b(modp)， 于是ap?bp?a?b(modp)。又(a?b)p?a?b(modp)，所以

(a?b)p?ap?bp(modp)。

10．证明：若a|m，b|m，并且(a,b)?1，则ab|m。

证明：由(a,b)?1得as?bt?1，所以asm?btm?m，于是ab|m。

初等数论练习题答案

信阳职业技术学院

2010年12月

初等数论练习题一

一、填空题

1、d(2420)=12; ?(2420)=_880_ 2、设a,n是大于1的整数，若an-1是质数，则a=_2. 3、模9的绝对最小完全剩余系是_{-4，-3，-2，-1,0,1,2,3,4}. 4、同余方程9x+12≡0(mod 37)的解是x≡11(mod 37)。

5、不定方程18x-23y=100的通解是x=900+23t，y=700+18t t?Z。. 6、分母是正整数m的既约真分数的个数为_?(m)_。 7、18100被172除的余数是_256。 8、??65?? =-1。 ?103?

9、若p是素数，则同余方程x p ? 1 ?1(mod p)的解数为 p-1 。 二、计算题

1、解同余方程：3x?11x?20 ? 0 (mod 105)。

解：因105 = 3?5?7，

同余方程3x2?11x?20 ? 0 (mod 3)的解为x ? 1 (mod 3)， 同余方程3x2?11x?38 ? 0 (mod 5)的解为x ? 0，3 (mod 5)， 同余方程3x2?11x?20 ? 0 (mod 7)的解为x ? 2，6 (mod 7)， 故原同余方程有4解。

作同余方程组：x ? b1 (mod 3)，x ? b2 (mod 5)，x ? b3 (mod 7)，

其中b1 = 1，b2 = 0，3，b3 = 2，6，

由孙子定理得原同余方程的解为x ? 13，55，58，100 (mod 105)。 2、判断同余方程x2≡42(mod 107)是否有解？

237）（）（）1071071071071073?1107?17?1107?1??2310727107222?（）??1，（）?（?1）（）??（）?1，（）?（?1）22（）??（）??1107107331077742?（）?11072?3?7解：(42)?（）?（2