《初等数论》第三版习题解答

《初等数论》习题解答（第三版）

第一章 整数的可除性

§1 整除的概念·带余除法 1．证明定理3

定理3 若a1，a2，，an都是m得倍数，q1，q2，，qn是任意n个整数，则

q1a1?q2a2?证明：

?qnan是m得倍数．

a1,a2,an都是m的倍数。

pn使 a1?p1m,a2?p2m,? 存在n个整数p1,p2,又q1,q2,,an?pnm

,qn是任意n个整数

?qnan

?q1a1?q2a2??q1p1m?q2p2m??(p1q1?q2p2?即q1a1?q2a2??qnpnm?qnpn)m

?qnan是m的整数

2．证明 3|n(n?1)(2n?1) 证明

n(n?1)(2n?1?)nn(? 1n)?(?2n? ?n(n?1)(n?2)?n(?1n)n(? 又

n(n?1)(n?2)，(n?1)n(n?2)是连续的三个整数

故3|n(n?1)(n?2),3|(n?1)n(n?1)

?3|n(n?1)(n?2)?(n?1)n(n?1)

从而可知

3|n(n?1)(2n?1)

3．若ax0?by0是形如ax?by（x，y是任意整数，a，b是两不全为零的整数）的数中最小整数，则(ax0?by0)|(ax?by)．

1 / 77

《初等数论》习题解答（第三版）

证：

a,b不全为0

?在整数集合S??ax?by|x,y?Z?中存在正整数，因而有形如ax?by的最小整数

ax0?by0

?x,y?Z，由带余除法有ax?by?(ax0?by0)q?r,0?r?ax0?by0

则r?(x?x0q)a?(y?y0q)b?S，由ax0?by0是S中的最小整数知r?0

?ax0?by0|ax?by

ax0?by0|ax?by （x,y为任意整数） ?ax0?by0|a,ax0?by0|b ?ax0?by0|(a,b). 又有(a,b)|a，(a,b)|b ?(a,b)|ax0?by0 故ax0?by0?(a,b)

4．若a，b是任意二整数，且b?0，证明：存在两个整数s，t使得

a?bs?t,|t|?|b| 2成立，并且当b是奇数时，s，t是唯一存在的．当b是偶数时结果如何？ 证：作序列

,?3bbb3b,?b,?,0,,b,,2222qq?1b?a?b成立 22则a必在此序列的某两项之间

即存在一个整数q，使

(i)当q为偶数时，若b?0.则令s?qq,t?a?bs?a?b，则有 22bqqq0?a?bs?t?a?b?a?b?b?t?

2222 若b?0 则令s??,t?a?bs?a?q2bqb，则同样有t?

22(ii)当q为奇数时，若b?0则令s?q?1q?1,t?a?bs?a?b，则有 22 2 / 77

《初等数论》习题解答（第三版） ?bbq?1q?1?t?a?bs?a?b?a?b?0?t? 2222bq?1q?1综上所述，存在性,t?a?bs?a?b，则同样有t?2，22若 b?0，则令s??得证．

下证唯一性

当b为奇数时，设a?bs?t?bs1?t1则t?t1?b(s1?s)?b 而t?bb,t1??t?t1?t?t1?b 矛盾 故s?s1,t?t1 22b为整数 2当b为偶数时，s,t不唯一，举例如下：此时

3?bbbbb?b?1??b?2?(?),t1?,t1?22222

§2 最大公因数与辗转相除法 1．证明推论4.1

推论4.1 a，b的公因数与（a，b）的因数相同． 证：设d?是a，b的任一公因数，?d?|a，d?|b 由带余除法

a?bq1?r1,b?r1q2?r2,?rnqn?1,0?rn?1?rn?rn?1??(a,b)?rn

?d?|a?bq1?r1， d?|b?r1q2?r2，┄, d?|rn?2?rn?1qn?rn?(a,b),

即d?是(a,b)的因数。

3 / 77

,rn?2

?rn?1qn?rn,rn?1?r1?b 《初等数论》习题解答（第三版）

反过来(a,b)|a且(a,b)|b，若d??|(a,b),则d??|a,d??|b，所以(a,b)的因数都是a,b的公因数，从而a,b的公因数与(a,b)的因数相同。

2．证明：见本书P2，P3第3题证明。

3．应用§1习题4证明任意两整数的最大公因数存在，并说明其求法，试用你的所说的求法及辗转相除法实际算出（76501，9719）．

解：有§1习题4知：

?a,b?Z,b?0,?s,t?Z,使a?bs?t,|t|?b。， 2??s1,t1，使b?s1t?t1,|t1|??sn,tn,tn?2?tn?1sn?tn; ?sn?1,tn?1,tn?1?tnsn?1?tn?1;

且|tn|?|t|b?,222,如此类推知：

|tn?1||tn?2|?2?22?|t||b| ?2n2n?1而b是一个有限数，??n?N,使tn?1?0

?(a,b)?(b,t)?(t,t1)?(t1,t2)??(tn,tn?1)?(tn,0)?tn，存在其求法为：

(a,b)?(b,a?bs)?(a?bs,b?(a?bs)s1)??(76501,9719)?(9719,76501?9719?7)?(8468,9719?8468)?(1251,8468?1251?6)??(3,1)?14．证明本节（1）式中的n?

logb log2 4 / 77

《初等数论》习题解答（第三版）

证：由P3§1习题4知在（1）式中有 0?rn?1?rn?rn?1rn?2?2?22?r1b，而rn?1 ?2n?12n ?1?logblogbbn?n?logb?n?， ，即 ,?2?b2log2log22n§3 整除的进一步性质及最小公倍数

1．证明两整数a，b互质的充分与必要条件是：存在两个整数s，t满足条件ax?bt?1． 证明 必要性。若(a,b)?1，则由推论1.1知存在两个整数s，t满足：as?bt?(a,b)，

?as?bt?1

充分性。若存在整数s，t使as+bt=1，则a，b不全为0。 又因为(a,b)|a,(a,b)|b，所以(a,b|as?bt) 即(a,b)|1。 又(a,b)?0，?(a,b)?1 2．证明定理3 定理3 ?a1,a2证：设[a1,a2,,an???|a1|,|a2|,|an|?

,n)

,an]?m1，则ai|m1(i?1,2,,n)又设[|a1|,|a2|,∴|ai||m1(i?1,2,,|an|]?m2

则m2|m1。反之若|ai||m2，则ai|m2，?m1|m2 从而m1?m2，即[a1,a2,3．设anxn?an?1xn?1?,an]=[|a1|,|a2|,,|an|]2

?a1x?a0 （1）

是一个整数系数多项式且a0，an都不是零，则（1）的根只能是以a0的因数作分子以an为分母的既约分数，并由此推出2不是有理数．

证：设（1）的任一有理根为

p，(p,q)?1,q?1。则 q 5 / 77

《初等数论》习题解答（第三版）

ppan()n?an?1()n?1?qqanpn?an?1pn?1q??a1p?a0?0 q?a1pqn?1?a0qn?0 （2）

?a1pqn?1?a0qn，

由(2)?anpn?an?1pn?1q?所以q整除上式的右端，所以q|anpn，又(p,q)?1,q?1， 所以(q,pn)?1,?q|an； 又由（2）有anpn?an?1pn?1q??a1pqn?1??a0qn

因为p整除上式的右端，所以P|a0qn ，(p,q)?1,q?1，所以(qn,p)?1, ∴p|an 故（1）的有理根为

p，且p|a0,q|an。 q假设2为有理数，x?2,?x2?2?0，次方程为整系数方程，则由上述结论，可知其有有理根只能是

?1,?2，这与2为其有理根矛盾。故2为无理数。

另证，设2为有理数2=

p,(p,q)?1,q?1，则qp22?2,?2q2?p2,?(p2,q2)?(2q2,p2)?q2?1

q但由(p,q)?1,q?1知(p2,q2)?1，矛盾，故2不是有理数。 §4 质数·算术基本定理 1．试造不超过100的质数表 解：用Eratosthenes筛选法 （1）算出100?10a

（2）10内的质数为：2，3，5，7

6 / 77

《初等数论》习题解答（第三版）

（3）划掉2，3，5，7的倍数，剩下的是100内的素数 将不超过100的正整数排列如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 2．求82798848及81057226635000的标准式．

解：因为8|848，所以8|A,A?82798848?8?10349856?23?B， 又8|856，所以8|B，B?8?1293732?23?C， 又4|32，所以4|C，C?4?323433?22?D

又9|（3+2+3+4+3+3），所以9|D，D?9?35937?32?E， 又9|（3+5+9+3+7），所以9|E，E?9?3993 又3993?3?1331?3?113 所以A?2835113；

同理有81057226635000?23?33?54?73?112?17?23?37。 3．证明推论3.3并推广到n个正整数的情形． 推论3.3 设a，b是任意两个正整数，且

?1?2a?p1?p2??n?pn，?i?0，i?1,2,,k， ,k，

?k?pk，

?2b?p1?1?p2??n?pn，?i?0，i?1,2,?1?2?p2?则(a,b)?p1?k?1?2?pk?p2?，[a,b]?p1 7 / 77

《初等数论》习题解答（第三版）

其中?i?min(?i,?i)，?i?min(?i,?i)，i?1,2,证：

,k

?i?min(?i,?i)，?0??i??i,0??i??i

k)

∴ pi?i|pi?i,pi?i|pi? i(i?1,2∴

?pii?1k?i?pi，?pii?1i?1k?ik?i?ip?i. i?1k?1?2p2∴ p1?1?2p2∴ p1?k?1?2pk|(a,b)，又显然(a,b)|p1p2?k?1?2pk?(a,b)，同理可得p1p2?kpk

?kpk?[a,b]，?i?max{?i,?i}

推广

?12设a1?p1?11p2?22pk?1k,a2?p1?21p2pk?2k,?n2,an?p1?n1p2?nkpk

(其中pj为质数j?1,2,?i1?i2p1p2?ikpk?(a1,a2,,k,ai为任意n个正整数i?1,2,,n,?ij?0)， 则

,an),?ij?min{?ij},1?i?nj?1,2,,k ,k

?i1?i2p1p2?ikpk?[a1,a2,,an],?ij?max{?ij},j?1,2,1?i?n4．应用推论3.3证明§3的定理4（ii）

?1?2p2证：设a?p1?k?1pk，b?p1?1p2?kpk，

其中p1, p2, ?, pk是互不相同的素数，?i，?i（1 ? i ? k）都是非负整数，有

?1(a,b)?p1?1p2?kpk，?i?min{?i,?i}，1?i?k，?k[a,b]?p1p2由此知(a, b)[a, b] =

?1?1pk，?i?max{?i,?i}，1?i?k。min{?i,?i}?max{?i,?i}i

?pii?1k?i??i??pi?1k??pi?i??i=ab；从而有[a,b]?i?1kab． (a,b)５．若2n?1是质数（n>1），则n是2的方幂． 证：（反证法）设n?2kl(l为奇数）， 则2n?1?22?l?1?(22)l?1?(22?1)[22kkkk?(l?1)?22?(l?2)?k?1]

8 / 77

《初等数论》习题解答（第三版）

∵ 1?22?1?(22)l?1?2n?1， ∴ 2n?1为合数矛盾，故ｎ一定为２的方幂． §5 函数[x],{x}及其在数论中的一个应用 1．求30！的标准分解式．

解：30内的素数为2，3，5，7，11，13，17，19，23，29

kk?2?????2???3???4???5???2??2??2??2??2??15?4?3?1?0?23

?30??30??30??30??30?

?3?????2???3???4???3??3??3??3??5?????2???3???5??5??5??7?????2???7??7??13?????2???13??13??17?????2???17??17??30??30??30??30??30??30??30??30??30??30??30??30??30??10?3?1?0?14

?6?1?0?7

?30??30??4?0?4，?11?????2???11??11??30??30??2?0?2，?13?????2???13??13??2?0?2

?2?0?2

?1?0?1，?19??19??23??29?1

∴ 30!?223?314?55?74?112?132?17?19?23?29 2．设n是任一正整数，?是实数，证明：

??n???(i) ??????

n????n?? (ii) ?????????????????nn????证：(i)设[?]?m.则由性质II知m???m?1,

?1??n?1? 9 / 77

《初等数论》习题解答（第三版）

所以 nm?n??nm?n, 所以nm?[n?]?nm?n，所以m?[n?]?m?1，又在ｍ与ｍ+１之间只有唯一整数ｍ，n所以[[n?]]?m?[?]． nkk?1?{?}?,k?0,1,2,nn,n?1,

(ii) [证法一]设

则k?n{?}?k?1,?[n?]?n[?]?k ①当i?k?n?1时,{?}?ik?1?ii??1,[??]?[?] ; nnnik?ii??1,[??]?[?]?1; nnn②当i?k?n时,2?{?}?1n?1?[?]?[??]??[??]nnn?1n?11n?1?kii??[??]??[??]??[??]

nni?n?kni?0i?0?(n?k)[?]?k([?]?1)?n[?]?ki??[??]?[n?]

ni?0[证法二] 令f(?)?n?1i[??]?[n?], ?ni?0n?1n?11i?1f(??)??[??]?[n??1]?f(?)

nni?0n?11i?1f(??)??[??]?[n??1]?f(?)

nni?0?f(?)是以

1为周期的函数。 n 10 / 77

《初等数论》习题解答（第三版）

又当??[0,1)时,f(?)?0?0?0,???R,f(?)?0，

即

?[??n]?[n?]。

i?0n?11[评注]：[证一]充分体现了 常规方法的特点，而[证二]则表现了较高的技巧。 3．设?，?是任意二实数，证明： (i) [?]?[?]?[???]或[???]?1 (ii) [2?]?[2?]?[?]?[???]?[?] 证明：（i）由高斯函数[x]的定义有

??[?]?r,??[?]?s,0?r?1;0?s?1。则

????[?]?[?]?r?sr,?s ?1 当r?s?0时,[???]?[?]?[?] 当r?s?0时,[???]?[?]?[?]?1

故 [???]?[?]?[?]或[???]?1?[?]?[?] （ii）设??[?]?x,??[?]?y,0?x,y?1， 则有0?x?y?{?}?{?}?2 下面分两个区间讨论：

①若0?x?y?1，则[x?y]?0，所以[???]?[?]?[?]，所以

[2?]?[2?]?[2[?]?2x]?[2[?]?2y]?2[?]?2[?]?2([x]?[y])?2[?]?2[?]?[?]?[?]?[?]?[?]?[?]?[???]?[?]

②若1?x?y?2，则[x?y]?1，所以[???]?[?]?[?]?1。 所以

11 / 77

《初等数论》习题解答（第三版）

[2?]?[2?]?[2[?]?2x]?[2[?]?2y]?2[?]?2[?]?2([x]?[y])?2[?]?2[?]?2([x]?[1?x])x?1?y?????

?[?]?[?]?[?]?[?]?2?2([x]?[?x])?2[?]?2[?]?1?[?]?[???]?[?]（ii）（证法2）由于?，?对称，不妨设{?}?{?}

[2?]?[2?]?[2([?]?{?})]?[2([?]?{?})]

?2[?]?2[?]?[2{?}]?[2{?}]

?2[?]?2[?]?[{?}?{?}]

?[?]?[?]?([?]?[?]?[{?}?{?}]) ?[?]?[?]?[[?]?{?}?[?]?{?}]

?[?]?[???]?[?]

4. (i) 设函数错误！未找到引用源。在闭区间Q?x?R上是连续的，并且非负，证明:和式

表示平面区域Q?x?R，0?y?f(x)内的整点（整数坐标的点）的个数. (ii) 设p，q是两个互质的单正整数，证明：

(iii) 设错误！未找到引用源。，T 是区域错误！未找到引用源。 内的整点数，证明：

(iv) 设错误！未找到引用源。，T 是区域错误！未找到引用源。，错误！未找到引用源。，

12 / 77

《初等数论》习题解答（第三版）

错误！未找到引用源。 内的整点数，证明：

证明：(略)

5. 设错误！未找到引用源。任一正整数，且错误！未找到引用源。，p 是质数，错误！未找到引用源。，证明：在错误！未找到引用源。的标准分解式中，质因数p的指数是

其中错误！未找到引用源。.

证明：在错误！未找到引用源。的标准分解式中，质因数p的指数有限，即

错误！未找到引用源。，错误！未找到引用源。

所以

而

第二章 不定方程 §2．1 习题

1、解下列不定方程 a)15x?25y? 1 00b)306x?360y?630

13 / 77

《初等数论》习题解答（第三版）

解：a) 原方程等价于：3x?5y?20 显然它有一个整数解 x0?10,y0??2 ，

故一般解为 ?t?x?10?5(t?0?,1,?2, )y??2?3t?b)原方程等价于：17x?20y?35 显然它有一个整数解 x0??7?35,y0??6?35

故一般解为 ??2t0?x??7?35(t?0?,1,?2, )?1t7?y??6?352、把100分成两份，使一份可被7整除，一份可被11整除。 解：依题意 即求 7x?11y?100 的正整数解，解得 x0?8,y0?4

一般解是： ??x?8?11t(t?0,?1,)

?y?4?7tb?0,(a,b?)

但除 t?0外无其他正整数解，故有且只有 100?56?44 3、证明：二元一次不定方程 ax?by?,Na?0, 的非负整数解为 ?? 或 ???1

?ab??ab?证明：当N?0时，原方程没有整数解，而 ???1?0 故命题正确

?ab? 当N?0时，原方程有且只有一个非负整数解 ?0,0? 而 ???0 ???1?1

?ab??ab? 因为 ?a,b??1 所以

原方程有整数解 ?x0,y0?,y0?(?1)n?1?q1, 其中

?N??N??N??N??N?,qn?1?N,x0?(?1)n?q2,,qn?1?N

a??q1,q2,q3,b,qn?，由于a?b?0，故x0,y0中一正一负，可设x?0,y?0

原方程的一般解是：??x?x0?bt?t?0,?1,y?y?at0??

要求x0?bt?0,y0?at?0?仅当 ?x0y?t??0， bay0?y??y?是整数时，才能取 t???0? ，否则 t???0? a?a??a? 14 / 77

《初等数论》习题解答（第三版）

故这个不等式的整数解个数T 是 ：

当是整数时 T??0????0??1??0???0??1

?b??a??b??a?因而 ????0???0??T????1

?ab??b??a??ab?当

?x??y??x??y??N??x??y??N?y0?x??y??x??y?不是整数时 T??0????0???0???0??1 a?b??a??b??a???x0??y0???b???a??N??????因而 ???? 所以 ?(m)

?ab???x0??y0??b???a??1??????

?x?x0?bt证明2：二元一次不定方程ax ? by = N的一切整数解为?，t?Z，于

y?y?at0?是由x ? 0，y ? 0得?整数个数为

：

4、证明：二元一次不定方程 ax?by?N,(a,b)?1,a?1,b?1，当 N?ab?a?b 时有非负整数解，N?ab?a?b 则不然。

证明：先证后一点，当 N?ab?a?b时，原方程有非负整数解 ?x0,y0? 则d?(m1,m2).

y0xyxN，故此区间内的?t?0，但区间[?0,0]的长度是

ababab[N]或[N]? 1。

abab?bx0?1,ay0?1?x0?1?bk,y0?1?ah,k?1,h?1

?ab?k?h??ab,k?h?2，这是不可能的。

次证，当N>ab-a-b时，因(a，b)=1，故原方程有整数解（x0，y0），一般解是要求x0-bt?0，y0?at?0???x?x0?bty?y0?at(t?0,?1,)y0x?t?0会证明存在满足这个不等式的整数t?t0可取使abx0?bt0?r(0?r?b)于是对于这个t0有：

15 / 77

《初等数论》习题解答（第三版）

x?bt0?r?b?1?t0?x?b?1b而

a111y0?at0?y0?(x0?b?1)(by0?ax0?ab?a)?(N?ab?a)?(ab?a?b?ab?a)??1bbbby?y0?at0?0?t0??0a这就证明了当N?ab?a?b时，原方程有非负整数解． 1．证明定理2推论。

推论 单位圆周上座标都是有理数的点（称为有理点），可以写成

2aba2?b2a2?b2(?22,?22)或(?22,?22ab2) a?ba?ba?ba?b的形式，其中a与b是不全为零的整数。

证明：设有理数x?ln，y?（m ? 0）满足方程x2 ? y2 = 1，即l2 ? n2 = m2，mm于是得l = ?2abd，n = ?(a2 ? b2)d，m = ?(a2 ? b2)d或l = ?(a2 ? b2)d，m = ?2abd，

2aba2?b2a2?b22ab,?)或(?,?)。反之，m = ?(a ? b)d，由此得(x, y) =(?22222222a?ba?ba?ba?b2

2

代入方程x2 ? y2 = 1即知这样的点在单位圆周上。

2．求出不定方程x2?3y2?z2,(x,y)?1,x?0,y?0,z?0的一切正整数解的公式。 解：设不定方程x2?3y2?z2,(x,y)?1有解则 (1)3/z-x或3/z+x因为3y2?z2?x2?(z?x)(z?x)

?3/(z?x)(z?x)?3/z?x或3/z+x

x2?3y?z?22y22z?xz?x???z?x?或者y??z?x??33

得3/z?x或3/z?x以下不妨设3/z?x

16 / 77

《初等数论》习题解答（第三版）

②?x,z??1， 设 (x,z?)则d,222d/x?,d/zy2d?z/3?x

22,若,3/d,?9/x,9/z?9/3y?3/y ?3/?x,y?与?x,y??1矛盾!

这样?3,d??1?d/y2?d/y?d2/3y而d/x?d/?x,y??d?1

2?③?z?x,z?x??1或2， 设t??z?x,z?x??t/(z?x)?(z?x)?2x，

t/(z?x)?(z?x)?2z?t/?2x.2z??2 即 t?1或t?2

④若

?z?x,z?x??1,则??2z?x?,z?x??1, ?3?从而3y??z?x??z?x??由引理可设

y2?z?x??z?x? 3z?x22?a,z?x?b,y?ab 3从而? ， 为证得x,z为整数， ?x,z??1, 必须有a ， b均为奇数，且3⑤若?z?x,z?x??2??a2?b

2?z?xz?x??z?xz?x?,?1?,????1 2262????2从而3y设

2z?xz?x?y? ??z?x??z?x??????62?2?z?x2z?x2y2222?a,?b,?ab,即x?3a?b,y?2ab,z?3a?b， 622

其中a,b为一奇一偶，且有?a,b??14．解不定方程：x2 ? 3y2 = z2，x > 0，y > 0，z > 0，(x, y ) = 1。

解：设(z ? x, z ? x) = d，易知d = 1或2。由(z ? x)(z ? x) = 3y2得z ? x = 3da2，z ? x = db2，y = dab或z ? x = db2，z ? x = 3da2，y = dab，a > 0，b > 0，(a, b )

|b2?3a2|b2?3a2，y?ab，z?= 1。(ⅰ) 当d = 1：x?，a > 0，b > 0，(a, b ) = 221，3?|b，a, b同为奇数； (ⅱ) 当d = 2：x = |b2 ? 3a2|，y = 2ab，z = b2 ? 3a2，a > 0，b > 0，(a, b ) = 1，3b，a, b一奇一偶。反之，易验证(ⅰ)或(ⅱ)是原

17 / 77

|? 《初等数论》习题解答（第三版）

不定方程的解，且x > 0，y > 0，z > 0，(x, y) = 1。 3．证明不等式方程x?2y?z,?x,y??1,x?0,y?0,z/x的一切正整数解．

42可以写成公式: x?4ab(a2?b),y?∣a?b?6a2442b2∣，z?a2?b

2其中a?0,b?0,?a,b??1,a,b一单一双 证明:由定理1知道原方程的解是x?2cd,y?c2?d,z?c?d,

222c?d?0,?c,d??1， 且c， d为一奇一偶，

其中，c?2ab,d?所以x?4ab(a22?b,a?b?0,?a,b??1， 且a， b为一奇一偶．

4422a2?b),y?∣a?b?6a2b2∣，z?a2?b是原方程的正整数解

2(x?0,y?0,z?0,?x,y??1,2/x,且a?b是奇数，

原方程正整数的解有:

20，0?,?0，4?a,?a?，??a,0,?a???4ab(a?b),?(a?b?6ab),?(a?b)?，?0，??(a?b?6ab),?4ab(a?b),?(a?b)?,

22224422224222222

6．求方程x2 ? y2 = z4的满足(x, y ) = 1，2?x的正整数解。

解：设x，y，z是x2 ? y2 = z4的满足(x, y) = 1，2?x的正整数解，则x = 2ab，y = a2 ? b2，z2 = a2 ? b2，a > b > 0，(a, b) = 1，a, b一奇一偶， 再由z2 = a2 ? b2得a = 2uv，b = u2 ? v2， z = u2 ? v2 或 a = u2 ? v2，b = 2uv， z = u2 ? v2， u > v > 0，(u, v) = 1，u, v一奇一偶，于是得x = 4uv(u2 ? v2)，y = |u4 ? v4 ? 6u2v2|，z = u2 ? v2，u > v > 0，(u, v) = 1，u, v一奇一偶。反之，易验证它是原不定方程的整数解，且x > 0，y > 0，z > 0，(x, y) = 1，2?x。

其中正负号可任意选取． 第三章 同余

?1同余的概念及其基本性质

18 / 77

《初等数论》习题解答（第三版）

1、 证明（i）若??1?k???1?k(modm)

xi?yi(modm)、i=1，2，、、、，k 则

???,,??1k?1?k1x?kx1?????1,,?k1,,?k?1y1?kyk(modm)

特别地，若ai?bi（modm），i=0，1，

,n则

?b0（modm）

anxn?an?1xn?1?a0?bnxn?bn?1xn?1?(ii)若a?b(modm)，k?0,ak?bk(modmk),

（iii）若a?b(modm)，d是a，b及m的任一正公因数，则(iv)若a?b(modm)，dm,d?0. 则a?b(modd)． 证明 ：（i）据性质戊，由xi?yi(modm),i?1,2,得xi?i?yi?i(modm),i?1,2,进一步，则

abm?(mod), bdd,k.

,k,

??1?1x?k1?kxk?B??1?1y?k1?kyk(modm)

最后据性质丁，可得：

???,,??1k?1?k1x?kx1?????1,,?k1,,?k?1y1?kyk（modm）

(ii) 据定理1，a?b(modm)?ma?b,

k?0,?mkk(a?b)?ka?kb

又据定理1，即得ka?kb(modmk).

（iii）据定理1， a?b(modm) ?ma?b,即a-b=ms(s?z)

a?bmabm?s，即???s, dddddabm仍据定理1，立得?(mod),

bddda,b,m,d?0,?(iv) 据定理1， a?b(modm)?a?a?ms,(s?z),

19 / 77

《初等数论》习题解答（第三版）

又

dm,?m?dt,t?z,

故a?b?ms?d(st),st?z,

?a?b(modd).

2、设正整数a?an10n?an?110n?1?a0,0?ai?10

试证11整除的充分且必要条件是11整除

?(?1)a.

ii?1ni证明 ：10??1(mod11),?由上题(i)的特殊情形立得

a?an10n?an?110n?1?a0?an(?1)n?an?1(?1)n?1?a0(mod11)

a??(?1)iai(mod11),

i?0n?11a?11?(?1)a．

ii?0ni3．找出整数能被37，101整除有判別条件来。 解：1000?1(mod37)

故正整数a?ak1000k?ak?11000k?1?立得37a?37a0,0?ai?1000

?a.

ii?0k100??1(mod101).

故设正整数a?bs100s?bs?1100s?1?立得101a?101b0,0?bi?100'，

?(?1)b.

iii?0s4、证明641｜232?1 证明：∵28?256?mod641?

20 / 77

《初等数论》习题解答（第三版）

∴216?2562?65536?154?mod641? ∴232?1542?23716??1?mod641? 即641∣232?1

5、若a是任一单数，则a2?1mod2n?2，?n?1? 证明：（数学归纳法）设a?2m?1

（1）n?1时，a2??2m?1??4m?m?1??1?1?mod8?， 结论成立。

（2）设n?k时，结论成立，即： ?2m?1??1?0mod2而a2k?12kn??2?k?2???2m?1?k2k?1?2k?2t，?t?z?

k?1?a2?1a2?1?a2?1a2?1?2

?k??2k????? ?2k?2t???2?2k?2?t

k?4 ?t2?22?t?2k? 3 ?t?2k?3t?2k?1?1

3 ?0modk? 2????故n?k?1时，结论也成立；∴n?1时，结论也成立。

证明：若2?|a，n是正整数，则a2? 1 (mod 2n + 2)。 (4) 设a = 2k ? 1，当n = 1时，有

a2 = (2k ? 1)2 = 4k(k ? 1) ? 1 ? 1 (mod 23)，

即式(4)成立。

设式(4)对于n = k成立，则有

n

a2? 1 (mod 2k + 2) ?a2= 1 ? q2k + 2，

其中q?Z，所以

kk

a2= (1 ? q2k + 2)2 = 1 ? q ?2k + 3 ? 1 (mod 2k + 3)，

其中q ?是某个整数。这说明式(4)当n = k ? 1也成立。

由归纳法知式(4)对所有正整数n成立。

21 / 77

k?1 《初等数论》习题解答（第三版）

?i?1535625； ?ii?1158066

解：?i?1535625?33?54?7?13；

?ii?1158066?2?3272?13?101

§2 剩余类及完全剩余系 1、 证明x?u?ps?tv，u?0,1,2,,pt?1，t?s是模ps的一个完全剩余类。

证明：显然对u,v的不同取值，x共有ps?t?pt?ps个值，故只需证这样的ps个值，关于模ps的两两互不同余。

若u1?ps?tv1?u2?ps?tv2modps

???u1?u2?ps?t?v1?v2??modps?

?ps?t∣u1?u2，即u1?u2?modps?t??u1?u2

?ps?tv1?ps?tv2?modps??v1?v2?modpt??v1?v2

∴u1?u2或v1?v2时，

s?t u1?pvu?1?2?spt?vmod?p．结论成立。

s22、 若m1,m2,余类，则

,mk是k个两两互质的正整数，x1,x2,,xk分别通过模m1,m2,,mk的完全剩

M1x1?Mx2?2通过模m1m2?Mkxk

,k

mk?m的完全剩余系，其中m?miMi，i?1,2,证明：（数学归纳法）

（1） 根据本节定理3，知k?2时，结论成立。

（2） 设对整数k?1，结论成立，即若m1,m2,,两两互质，令km?,mk?1的完全剩

s'?M1x'1?Mx2'?余系时，s'必过模

2,x?Mk?xk?'，1当x11,x2,k1?分别通过模m1,m2,m'?m1m2...mk?1的完全剩余系，其中miMi'?m'(i?1,2...k?1)。

22 / 77

《初等数论》习题解答（第三版）

现增加mk,使(mi,mk)?1 (i?1,...k?1)，

令Mi?Mkmk(1,...k?1)，m'?Mk?m1m2...mk?1，m?mkMk?m1m2...mk 则易知(m1,m2,...,mk)?(mk,Mk)?1， 再令x?Mkxk?mks'，

当xk过模mk的完全剩余系，s'过模Mk的完全剩余系时，据本节定理3，x必过模

m?mkMk?m1m2...mk的完全剩余系，即对k结论成立。

3n?1?1)中每一个整数有而且只有一种方法表示成 3、（i）证明整数?H,...?1,?0,1,...,H(H?3?13nxn?3n?1xn?1?...3x?x0.............?

的形状，其中xi??1,0,1(i?0,1,...n)；反之，?中每一数都??H且?H,。

（ii）说明应用n?1个特别的砝码，在天平上可以量出1到H中的任意一个斤数。 证明：（i）当xi??1,0,1(i?0,1,...n)时，?过模2H?1?3n?1的绝对最小完全剩余系，也就是?表示??H,H?中的2H?1个整数，事实上，当xi??1,0,1时，共有3n?1个值，且两两互不相等，否则

3nxn'?3n?1xn?1'?...3x1'?x0'?3nxn?3n?1xn?1?...3x1?x0

'?3n(xn'?xn)?3n?1(xn?1'?xn?1)?...3(x1'?x1)?x0?x0?3|x0?x?x0?x.此即

'0'0

3n?1(xn'?xn)?3n?2(xn?1'?xn?1)?...(x'?x)?0?3|x?x1?x?x1?...?x?xn又?的最大值是3?3nn?1'1'1'n

3n?1?1?...3?1??H

3?1最小值是?3n?3n?1?...?3?1??H 所以，结论成立。

23 / 77

《初等数论》习题解答（第三版）

（ii）特制n?1个砝码分别重1,3,3,...,3斤，把要称的物体

2n???di?????i?1i?1rr?a?di??及取-1?的砝码放在天平的右盘，xi取1的砝码放在左盘，则从（i）的结论知，当xi取适当的值时，可使T?3nxn?3n?1xn?1?...3x?x0.之值等于你所要称的物体的斤数??H?。

4、若m1,m2,...,mk是K个两两互质的正整数，x1,x2,...xk分别过模m1,m2,...,mk的完全剩余系，则

x1?m1x2?m1,m2x3?...?m1,m2,...,mkxk.................?

通过模m1,m2,...,mk的完全剩余系。 证明：（数学归纳法）

（1）K?2时，x1,x2分别过模m1,m2的完全剩余系时，

x1?m1x2共有m1m2个值，且若

??m1x2?(modm1m2)?m1(x2?x2?)?x1??x1(modm1m2) x1?m1x2?x1????x1，且x2?x2?m1x1??x1x1(modm2) m1?，x2?x2?，即k?2时结论成立； ?x1?x1（2）设当x2,,xk分别过模m2,?m2m3,mk的完全剩余系时，

mk的完全剩余系。

x2?m2x3?因为(m1,m2mk?1xk过模m2mk)?1，由本节定理2得， ?m2mk?1xk)亦过模m2mk的完全剩余系。

m1(x2?m2x3?当x1,x2,2有m1m2,xk?1,xk分别过模m1,m2,,mk?1,mk的完全剩余系时，

mk个值，且据归纳假设，

?m1?m1mk?2xk?1?m1??1?m1mk?2xkmk?1xk ?(modm1mk?1xk 24 / 77

若x1?m1x2???m1x2???x1mk)

《初等数论》习题解答（第三版）

?(modm1)； x2?m2x3??x1?x1??m2x?3? ?x2?m2?m2mk?1xk

k??modmm1k(x2km )?(modm1)，x2?x2?(modm2)，…，xk?xk?(modmk) ?x1?x1?，x2?x2?，…，xk?xk?。 ?x1?x1所以x1?m1x2??m1m2mk?1xk过模m1m2mk的完全剩余系。

3．简化剩余系与欧拉函数 1．证明定理2：若a1,a2,,a?(m)是?(m)与m互质的整数，

,a?(m)是模m的一个简化剩余系。

并且两?对模m不同余，则a1,a2,证明：

a1,a2,又

,a?(m) 两?对模m不同余，所以它们分别取自模m的不同剩余类，

,a?(m)恰是?(m)个与m互质的整数，即它们恰取自与模m互质的全部剩余类。

a1,a2,2．若m是大于1的正整数，a是整数，(a,m)?1，?通过m的简化剩余系，

?a??1则?????(m)，其中?表示展布在?所通过的一切值上的和式。

2??m??证明：由定理3知，?通过m的简化剩余系：

a1,a2,而?,a?(m)，其中0＜ai＜m且(ai,m)?1，

。 ?(m)）

?ai?ai??（i?1,2,?m?m若m＞2，则?(m)必是偶数，又由(ai,m)?1， 得(m?ai,m)?1，且易见m?ai?ai， 故??ai??m?ai?ai?m?ai?1 ?????m?m??m? 25 / 77

《初等数论》习题解答（第三版）

243x??30?112?mod551? 2?5??同?i?的方法的得其解是x?200?mod551?

?原同余式的解是x?200,751,1302,1853,2404?mod2755?

?iii?(1296，1935)=9，故原同余式有9个解。

由144x??30?125?mod215?得x?80?mod215? 2?5???原同余式的解是x?80?215t?mod1935?,t?0,18.

2．求联立同余式??x?4y?29?0(mod143)的解。

2x?9y?84?0(mod143)?解：据同余式的有关性质，

?x?4y?29?0(mod143)?x?4y?29(mod143) ????2x?9y?84?0(mod143)?17y??1(mod143)?x?4y?29(mod143)?x?4(mod143)为所求的解。 ????y?42(mod143)y?42(mod143)??3．(i)设m是正整数，(a,m)?1．证明

?(m?)1(modm ) x?ba是同余式 ax?b(modm)的解 (ii)设p是质数，0?a?p，证明

x?b(?1)a?1(p?1)(p?a?1)(modp)

a!是同余式ax?b(modp)的解． 证明: (i)

(a,m)?1 ， ?ax?b(modm) 有唯一解．

而据欧拉定理，得 a?(m)?1(modm)，

31 / 77

《初等数论》习题解答（第三版）

ax?b(momd)?a?(m?)1?ax?ba?m(?)1(momd)

即 x?ba?(m)?1(modm)是ax?b(modm)的解． (ii) 又

0?a?p?(a,p)?1 即ax?b(modp)有唯一解

a个连续整数之积必被a!所整除，

(p?1)(p?a?1)故可令 ab(?1)a?1?k

a!则b(?1)a?1(p?1)(p?a?1)?k(a?1)!

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

b(?1)a?1(p?1)即b(?1)2(a?1)(a?1)!?k(a?1)!(modp)

?k?b(modp)

即 x?b(?1)a?1(p?1)(p?a?1)(modp)

a!是ax?b(modp)的解．

设p是素数，0 < a < p，证明：

x?b(?1)a?1(p?1)(p?2)???(p?a?1)(mod p)。

a!是同余方程ax ? b (mod p)的解。

(p?1)(p?2)???(p?a?1)是整数，又由(a, p) = 1知方程ax ?

a!(p?1)(p?2)???(p?a?1)b (mod p)解唯一，故只须将x?b(?1)a?1(mod p)代入ax ? b

a!解：首先易知b(?1)a?1(mod p)验证它是同余方程的解即可。

4．设m是正整数，?是实数，1???m,(a,m)?1，证明同余式

ax?y(modm),0?x??,0?y?有解．

m?

32 / 77

《初等数论》习题解答（第三版）

证明: 因(a,m)?1. 故同余式 ax?1(modm) 必有解x0， (i) (ii)

若 0?x0??，则结论成立;

若??x0，令m?q1x0?x1，0?x1?x0， 则ax1??(ax0)q1??q1(modm)

又若 x1??,则由 q1?m?x1m?，结论成立． x0?若 ??x1 令 x0?q2x1?x2 则 ax2?1?q1q2(modm).

0?x2?x1

又若 x2??,则由m?q1x0?x1?q1(q2x1?x2)?x1 即m?(1?q1q2)x1?q1x2, 故 1?q1q2?结论成立。

若??x2,又令x1?q3x2?x3, 0?x3?x2. 则 ax3??(q1?q2?q1q2q3)(modm) 重复上述讨论：即若

m?q1x2m? x1?x3??,则结论成立，

若??x3.又令 x2?q4x3?x4,0?x4?x3 ``````

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

?x?2(mod7)?解：

模3,5,7两两互质，故原方程组对模m?3?5?7有唯一解

33 / 77

《初等数论》习题解答（第三版）

35M1??1(mod3)得M1??2(mod3)??1(mod5)21M2??1(mod5)M1M1??1(mod3)即M2??1(mod7)15M3??1(mod7)M3根据孙子定理方程组的解是

x?2?35?2?1?21?3?1?115?2?233?23(mod105)

注意到 x0?x1?x2?,

故有限步后，必有 axn?y(modm) 其中0?xn??,y?m?,即结论成立。

?2.孙子定理

试解下列各题：

（i） 十一数余三，七二数余二，十三数余一，问本数。 （ii） 二数余一，五数余二，七数余三，九数余四，问本数。 （杨辉：续古摘奇算法（1275））。

?x?3(mod11)?解：（i）依题意得?x?2(mod72)

?x?1(mod13)?则据孙子定理，上述方程组有唯一解(mod11?72?13)

72?73M1??1(mod11)得M1??1;??1(mod72)得M2???1; 由11?13M2??1(mod13)得M3???1;11?72M3故原方程组的解是x?3?936?2?(?1)?143?1?(?1)?792?1730(mod10296).

?x?1(mod2)?x?2(mod5)?(ii)依题意得?

x?3(mod7)???x?4(mod9)?x?1?315?2?126?3?6?90?4?4?70?3307?157(mod630).

2、（i）设 m1,m2,m3是三个正整数，证明：

34 / 77

《初等数论》习题解答（第三版）

???(m1,m3),(m2,m3)?????m1,m2?,m3?．

（ii）设 d?(m1,m2).证明：同余式组

?, x?b1(modm1)x2b(momd)1） （2有解的充分与必要条件是db1?b2.

在有解的情况下，适合（1）的一切整数可由下式求出：

x?x1,2?mod?m1,m2??

其中x1,2是适合?1?的一个整数。

?iii?应用?i?,?ii?证明同余式组x?bi?modmi?,i?1,2,有解的充分与必要条件是(mi,mj)|(bi,bj),i,j?1,2,整数可由下式求出：

,k ?2?

,k，并且有解的情况下，适合(2)的一切

x?x1,2,其中x1,2,,k(mod?m1,m2,mk?)

,k是适合(2)的一个整数。

证明：?i??(m1,m3),(m2,m3)??(m1,m3)(m2,m3)(m,m)(m2,m3)?13

((m1,m3),(m2,m3))(m1,m2,m3)3 (?m1,m2?,m3)?((mm,(m,1m)2m)3(mm1,m2m,1mmm1m23)2,m3)?12?

(m1,m2)(m1,m2)(m1,m2)(m1,m2,m3)(m1m2,m1m3,m2m3)?((m1,m2,m3)m1m2,(m1,m2,m3)m1m3,(m1,m2,m3)m2m3)

22222?(m12m2,m1m,mm,mm,mm,mm3m1m2)m(3,m1)m(221313232,m1)m( 3m2)m3?(m12,m1m3,m1m2,m2m),m3)3(m2222?(m12m2,m1m,3m22m,32m1m,33,mmmm2,m2m112)3m1m2,m1m3,m2?m3) ?(m1,m2,m3)(即

(m1,m2)(m1,m3)(m ,m)(m1,m3)(m2,m3)(m1m2,m1m3,m2m3)?

(m1,m2,m3)(m1,m2) ??(m1,m3),m(2m,3??)?m(1?m,2m, 3). 35 / 77

《初等数论》习题解答（第三版）

?ii?设(1)有解c，即c?b1(modm1),c?b2(modm2)

故此得b1?b2(mod(m1,m2))，必要性成立； 反之，设d|b1?b2即b1?b2(modd)

则由§1定理，知方程m1y?b2?b1(modm2)必有解， 设其解为y?y0(modm2)，即m1y0?b2?b1(modm2) 令x1,2?b1?m1y0则易见：

x1,2?b1(modm1)且x1,2?b2(modm2)

即(1)有解x1,2，充分性得证。 进一步，若(1)有解x,y，则

x?y(modm1),x?y(modm2)

即x?y是m1,m2的公倍数，当然也是?m1,m2?的倍数，

?x?y(mod?m1,m2?)

故若x1,2是(1)的一个解，则(1)的任一解x必满足

x?x1,2(mod?m1,m2?)。

(iii)若同余式组x?bi(modmi),i?1,2,则?,k有解，

??x?bi(modmi) 也有解。从而由(ii)知必有

??x?bj(modmj),k，必要性成立。

(mi,mj)|(bi,bj),i?1,2,下证充分性。首先，推(i)，用归纳法易证：

?(m1,mk),(m2,mk),,(mk?1,mk)??(?m1,m2,,mk?1?,mk)

又由(ii)知k?2时，充分性也成立；

36 / 77

《初等数论》习题解答（第三版）

?x?b1(modm1)?现设同余式组? 有解x?b(mod?m1,?x?b(modm)k?1k?1?即b?bi(modmi),1?i?k?1。

设bi?b?limi,1?i?k?1；又由条件知(mi,mk)|(bi?bk)，

,mk?1?)，

而bi?bk?(b?bk)?limi，从而(mi,mk)|bi?bk,1?i?k?1， 所以x2?41(mod16)， 即(?m1,m2,,mk?1?,mk)?b?bk，

??x?b(mod?m1,,mk?1?)又由(ii)，则同余式组?，

??x?bk(modmk)必有解x?c(mod?m1,,mk?1,mk?) （※）

显然c?bi(modmi),1?i?k，即（※）就是同余式组(2)的解，据归纳性原理，结论成立。后一结论由上述过程亦成立。

§3 高次同余式的解数及解法

1、 解同余式6x3?27x2?17x?20?0(mod30)。

?x2?x?0(mod2)??????????(1)?解：原同余式等价于?2x?2?0(mod3)??????????(2)

?x3?2x2?2x?0(mod5)??????(3)?(1)有解x?0,1(mod2) (2)有解x?2(mod3) (3)有解x?0,1,2(mod5)

?x?b1(mod2)? 联立?x?b2(mod3)?x?b3(mod5)?b1?0,1b2?2b3?0,1,2

据孙子定理，可得x?15b1?10b2?6b3(mod30)

37 / 77

《初等数论》习题解答（第三版）

故原同余式共有6个解是：

x1?20,x2?5,x3?26,x4?11,x5?2,x6?17,(mod30)

2、 解同余式31x4?57x3?96x?191?0(mod225)

解：

225?32?52

?4x4?3x3?6x?2?0(mod32)? 故原同余式等价于?4 32??6x?7x?4x?9?0(mod5)1） 先解4x4?3x3?6x?2?0(mod3)

即x4?1?0(mod3) 得x??1(mod3)

f?(x)?16x3?9x2?6?f?(1)?31,3?31

f?(?1)??1,3?(?1)f(1)??5(mod3)?t1?1(mod3).3?x1?1?3t1?4(mod32);由f?(1)t1??又由f?(?1)t2??5(mod3)?t2?2(mod3)?x2??1?3t2?5(mod32);即第一式有两个解x1?4,x2?5②再解g(x)?6x4?7x3?4x?9?0即 x4?2x3?x?1?0设 x?1,

(mod32).(mod5)

(mod5)

2(mod 5g?(1)?41.g?(2)?272,

g?(x)?24x3?21x2?4.而5?415?272

(mod5)(mod5)(mod52).

由41t1?0(mod5)?t1?0272t2??27(mod5)?t2?4?3?第二式有两个解x3?1,?x?b1联立??x?b2(mod9)(mod25)b1?4,5b2?1,?3 38 / 77

《初等数论》习题解答（第三版）

由孙子定理设x?100b1?126b2即原四条式有4个解是x?76, §4．质数模的同余式

补充例子： 1．解同余方程：

(mod225)

22,176,122(mod225).

(ⅰ) 3x11 ? 2x8 ? 5x4 ? 1 ? 0 (mod 7)； (ⅱ) 4x20 ? 3x12 ? 2x7 ? 3x ? 2 ? 0 (mod 5)。

解：(ⅰ) 原同余方程等价于3x5 ? 5x4 ? 2x2 ? 1 ? 0 (mod 7)，用x = 0，?1，?2，?3代入知后者无解； (ⅱ) 原同余方程等价于2x4 ? 2x3 ? 3x ? 2 ? 0 (mod 5)，将x = 0，?1，?2 代入，知后者有解x ? ?1 (mod 5)。 2．判定

(ⅰ) 2x3 ? x2 ? 3x ? 1 ? 0 (mod 5)是否有三个解； (ⅱ) x6 ? 2x5 ? 4x2 ? 3 ? 0 (mod 5)是否有六个解？

解：(ⅰ) 2x3 ? x2 ? 3x ? 1 ? 0 (mod 5)等价于x3 ? 3x2 ? 4x ? 3 ? 0 (mod 5)，又x5 ? x = (x3 ? 3x2 ? 4x ? 3)(x2 ? 3x ? 5) + (6x2 ? 12x ? 15)，其中r(x) = 6x2 ? 12x ? 15的系数不都是5的倍数，故原方程没有三个解； (ⅱ) 因为这是对模5的同余方程，故原方程不可能有六个解。

定理5 若p是素数，n?p ? 1，p?|a则

x n ? a (mod p) (14)

有解的充要条件是

p?1na若有解，则解数为n。

?1 (mod p)。 (15)

证明 必要性 若方程(14)有解x0，则p?|x0，由Fermat定理，得到

39 / 77

《初等数论》习题解答（第三版）

a充分性 若式(15)成立，则

p?1n?(x)n0p?1n= x0p ? 1 ?1 (mod p)。

p?1np?1np?1nxp?1?x?x((x)n?a?a?1)?(xn?a)P(x)?x(ap?1n

?1)，其中P(x)是关于x的整系数多项式。由定理4可知同余方程(14)有n个解。证毕。

1、 设n︱p?1， n?1， (a,p)?1．证明同余式 xn?a有解的充分必要条件是a(modp )p?1n?1(modp)，并且在有解的情况下就有n个解。

证明：?)若同余式有解，令其解为x?x0(modp), 设p?1?kn.则x0p?1?x0kn?1但x0p?1?a(a,p)?1,?(x0,p)?1 (modp)

(modp)

?ap?1n?x0p?1?1(modp);

?)ap?1n?1(modp)

(modp) 可得xp?1则由x?an?ap?1n?1(modp)。

它有p?1个解。

又n︱p?1

p?1p?1?2?1??(p?1)?n(p?1)?2nnnn?ax?ax?a 令g(x)??x?

??则xp?1?(xn?a)g(x)?0(modp)

g(x)?0(modp)

40 / 77

《初等数论》习题解答（第三版）

无多于(p?1?)n个解，而xp?1?1?0(mpo d恰)有p?1个解，

xp?1?a?0(mo必有pdn)个解。

2．设n是整数，（a，m）=1，且已知同余式xn?a(modm)

有一解x?x0(modm)，证明这个同余式的一切解可以 表成x?yx0(modm)

其中y是同余式yn?1(modm)的解。

证明：设x?x0,x?x1(modm)均是xn?a(modm)的解， 则x1n?x0n?a(modm)，

（a，m）=1 ， ? （x0，m）= (x1，m) = 1

则由第三章定理3．3知，必存在y，使 yx0?x1(modm)，

? ynx0n?x1n?x0n(modm) ．

故原同余式的任一解可表示为x?yx0(modm) 而y满足yn?1(modm)

3．设(a, m) = 1，k与m是正整数，又设x0k ? a (mod m)，证明同余方程

xk ? a(mod m)

的一切解x都可以表示成x ? yx0 (mod m)，其中y满足同余方程yk ? 1 (mod m)。 解：设x1是xk ? a(mod m)的任意一个解，则一次同余方程yx0 ? x1 (mod m)有解y，再由yka ? ykx0k ? (yx0)k ? x1k ? a (mod m)得yk ? 1 (mod m)，即x1可以表示成x ? yx0 (mod m)，其中y满足同余方程yk ? 1 (mod m)；反之，易知如此形式的x是xk ? a(mod m)的解。

41 / 77

《初等数论》习题解答（第三版）

第五章 二次同余式与平方剩余 §1 一般二次同余式

1、 在同余式y2?A?0(modp?)中，若p?|A，试求出它的一切解来。 解：若p?|A，则A?0(modp?)，上同余式即为

y2?0(modp?)

从而p?|y2，即有p????2???|y。

????????易见，当??2?为偶数时，????，则p?2??p?，上同余式有解：

?2?x?0,p?,2p?,,(p??1)p?(modp?)，共有n?2m?1?p个解

????2???当??2??1为奇数时，p?p?，上同余式有解：

x?0,p??1,2p??1,,(p??1)p??1(modp?)，共有n?2m?1?p个解。

2、证明：同余式abax2?bx?c?0(modm),(2a,m)?1 (1)有解的充分必要条件是

x2?q(modm),q?b2?4ac (2)有解，并且前一同余式的一切解可由后一同余式的解导出。

证明：因(2a,m)?1，故a 用4a乘(1)后再配方，即得

(2ax?b)2?q?0(modm),q?b2?4ac

仍记2ax?b为x，即有

x2?q(modm)

由以上讨论即知若x?x0(modm)为(1)的解， 则x?2ax0?b(modm)为(2)的解，必要性得证。 反之，若(2)有一解x?x0(modm)，即有：

2x0?8?0(modm),q?b2?4ac

42 / 77

《初等数论》习题解答（第三版）

由于(2a,m)?1，故2ax?b?x0(modm)有解x?x1(modm) 即有：(2ax1?b)2?(b2?4ac)?0(modm) 即有：4a(ax12?bx1?c)?0(modm) 由a，即有：ax12?bx1?c?0(modm) 即x?x1(modm)为(1)的解，充分性得证。 由充分性的讨论即知(1)的解可由(2)的解导出。 §2 单质数的平方剩余与平方非剩余

1、 求出模

??()的平方剩余与平方非剩余。

damd解：p?37,序列12,22,p?1?18，由书中定理2知，模p?37的简化剩余系中18个平方剩余分别与2,182

例2．试判断下述同余方程是否是有解。 （1）?2?27(mod37) （2）?2?2(mod37) （3）?2?3(mod17) 中之一数同余，而

12?1 ,22?4, 32?9, 42?16, 52?25, 62?36, 72?12, 82?27, 92?7,

2?26,2?10, 122?33, 132?21, 142?11, 152?3, 162?34, 172?30, 10 112?28. 18

故模37的平方剩余为：

1，3，4，7，9，10，11，12，16，21，25，26，27，30，33，34，36 而其它的18个数为模37的平方非剩余：

2，5，6，8，13，14，15，17，18，19，20，22，23，24，29，31，32，35

2． (i)应用前几章的结果证明:模p的简化剩余系中一定有平方剩余及平方非剩余存在，

43 / 77

《初等数论》习题解答（第三版）

(ii)证明两个平方剩余的乘积是平方剩余;平方剩余与平方非剩余的乘积是平方非剩余。 (iii)应用(i)、(ii)证明：模p的简化剩余系中平方剩余与平方非剩余的个数各为

p?1。 2证明：(i)因为12?1(modp),1为模p的简化剩余系中的平方剩余。若模p的简化剩余系中均为平方剩余，考虑模p的绝对最小简化剩余系：?p?1p?1 ,...,?1,1,...,22p?1个数： 2p (?12 ),?(22),?...(2)2它们的平方为模p下的

由假设模p的简化剩余系中任一个数与上

p?1个数同余，而模p的简化剩余系中有p个数，2故必有两个互相同余，矛盾。从而必有平方非剩余存在。

(ii)若

p?12a,b为平方剩余，则

ap?12?1(modp),bp?12?1(modp)故

(ab)??1(modp),(p?1)?r?r?p?12p?1,从而ab也为平方剩余。若a为平方剩余，b为平方2非剩余，则a故(ab)p?12?1(modp),bp?12??1(modp)

??1(modp),从而ab为平方非剩余。

(iii)设a1,...,ar为模p的简化剩余系中的平方剩余；ar?1,...,ap?1为模p的简化剩余系中的平方

非剩余。由(ii)知，ar?1a1,...,ar?1ar为平方非剩余，显然互不同余。故r?(p?1)?r,反之，由

ar?12,ar?1ar?2,...,ar?1ap?1为平方剩余知(p?1)?r?r,故r?3．证明：同余式x2?amodp?，?a,p??1的解是

p?1，得证。 2???mod? x??pQp，其中

??? p?2?a????2?2a???,Q??12?a?????2?a?2a?mopd?

?? 22?a?modp?Q,Q证明：若x2?amodp?有解，则x2?a?modp?有解，

44 / 77

?? 《初等数论》习题解答（第三版）

设其解是：x?2?modp?，即有： 22?a?modp?， 令22?a?kp?22?a而2?a????k?p??0?modp?? a?C?22????2?C?2?1??1??2?a?2???a??

?p?Qa ，p,Q 为整数

?2?a???p?Qa 由此两式即得：

?p?

2?a????2?a2??2?a???2?a??Q???

2a两式相乘得： 2?a?2???p2?aQ2?p2?aQ2?0?modp??

?p2?aQ2modp? 取Q?使得： QQ??1modp?

则 p2?Q???amodp? 故其解为 x??pQ?modp? 4．证明同余式x2?1?0?modp?,p?4m?1 的解是 x??1?22?????????2mp??mod?

证明：首先我们证明对任意n：p?n 有下式： ?n?1?!?p?n?!????1?因为??1?k?p?k?modp? ，于是 ?n?1?!???1?因此由威尔生定理得：

45 / 77

n?1nmo?dp

?p??1?p?n???1 mo?dp

《初等数论》习题解答（第三版）

?n?1?!?p?n?!???1?

n?1?p?1?!???1???1?

n?1???1n??modp?

其次由p?4m?1，可令n?2m?1?p ，代入上式

即有 ?2m!???1?mopd?

故原同余式的解为 x???2m?!?modp? §3 勒让得符号

1．用本节方法判断下列同余式是否有解

2?i?x2?429?mod5?63 ?ii?x2?680?mod7?6 9 其中503，563，769，1013都是质数

013?iii?x2?503?mod1? 解：?i???429???1，有解。 ?563?680??ii?????1，有解。

769???iii???503???1，有解。 ?1013?2、求出以?2为平方剩余的质数的一般表达式；以?2为平方非剩余的质数的一般表达式。

p?1p?1??2???1??2??28 解：????1????????p??p??p?2p?1p2?1??2n ?2为模p平方剩余时，必有28?i?p?4k?1，必有p?8k??1，故p?8m?1 ?ii?p?4k?3，必有p?8k??3，故p?8m?3

p?1p2?1??2n?1 ?2为模p平方非剩余时，必有28?i?p?4k?1，必有p?8k??3，故p?8m?5

46 / 77

《初等数论》习题解答（第三版）

?ii?p?4k?3，必有p?8k??1，故p?8m?7

3、设n是正整数，4n?3及8n?7都是质数，说明

24n?3?1(mod8n?7)

由此证明：23|211?1,47|223?1,503|2251?1。

证明：当p?8n?7时，由本节定理1的推论知2为平方剩余，应用欧拉判别条件即有

2p?12?1(modp)

由p?8n?7，即得出24n?3?1(mod8n?7)

而23?8?2?7,47?8?5?7,503?8?62?7都是形如8n?7的素数，并且

11?23?147?1503?1，所以 ,23?,251?22223|211?1,47|223?1,503|2251?1。

§4 前节定理的证明

1、 求以?3为平方剩余的质数的一般表达式，什么质数以?3为平方非剩余？

p?1?3??p?解：由互反律 ?????1?2??

?3??p?p?12因此??1??3??p?,??当它们同为1或同时为?1时，???1， ?3??p??3????1 p??p?12一为1，一为?1时，?p?1显然，当为偶数，而p?1(mod4)时，(?1)2p?1当是奇数，即p??1(mod4)时，(?1)2p?12?1，

??1。

再因为p是奇质数，关于模3我们有p?1或p??1， 当p?1(mod3)时，??p??1??????1 ?3??3? 47 / 77

《初等数论》习题解答（第三版）

当p??1(mod3)时，?

?p???1???????1 3???3?这样3为平方剩余时，p为下方程组的解

?p?1(mod3)?p??1(mod3)或? ??p?1(mod4)?p??1(mod4)由孙子定理，即可知p?1或?1(mod12)，立即 当p?12n?1时，3为平方剩余。

3为平方非剩余时，p为下方程组的解 ?p?1(mod3)?p??1(mod3)或 ??p??1(mod4)p?1(mod4)??由孙子定理，即可知p?5或?5(mod12)，立即 当p?12n?5时，3为平方非剩余。

p?1?3?133因为()?()()?(?1)2()

pppp当

33p?1p?1为偶数，()?1，或为奇数，()??1时，即

pp22p?12n?1或12n?5时，?3为平方剩余，

类似p?12n?1或12n?5，?3为平方非剩余。 2、求以3为最小平方非剩余的质数的一般表达式。 解：由上题知以3为平方非剩余的质数p满足：

p??5(mod12)

又由3为模p的最小平方非剩余，故()＝1 从而p??1(mod8)（§3Th1推证）

48 / 77

2p 《初等数论》习题解答（第三版）

满足p??5(mod12)的素数p形如24m?5,24m?7,24m?17,24m?19， 其中只有24m?7,24m?17满足p??1(mod8)

故p?24m?7或24m?17时，3为它的最小平方非剩余。 §5 雅可比符号 1、 判断§3习题1所列各同余式是否有解。 略

2、 求出下列同余式的解数：

(i)x2?3766(mod5987)，(ii)x2?3149(mod5987)其中5987是一个质数。

解：(i)(37662?188321883)?()?()() 598759875987598725987?748?8?3，故()??1

59871883?15987?1?1883598759873382()(?1)2()??()??() 598718831883188321691691883246??()()?()?()?()?()

1883188318831691691692331694?()()?()?()?()?1 16916916933故??3766????1，即?i?的解数为0． ?5987??3149???1，故解数为2． ?5987? ?ii? ?3． ?i?在有解的情况下，应用定理1，求同余式

x2?a(modp)，p?4m?3的解。

?ii?在有解的情况下，应用 §2 定理1及§3定理1的推论，求同余式

x2?a(modp)，p?8m?5的解。

解：同余式x2?a(modp)有解，故

a1(p?1)2?1(modp)

49 / 77

《初等数论》习题解答（第三版）

?i? a1(p?1)2?a?a1(p?1)2?a(modp)

由p?4m?3知(am?1)2?a(modp) 故x??a(modp)即为原同余式的解。

?ii? 由p?8m?5知

1(p?1)?4m?2，故 2a4m?2?1?0(modp)

故(a2m?1?1)(a2m?1?1)?0(modp)

因此(a2m?1?1)?0(modp)或(a2m?1?1)?0(modp) 若前式成立，那末a2m?1?a?a(modp) 即 (am?1)2?a(modp)

若a2m?1?1(modp)则原同余式的解是x??am?1(modp) 即 x??am?1(modp)为原同余式的解。

1 若后式成立，那末 a2m?1?a??a(modp)

由§3定理1的推论知，2是模p的平方剩余，即

1(p?1)22?24m?2??1(modp)

于是： 24m?2?a2m?2?a(modp)

2 若a2m?1??1(modp)则原同余式的解是

x??22m?1am?1(modp)

故x??22m?1am?1(modp)为原同余式的解． §6 合数模的情形

25)?x?41(mod64) 1. 解同余式 ?i?x2?59(mod1，?ii

解：从同余式x2?59(mod125) 得x?2(mod5)

50 / 77

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