（解答题36道）第四章 同余式

2011年2月《初等数论》题库

第四章 同余式

三、解答题

1、设(a,m)?1，k与m是正整数，又设x0k?a(modm)，证明同余方程xk?a(modm)的一切解x都可以表示成x?yx0(modm)，其中y满足同余方程yk?1(modm)。 解：设x1是x0k?a(modm)的任意一个解，

则一次同余方程yx0?x1(modm)有解y， 再由yka?ykx0k?(yx0)k?x1k?a(modm) 得yk?1(modm)，

即x1可以表示成x?yx0(modm)，其中y满足同余方程yk?1(modm)； 反之，易知如此形式的x是xk?a(modm)的解。

??3x?1?mod10?2、解同余方程组?

4x?7mod15?????3x??3x解：这同余方程组的解与同余方程组??4x??4x?1?mod2?,?1?mod5?,?7?mod3?,?7?mod5?的解相同，

但第二个同余方程3x?1?mod5?可化为x?2?mod5?, 第四个同余方程4x?7?mod5?可化为x??2?mod5?, 与x?2?mod5?矛盾，所以原同余方程组无解.

3、设素数p?2,求同余方程x2?1?modpl?的解 解：同余方程可写为?x?1??x?1??0?modpl?

由于?x?1,x?1?|2,所以上式等价于x?1?0?modpl?或x?1?0?modpl?

第 1 页 共 23 页

2011年2月《初等数论》题库

因此，对任意的l?1解为x??1,1?modpl? 解数为2.

4、求同余式f(x)?x3?4x2?5x?6?0(mod27) 解：∵f(x)?0(mod3),f?(x)?0(mod3)无公解

∴20有唯一解x?0(mod3)

以x?3t1代入f(x)?0(mod9)得f(0)?3t1f?(0)?0(mod9) 但f(0)?3(mod9)，f?(0)?5(mod9)

故3?6t1?0(mod9)，1?2t2?0(mod3)，t1?1(mod3) 因此t1?1?3t2,x?3?9t2是f(x)?0(mod9)的唯一解

将x?3?9t2代入f(x)?0(mod27)得f(3)?9t2f?(3)?0(mod27) 但f(3)?0(mod27)，f?(3)?8(mod27)

故8?9t2?0(mod27)，8t2?0(mod3)，t2?0(mod3)

设t2?3t3,x?3?27t3,x?3(mod27)是f(x)?0(mod27)的唯一解。

5、45x?21(mod132).

解： 因为(45,132)?3??? ,所以同余式有3个解.

将同余式化简为等价的同余方程15x?7(mod44). 我们再解不定方程15x?44y?,

得到一解(21,7). 于是定理4.1中的x0?21. 因此同余式的3个解为

x?21(mod132), x?21?1323(mod132)?65(mod132), (mod132)?109(mod132).

x?21?2?1323第 2 页 共 23 页

2011年2月《初等数论》题库

6、111x?75(mod321).

解：因为(111,321)?3???,所以同余式有3个解.

将同余式化简为等价的同余方程37x?25(mod107). 我们再解不定方程37x?107y?25, 得到一解(?8,3).

于是定理4.1中的x0??8. 因此同余式的3个解为

x??8(mod321), x??8?3213(mod321)?99(mod321), (mod321)?206(mod321).

x??8?2?3213

?x?1(mod7)?7、?x?2(mod8).

?x?3(mod9)?解: 因为(7,8,9)=1,所以可以利用定理5.1.我们先解同余式

72x?1(mod7),63x?1(mod8),56x?1(mod9),

得到x1?4(mod7),x2??1(mod8),x3??4(mod9).于是所求的解为

x?72?4?1?63?(?1)?2?56?(?4)?3(mod494) ??510(mod494)?478(mod494).

8、判定2x?x?3x?1?0?mod5?是否有3个解

32解：2x?x?3x?1?0?mod5?等价于x?3x?4x?3?0?mod5?，

3232又x5?x??x3?3x2?4x?3??x2?3x?5???6x2?12x?15?， 其中r?x??6x?12x?15的系数的都不是5的倍数，故方程没有3个解

2

9、解同余式9x?5(mod25)

第 3 页 共 23 页

2011年2月《初等数论》题库

解： 9x?5(mod25)??18x??10(mod25) ?7x??10(mod25) ?4x?5(mod25) ?x??5(mod25)

10、同余方程5x2?6x?49?0(mod60)的解的个数. 解：因为60?3?4?5 所以5x?6x?49?0(mod60)等价于

5x?6x?49?0(mod3) （1） 5x?6x?49?0(mod4) （2） 5x?6x?49?0(mod5) （3）

2222解同余方程（1）（2）（3）得到

xxx

112131?1 x2??1(mod3) ?1x2??1(mod4) ?1(mod5)

21所以原方程的解得个数有2*2*1=4个。

11、解同余式8x?9(mod11) 解：?(8,11)?1

?同余式只有一个解 ?11是素数??(11)?10 ?x?9?8?8(mod11)

9

?x?2(mod3)?12、解同余方程组?x?3(mod5)

?x?2(mod7)?解：利用孙子定理有，m?3?5?7?105,M1?35,M2?21,M3?15

第 4 页 共 23 页

2011年2月《初等数论》题库

?35M1?1(mod3)?M1?2(mod3)

'' 21M 15M?x0?2'?1(mod5)?M?1(mod7)?M2'?1(mod5) ?1(mod7)

3'3'2?35?2?3?21?1?2?15?1(mod105)?23(mod105)

13、求整数n，它被3，5，7除的余数分别是1，2，3。 ?n?1(mod3)?解：n是同余方程组?n?2(mod5)的解.

?n?3(mod7)?在孙子定理中，取m1?3,m2?5,m3?7,m?3?4?5?105，

M1?35,M2?21,M3?15, M'1??1,M'2?1,M'3?1,

则n?1?35?(?1)?2?21?1?3?15?1?52(mod105) 因此所求的整数n?52?105t,t?z.

?x?3?mod8??14、求?x?5?mod3?的解

??x?7?mod5?解：M?2?3?5?30；

M1?3?5?15而M1?M1?1?mod2?所以M1?1?mod2?

''同理M2?10而M2?M2?1?mod3?所以M2?1?mod3?

''M3?6，而M3?M3?1?mod5?所以M3?1?mod5?

''第 5 页 共 23 页

2011年2月《初等数论》题库

3所以x0?

?Mi?1i?Mi?1?15?3?1?10?5?1?6?7?17?mod30?

'?x??x15、解同余方程组??x??x?1(mod3)??1(mod5)?2(mod7)??2(mo11)

解：取m1?3,m2?5,m3?7,m4?11，都是素数，满足条件。

?M1?5?7?11,M2?3?7?11,M3?3?5?11,M4?3?5?7

我们来求M?1?1j.由于M1?(?1)?(1)?(?1)?1(mod3)知，

?11?M1M1?M1(mod3)，

?1因此可取M1?1.由M2?(?2)?(2)?1?1(mod5)知，

1?M2M2?M2(mod5)

?1因此可取M2?1，由M3?3?5?4?4(mod7)知，

?1?11?M3M3?4M3(mod7)

?1因此可取M3?2.由M?1?14?3?5?7?4?7?6(mod11)知，

1?M4M4?6M4(mod11)

?1因此可取M4?2.

?1?1所以同余方程的解为：

x?(5?7?11)?1?1?(3?7?11)?1?(?1)?(3?5?11)?2?2?(3?5?7)?2?(?2)(mod3?5?7?11)，

即x?385?231?660?420?394(mod1155)

16、解同余方程x?2x?8x?9?0?mod35? ?1?

43解：因为35?5?7，所以同余方程?1?等价于同余方程组

x?2x?8x?9?0?mod5? ?2?

43第 6 页 共 23 页

2011年2月《初等数论》题库

x?2x?8x?9?0?mod7? ?3?

43分别解同余方程?2?，?3?得到解

x1x1?1??1,x2?1??4?mod5? ?5,x3?2??2??3,x2?2??6?mod7?

这样，同余方程?1?的解x可由下面的方程组决定：x?a1?mod5?,x?a2?mod7?

其中a1?1或4，a2?3或5或6.利用孙子定理，取

m1?5,m2?7,m?35

M1?7,M2?5,7M1?1?mod5?,5M2?1?mod7?

''M1?3,M''2?3

则x?21a1?15a2?mod35?

将a1，a2所有可能的取值代入上式，得到方程?1?的全部解是 x1?21?1?15?3?31?mod35?x2?21?1?15?5?26?mod35?x3?21?1?15?6?6?mod35?x4?21?4?15?3?24?mod35?x5?21?4?15?5?19?mod35?x6?21?4?15?6?34?mod35?

17、解同余式8x?9?mod11? 解：??8,11??1

?同余式只有一个解

?11是素数 ??11??10

8mod11） ?x?9?8?（9第 7 页 共 23 页

2011年2月《初等数论》题库

18、解同余方程：31x?5?mod17? 解：若f?x0??0?modm?，则f?x0??b?x0??b?x0??modm?成立，反之，若

f?x0??b?x0??b?x0??modm?，则f?x0??0?modm?成立；

19、解同余方程3x14?4x10?6x?18?0(mod5).

解：由Fermat定理得，x5?x(mod5),因此，原同余方程等价于2x2?x?3?0(mod5) 将x?0,?1,?2(mod5)分别代入方程2x2?x?3?0(mod5)中进行检验，可得原同余方程的解是：x?1(mod5)

20、解同余方程x3?2x?12?（ 0mod81）解：方程x3?2x?12?（有一解x?0?mod3?， 0mod3）f??x??3x-2，f(0)?12, f'(0)??2 故x?3t1，f?x??x-2x?12， 3222解12?2?3t1?0(mod3)，得t1?2(mod3)，

t1?2?3t2 ，x?6?3?t2，f(6)?216 ，f'(6)?106,

2333解216?106?3t2?0(mod3)，得t2?0(mod3) 故t2?3t3，x?6?3t3，

2再解216?106?33t3?0?mod34?，得t3?1?mod34?

4故t3?1?3t4,x?33?3t4

原方程的解为x?33?mod81?

21、1、求同余方程9xo6(mod15)的所有解. 解：因为(9,15)?3且3整除6

所以同余方程9xo6(mod15)恰有三个解.

先求同余方程3xo2(mod5)的唯一解，显然

第 8 页 共 23 页

2011年2月《初等数论》题库

3x?210汉12(mod5),x4(mod5)

所以原同余方程9xo6(mod15)的三个解为

x汉4(mod15),x9(mod15),x 14(mod15)

2、求一次同余方程组

ì?xo2(mod35)???yo9(mod14) í??zo7(mod20)???解：由于35、14、20两两不互质，所以不能直接用孙子定理，原一次同余方程组与一

ì?xo2(mod5)???xo2(mod7)???xo9(mod2)?次同余方程组?等价 í?xo9(mod7)???xo7(mod4)??????xo7(mod5)显然，去掉相同的一次同余方程后，此一次同余方程组又与一次同余方程组

ì?????í??????xo2(mod5)xo2(mod7)xo9(mod2)xo7(mod4)（9?2）整除，此一次同余方程组又与一次等价，由于（4,2）?2能被

ì?xo2(mod5)??同余方程组{?íxo2(mod7)等价

??xo7(mod4)???74两两互质，由孙子定理知，原一次同余方程组有唯一解 此时5、、m=5创74=140,M1=7?4,28,M2=5?4iＮ3,i20,

NM3=5?7,,35,MiMi海1(modmi),1,求得M1=2,M2=6,M3=3 所以x捍228?22创206+7创35汉31087为原一次同余107(mod140方程组的解.

??3x?5y?1?mod7?3、解同余方程组?

2x?3y?2mod7????解:19y??4?mod7?

第 9 页 共 23 页

2011年2月《初等数论》题库

5y??4?mod7? y?2?mod7?

再代入3x?5y?1?mod7? 3x?10?1?mod7? x?4?mod7?

即方程组的解是x?4,y?2?mod7?

4、解同余方程6x?7?mod23?.

解： 6x?7?mod23??5x??7?3?2?mod23?

?3x??2?4??8?mod23? ?2x??8??7??10?mod23? ?x?5?mod23?

5、 解同余式. 12x?15?0(mod15)

解：因为?12,45??3︱5,所以同余式有解,而且解的个数为3.

又同余式等价于4x?5?0(mod15即4x?5?15y. 我们利用解不定方程的方法得到它的一个解是?10,3?, 即定理4.1中的x?10 . 因此同余式的3个解为

0x?10?mod45? ,

x?10?x?10?2?453453?mod45??25?mod25?, ?mod45??40?mod25?.

6、韩信点兵：有兵一队，若列成五行纵队，则末行一人，成六行纵队，则末行五人，成七行纵队，则末行四人，成十一行纵队，则末行十人，求兵数. 解：x?b1(mod5),x?b2(mod6),x?b3(mod7),x?b4(mod11)，此时：

第 10 页 共 23 页

2011年2月《初等数论》题库

m?5?6?7?11?2310

M1?6?7?11?462 M2?5?7?11?385 M3?5?6?11?330 M4?5?6?7?210

Mi??Mi?1(modmi),i?1,2,3,4 得

?=3,M?M1=1,M?=1,M?=1 234故：x?3?462b1?385?b2?330?b3?210?b4(mod2310)

又?b1?1,b2?5,b3?4,b4?10

?x?3?462?1?385?5?330?4?210?10?6731?2111(mod2310)

7、解同余方程

5x?3x?14?0(mod45).

解： 原同余方程等价于同余方程组

5x?3x?14?0(mod9)， (1)

5x?3x?14?0(mod5). (2)

先解同余方程(1).容易验证，同余方程x?3x?14?0(mod3)的解是x?2(mod3). 令x?2?3t并代入方程(1)，得到

55(2?3t)?3(2?3t)x?14?0(mod9) ， (3)

容易看出，这是一个对于任何整数t都成立的同余式，所以，方程(3)的解是(1)的解是 t?0,1,2(mod，于是方程3)第 11 页 共 23 页

2011年2月《初等数论》题库

x?2,5,8(mod9). (4)

再解同余方程(2).用x?0,1,2,3,4去验证，得到(2)的解是

x?1,2(mod5).

因此，原同余方程的解是下面六个同余方程组的解：

x?a1(mod9),a1?2,5,8， x?a2(mod5),a2?1,2.

利用孙子定理解这六个方程组，记

m1?9,m2?5,m?45,M1?5,M2?9,M1??2,M2???1

则

x?10a1?9a2(mod45).

将a1和a2的不同取值代入，得到所求的解是

x1?10.2?9.1?11(mod45)， x2?10.2?9.2?2(mod45)， x3?10.5?9.1?41(mod45)， x4?10.5?9.2?32(mod45)， x5?10.8?9.1?26(mod45)， x6?10.8?9.2?17(mod45).

28、解同余方程5x?6x?49?0(mod60).

第 12 页 共 23 页

2011年2月《初等数论》题库

（理由：考察孙子定理，解同余方程组.）

解：因为60?3?4?5，所以，原同余方程等价于同余方程组

?5x2?6x?49?0(mod3)????1???2?5x?6x?49?0(mod4)????2? ?2??5x?6x?49?0(mod5)????3?分别解同余方程?1?,?2?,?3?，得到解

x1?1,x2??1(mod3),x1x1?2??3??1??1??1,x2?2???1(mod4),

?1?mod5??x?a1?mod3???x?a2?mod4? ??x?a3?mod5?这样，原同余方程的解可由下面的方程组决定：

其中a1?1,?1;a2?1,?1;a3?1.利用孙子定理，令m1?3,m2?4,m3?5,m?60

M1?20,M2?15,M3?12???1,M3??3M1??2,M2

则 x?40a1?15a2?36a3(mod60)

将a1,a2,a3所有可能的取值带入上式，得到原方程的全部解是

x1?40?1?15?1?36?1?1(mod60)x1?40?(?1)?15?1?36?1??19(mod60)x1?40?1?15?(?1)?36?1?31(mod60)x1?40?(?1)?15?(?1)?36?1?11(mod60)

9、判定同余方程2x?3x?1?0(mod7)是否有三个解.

（理由：考察素数模的同余方程的解的个数，应用第四节的Fermat定理及定理4.）

3解：因为2?4?1?mod7?，所以，原方程与4?2x?4?3x?4?0(mod7)

3即x?2x?3?0(mod7)等价.

由于x7?x??x3?2x?3??x4?2x2?3x?4??12x2?16x?12， 所以，由定理4可知，原方程的解数小于3.

第 13 页 共 23 页

32011年2月《初等数论》题库

10、有一对士兵，若三人一组 则余一人，若五人一组，则余2人，若十一人一组，则余3人，已知这对士兵不超过170人，问这对士兵有几人？ 解：设士兵有x人，则由题意得

x?1(mod 3)，x?-2(mod 5)

x?3(mod 11) 由孙子定理得x?58(mod 165) 故x?58人.

12、求一个最小的自然数n，使得它的个5次方数.

解：可设n?2?3?5，由条件得

y12是一个平方数，它的

13是一个立方数，它的

15是一

??1?mod2?,??0?mod3?,??0?mod5?;

??0?mod2?,??1?mod3?,??0?mod5?;

??0?mod2?,??0?mod3?,???mod5?,

由孙子定理得??15?mod30?,??10?mod30?,??6?mod30?,故n?235.

15106

??3x?5y?1?mod7?13、解同余方程组 ?

2x?3y?2mod7????解：19y??4?mod7?

5y??4?mod7? y?2?mod7?

再代入3x?5y?1?mod7?

3x?10?1?mod7? x?4?mod7?

即方程组的解是x?4,y?2?mod7?

14、证明不定方程

x1?x2?x3?9x4?4

333没有整数解.

第 14 页 共 23 页

2011年2月《初等数论》题库

证明：取m?9.因为x13333?0，?1(mod9)，于是同余式

x1?x2?x3??4(mod9)

无解，由此知原方程无整数解.

15、解同余方程f?x??3x?4x?15?0?mod75?.

2解：因75?3?5，先解f2?x??0?mod?3，用逐一代入法得解x?0?mod3?；再解

2f?x??0?mod5?，用逐一代入法得f?x??0?mod5?的解为x?0,2?mod5?，对于

x?0?mod5?，令x?5t代入f?x??0?mod25t?2?mod5?，于是?得x?5?2?5t2??10?25t2，即x?10?mod2?5是f?x??0?mod25?的一个解，对于x?2?mod55t?4?mod5?，于是?，令x?2?5t代入f?x??0?mod?2得x?2?5?4?5t2??22?25t2，即x?22?mod25?是f?x??0?mod25?的一个解； 最

后构造同余方程组x?b1?mod3?，x?b2?mod25?，b1?0，b2?10,22，由孙子定理得

f?x??0?mod75?的两个解x?10,72?mod75?.

16、设p是素数，0?a?p，证明：

(p?1)(p?2)???(p?a?1)a!x?b(?1)a?1?modp?.

是同余方程ax?b?modp?的解. 解：首先易知b(?1)a?1(p?1)(p?2)???(p?a?1)a!是整数，又由?a,p??1知方程ax?b?modp?解唯一，

故只须将x?b(?1)a?1(p?1)(p?2)???(p?a?1)?modp?代入ax?b?modp?验证它是同余方程的解

a!即可.

17、证明：同余方程a1x1?a2x2?...?anxn?b?modm?有解的充要条件是

?a1,a2,...,an,m??d|b.

若有解，则恰有

d?mn?1个解，modm.

第 15 页 共 23 页

2011年2月《初等数论》题库

解：必要性显然，下证充分性.当n?1时，由定理2知命题成立.假设n?k时结论已真，考虑

a1x1?a2x2?...?anxn?b?modm?，令?a1,a2,...,an,m??d1，?d1,ak?1??d，因为同余

modm.方程ak?1xk?1?b?modd1?有解，其解数为d，记m?m1d1，则解数为dm1，modd1，

现在固定一个解xk?1，由归纳假定知a1x1?a2x2?...?akxk?b?modm? 有解，其解数为

d1mk?1，modm，从而a1x1?ax2?2..?.anxn?b?mmo?d 有解，其解数为

dmk?1?d?mk1?d1m，modm.由归纳原理知命题对于一切n?1成立.

18、解同余方程：3x2?11x?20?0?mod15?.

解：因105?3?5?7

同余方程3x2?11x?20?0?mod3?的解为x?1?mod3?，

同余方程3x2?11x?20?0?mod5?的解为x?0,3?mod5?，

同余方程3x2?11x?20?0?mod7?的解为x?2,6?mod7?，

故原同余方程有4解，mod105.

作同余方程组：x?b1?mod3?，x?b2?mod5?，x?b3?mod7?，b1?1,b2?0,b33,? 2,6由孙子定理得原同余方程的解为x?13,55,58,100?mod105?.

?x?8(mod15)19、解同余方程组：??x?5(mod8)

??x?13(mod25)。解：因为?15,8??1|8?5，?15,25??5|8?13，?8,25??1|8?5.

故原同余方程组有解，解数唯一mod?15,8,25??600.

将第一个同余方程的解 x?8?15t1,t1?Z，代入第二个同余方程 得t1?3?mod8?，即t2?3?8t1,t2?Z，x?53?20t2，

代入第三个同余方程 得t2?3?mod5?，即t3?3?5t2,t3?Z，x?413?600t， 所以原同余方程组的解为x?413?mod600?.

第 16 页 共 23 页

其中

2011年2月《初等数论》题库

7mod15）?x?（?2mod35） 20、讨论并解答：?x?（?x?16（mod21）?（15，35）?5且7?（2mod5）解：∵ （15，21）?3且7?16（mod3）

（21，35）?7且2?16（mod7）

∴原同余式组等价于

7mod3）?x?（?x?（7mod5）??x?（2mod5） ?

x?（2mod7）??x?16（mod3）?（mod7）?x?161mod3）?x?（?2mod5）??x?（ ?x?（2mod7）?M?3?5?7?105，

M1?Mm1?35，M2?Mm2?21，M3?Mm3?15

，1mod3）由M1M1?（得M?2

i同理，M2=1，M3=1

1mod105）∴x?1?35?2?2?21?1?2?15?（

（mod105）?37（mod105） ?142

，，21、解同余式8x?9（mod11）

解：x?9???1?8?110?9?8?7?6?5?48！

8mod11） ???9??15?（

22、解同余式8x?9（mod11） （用三种方法解）

（8，11）?1 解：?∴同余式只有一个解

第 17 页 共 23 页

2011年2月《初等数论》题库

法1：∵11是素数，??11??10 ?x?9?89?（ 8mod11）8?1法2：x?9?（?1）10?9?8?7?6?5?48！?（?9）?15?（8mod11）

法3：（求解不定方程8x－11y?9）

23、解同余式 6x?27x?17x?20?0(mod30) 解：设

f(x)?6x?27x?17x?203232

由定理3知解同余式f(x)?0(mod30)可先分别解以下两同余式 f(x)?0(mod5),f(x)?0(mod6),

容易验证第一个同余式有解x?0,1,2(mod5) 第二个同余式有解x?2,5(mod6)

由孙子定理，当(a,a)取(0,2),(0,5),(1,2),(1,5),(2,2),(2,5)时，得到

12f(x)?0(mod30)的６个解x?6a1?12a2?2,5,11,17,20,26(mod30)

24、求相邻的四个整数，它们依次可被2，3，5及7整除 解：设这四个相邻的整数是x?1,x,x?1,x?2，按要求应满足

x?1?0(mod2), x?0(mod3), x?1?0(mod5), x?2?0(mod7).

2222所以，这是一个解同余方程组问题，这里m1?2,m2?3,m3?5,m4?7

22222222222222两两既约.满足定理1的条件.M1?3?5?7,M2?2?5?7,

M3?2?3?7,M4?2?3?5

2?1?121?1?1(mod2)知1?M1?M1?M1(mod2) 由M1?1?222222因此可取M1?1?1，由M2?10?7?1?4?4(mod3)

第 18 页 共 23 页

2222011年2月《初等数论》题库

知1?M2?M2?1?4M1?1(mod32)因此可取M2?1??2

由M3?22?212?22?42??11(mod52)知1?M3?M3?1??11M3?1(mod52)

2??22M3?1?3M3(mod5) 16?24M3?12?1??M3(mod5)

?12因此可取M3?1?9，由M4?(?13)(?24)?3?6?18(mod72) 知1?M4?M4?1?18M4?1(mod72) 3?54M4?1?5M4?1(mod72) 30?50M4?1?M4?1(mod72)

因此可取M4?1??19，因而由定理1知

x?3?5?7?1?1?2?5?7(?2)?0?2?3?7?9?(?1)?2?3?5?(?19)?(?2)(mod2?3?5?7)2222222222222222 x?11025?15876?34200?29349(mod44100)

所以满足要求的四个相邻整数有无穷多组，它们是29348?44100t,29349?44100t,

29350?44100t,29351?44100t,t?0,?1,?2,?

29349，29350，29351. 最小的这样的四个相邻的正整数是29348，25、解同余式f?x??0(mod35)，f?x??x?2x3?8x?9

4??f解：上式与同余式组???f?x??0(mod5)等价，

?x??0(mod7)容易证第一个同余式有两个解即：x?1，4(mod5)，第二个同余式有三个解即

x?3，5，6(mod7)，故题中所求同余式f?x??0(mod35)，f?x??43x?2x?8x?9有6

个解，即同余式组的解x?b1(mod5)，x?b1(mod7)，b1?1,4，b2?3,5,6

由孙子定理得x?21b1+15b2(mod35)，以b1，b2的值分别代入即得全部解：

x?31，26，6，24，19，34(mod35)

26、求同余方程x?1(mod2)的解. 解：当l?1时，解数为1，x?1(mod2)

第 19 页 共 23 页

2l2011年2月《初等数论》题库

当l?2时，解数为2,x??1,1(mod22)

当 l?3时，同余方程可写为(x?1)(x?1)?0(mod2l) 由于x是解时，必可表为x?2y?1.带入上式得

4y(y?1)?0(mod2)即y(y?1)?0(mod2ll?2)

所以必有y?0,?1(mod2l?2) 因此，解x必满足x?1,?1(mod2l?1)

l?1l?1l所以原方程的解是x?1，1+2,?1,?1?2(mod2)解数为4.

27、解同余方程组

x?b1(mod5),x?b2(mod6),x?b3(mod7),x?b4(mod11)

解：由题意可知：

m?5?6?6?7?11?2310,M1?6?7?11?462

M2?5?7?11?385,M3?5?6?11?330,M4?5?6?7?210

解得

'MiMi?1(modmi),i?1,2,3,4

得

M1?3,M2?1,M3?1,M4?1

''''x?3?462b1?385b2?330b3?210b4(mod2310)

即为所求

?x?1(mod3)??x??1(mod5)28、求? 的整数解

x?2(mod7)???x??2(mod11)第 20 页 共 23 页

2011年2月《初等数论》题库

解：?m1?3,m2?5,m3?7,m4?11 ?m?3?5?7?11?1155 由孙子定理得：

M1?385,M2?231，M3?165，M4?245

?385M1'?1(mod3)?M1'?1(mod3)

231M2'?1(mod5)?M2'?1(mod5) 165M3'?1(mod7)?M3'?2(mod7) 245M4'?1(mod11)?M4'?3(mod11)

?x0?1?385?1?(?1)?231?1?2?165?2?(?2)?245?3

?556(mod1155)

?所有整数解为：x0?1155t?556(t?Z)

29、解同余方程

325x?20(mod161)

解：同余方程(6)即是

3x?20(mod161)

解同余方程

161x??20(mod3)

2y?1(mod3)，

得到y?2(mod3)，因此方程的解是

第 21 页 共 23 页

2011年2月《初等数论》题库

x?

30、解同余方程组

20?2?1613?114(mod161)

?3x?5y?38(mod47) ??x?y?10(mod47) 解：消去y得8x?41(mod47)解得x?11(mod47) 代入原方程组中的第二式得y?1(mod47)

?x?11(mod47) 即?

y?1(mod47)?

31、解同余方程17x?16?0(mod25)

解：17x?6?0(mod25)?34x?12?0(mod25) 有9x?12?0(mod25)?3x?4?0(mod25) 则24x?32?0(mod25)??x?7?0(mod25) 所以x?7(mod25)

?x?2(mod5)?32、解同余方程的解 ?x?3(mod8)

?x?1(mod7)? 解：M?5?8?7?280，

M1?56,M2?35,M3?40???M1?1,M2?3,M3?10，

，

1mod280) x?56?1?2?35?3?3?40?10?（?827(mod280)?267(mod280) ??13(mod280)

第 22 页 共 23 页

2011年2月《初等数论》题库

33、解同余方程：3x2?11x?20?0(mod105)

解：因105?1?3?7，同余方程3x?11x?20?0(mod3)的解为同x?1(mod3)，同余方程

223x?11x?38?0(mod5)的解为x?0,3(mod5)，同余方程3x?11x?20?0(mod7)2的解为x?2,6(mod7)，故原同余方程有4解，mod105.作同余方程组：xob1(mod3)，

xob2(mod5)，xob3(mod7)，其中b1?1，b2=0,3，b3=2.

34、解方程21xo38(mod117) 解：21x痕38(mod117) ?9y痕4(mod21)117y?21z?38(mod21) 4(mod9)

酆3z 酆0?w-4(mod9)酆9w1(mod3)

4(mod3)

最后同余方程无解，所以原方程无解.

35、化简同余方程21x18+2x15-10x10+4x-3 0(mod7) 解： 先去掉系数项为7的项得：2x-10x+4x-3 0(mod7)

做多项式除法得：

2x-10x15101510+4x-3=(x-x)(2x-x+2x)+ (-x+2x+4x-3)783243

由此得到等价同余方程：-x+2x+4x-3 0(mod7) 直接代入x=0,北1,

36、解同余方程81x+24x+5x+23?0?mod7?

32432, 3，计算知同余方程无解.

解：原同余方程即是?3x+3x-2x+2?0?mod7?

32用x?0,?1,?2,?3，每个代入验证，得到它的解是 x1?1,x2?2,x3??2?mod7?

第 23 页 共 23 页

本文来源：https://www.bwwdw.com/article/pzxw.html