第一讲--整数与同余理论

第一讲 整数与同余理论

本讲介绍有关整数的一些基本概念、性质与定理.主要包括整数的整除性、奇偶性，以及依据整除性而产生的质数与合数、带余除法、最大公约数与最小公倍数. 同时简单介绍同余式的一些最基本的知识及有关重要定理，如欧拉定理、中国剩余定理(CTR).

______________________________________________________________________________

§1. 1 整数的基本概念、性质与定理

自然数和它的相反数，以及零均称为整数. 定义1. 1 设a与b是任意两整数且b?0，若存在整数q使得a?bq，则称b整除a或a能被b整除.记作b|a；否则，称b不能整除a或a不能被b整除，此时记作b?a.

?1,?a，则称b是a如果b|a，则称b是a的约数或因数，a是b的倍数；若b是a的约数但b?的真约数或真因数.

定理1. 1 设a,b,c,m,n是整数, 则有 i)

a|a；

??b；

ii) 如果a|b且b|a，则aiii) 如果a|b且b|c，则a|c； iv) 如果a|b且a|c，则a|(mb?nc).

定理1. 2（带余除法定理） 对任意两整数a与b且b?0，则存在唯一的一对整数q与r，使得

a?qb?r，其中0?r?|b|.

q称为a被b除得到的商，r称为a被b除得到的余数.

我们借助自然数集的最小数原理来证明该定理:

自然数集的最小数原理 若S是广义的自然数集的任一非空子集，则存在a?S使得?x?S，有

a?x成立，此a称为S的最小数.

定理1.2的证明 设S=?a?kb|k??, a?kb?0?，则S是广义自然数集的非空子集，于是存

?a?qb，亦即a?qb?r.下面证明0?r?|b|且q与r是

在S的最小数r，即存在q??，使r 1

唯一的.（注：广义自然数集可包含零及正无穷大这两个元素.）

若r?|b|，则0?r?|b|?a?(q?1)b?S且r?r?|b|，这与r是S的最小数矛盾.

若存在两整数q1与r1，使得

a?q1b?r1，0?r1?|b|,

则

q1b?r1?qb?r,

即

(q1?q)b?r?r1.

若q1?q，则r?r1?|b|，这与0?r,r1?|b|?1矛盾，故q1?q，于是r?r1. ▋

显然，a被b整除的充分且必要条件是其余数为0. 例1. 1 设a??89,b?13, 则q??7, r?2.

练习1. 1

1. 证明对任意整数n有6n(n?1)(2n?1).

2. 如果2a?3b与9a?5b中有一能被17整除，那末另一数一定也能被17整除. 3. 证明：7a00a，其中a00a表示一个四位数a?{1,2,?,9}.

§1. 2 整数的奇偶性

奇偶数的定义：能被2整除的整数称为偶数；不能被2整除的整数称为奇数. 基本性质：

1）两个整数的和与差具有相同的奇偶性.

2）奇数的平方被4除余1，被8除也余1，而偶数的平方能被4整除.

3）如果若干个整数的乘积是奇数，则每个因数都是奇数；如果若干个整数之积是 偶数，则至少有一个因数是偶数.

例1. 2 在广场上有m（奇数）个学生面向南方排成一行，命令其中n（偶数）个学生向后转，称作一次“反向运动”，证明：无论作多少次“反向运动”（转向后的学生允许再转动），都不可能使所有的学生全部面向北方.

证 假设做k次“反向运动”后，可使全体学生面向北方，又设各学生“向后转”的次数分别为x1,?,xm,

2

而对每个学生来说，从面向南方变为面向北方，必须经过奇数次“向后转”，即x1,?,xm均为奇数，又m为奇数，所以x1???xm是奇数.另一方面，每次“反向运动”均是n个学生的“向后转”，所以k次“反向运动”所作的“向后转”总次数应为kn，故有x1?x2边是偶数，矛盾. ▋

???xm?kn，但该等式左边是奇数，而右

练习1. 2

1.

4?4的方格纸上填着1,9,9,8这四个数字，如图所示，问是否可能在余下的方格

内各填入一整数，使得方格纸上的每一行和每一列都构成等差数列

9 1 9 8 表1. 1

2. 已知多项式x3?bx2?cx?d的系数均为整数，且bd?cd是奇数，证明：此多项

式不可能分解成两个整系数多项式之积.

3. 将下图表1.2中任何一行或一列作全部变号操作，问可否经过若干次这样的操作使表1.2变为表1.3？

?

???????????

??? ???表1.2 表1.3

a,求证：24|(a4. 若a是奇数，且3?2?1).

§1. 3 最大公约数与最小公倍数

本节利用带余除法，引入辗转相除法，并由此介绍最大公约数与最小公倍数.

定义1. 2 设a1,a2,?,an是n(n?2)个整数.若整数d是每个ai的因数，则称d是

a1,a2,...,an的一个公因数.

定义1.3 整数a1,a2,?,an的公因数中的最大者称为它们的最大公因数，记作(a1,a2,?,an)或

3

gcd(a1,a2,?,an).

显然，若a1,a2,?,an中至少有一个非零.比如说ai??0，则(a1,a2,?,an)?ai，因而此时

a1,a2,?,an的最大公因数存在.

定义1. 4 如果

；如果i?(a1,a2,?,an)?1，则称a1,a2,?,an互素（或互质）?j时有

(ai,aj)?1，则称a1,a2,?,an两两互素（或互质）.显然，若后者成立，则前者也成立，反之则不然.

如(3,5,10)?1，但(5,10)??1.

性质定理1.1 设a1,a2,?,an是n个不全为零的整数，则有 i) ii)

(a1,a2,?,an)?(ai1,ai2,ai2,?,ain)，其中i1,i2,?,in是1,2,3,?,n的一个排列； (a1,a2,?,an)?(|a1|,|a2|,?,|an|)；

iii) 若a1,a2,?,an中有一个为1, 则它们互素； iv) 若aj1,aj2,?,ajs是a1,a2,?,an中全不为零的整数，则

(a1,a2,?,an)?(|aj1|,|aj2|,?,|ajs|).

以上性质的证明均显而易见. 定理1. 3 如果a证 设(a,b)从而

另一方面，d1从而

综合(1.3.1)与(1.3.2)即得

?bq?r,则有(a,b)?(b,r).

及(b,r)?d?d1，则一方面，da且db，于是由a?bq?r得d|r，

d?d1. (1.3.1)

|b且d1|r，以及a?bq?r得d1|a.

d1|d. (1.3.2)

d?d1. ▋

辗转相除法 设a,b是任意两个正整数，多次利用带余除法，可得下列诸等式：

4

a?bq1?r1 0?r1?b,?b?r1q2?r2 0?r2?r1,??? ? ? ?? (*) rk?2?rk?1qk?rk 0?rk?rk?1,??rk?1?rkqk?1?rk?1 rk?1?0.??由于b是有限正整数，且b?r1?r2???rk?rk?1?0，所以(*)中的正整数k是存在的.

辗转相除法(*)是我国古代筹算家的一大成就，西方Euclid(欧几里德)也推得该法则，所以又称为Euclid算法.

定理1. 4 设a,b是任意给定的两整数，则由(*)式可得，(a,b)证明 反复利用定理1. 3有

例1. 3 设a解

?rk.

(a,b)?(b,r1)?(r1,r2)???(rk?1,rk)?(rk,0)?rk. ▋

??1895, b?1573, 求(a,b)??

(a,b)??(1895,15?73)(185. 9,反复利用定理1.3，如下面的辗转相除计算图. 再由定理1. 4即得

(a,b)?(1859,1573)?143. ▋

1859 1573 1573 1430 143=r2 2=q3 1=q1

q2=5

286=r1 286 0=r3 图1.4

定理1. 5

a与b的任一公约数是(a,b)的约数.

证 设d是a与b的任一公约数，则由(*)知d是b与r1的公约数，进而知d是r1与r2的公约数，如此继续，可得d是rk的约数. ▋

定理1. 6 （扩展Euclidean等式）若(a1,?,an)?d，则必存在整数ki(i?1,?,n)使

k1a1?k2a2???knan?d.

推论1.1

(a1,a2,?,an)?1的充要条件是存在t1,t2,?,tn??使

5

t1a1?t2a2???tnan?1.

定理1. 7 设a1,a2,?,an是任意n个整数.且(a1,a2)?d2，(d2,a3)?d3,? ,

(dn?1,an)?dn，那么(a1,a2,?,an)?dn.

性质定理1.2 i) 如果(a,b)ii) 如果(a,b)iii) 如果(a,c)?1,则(ac,b)?(c,b)； ?1，且bac，则bc；

?1，且(c,b)?1，则(ab,c)?1；

(a,b)?a?，进而有?,b??1. c?(a,b)(a,b)?iv) 如果c,b???c?0?是a与b的公约数,则?acc以上性质均易证明(请读者自证).以下我们讨论最小公倍数: 定义1. 5 设a1,a2,?,an是n(n?2)个整数.

i) 如果d是每个ai的倍数，则称d是这n个数的公倍数； ii)

a1,a2,?,an的一切公倍数中的最小正整数称为它们的最小公倍数，记为

[a1,a2,?,an].

由于任意正数均不是0的倍数，所以任意包含0的一组整数其最小公倍数均不存在. 性质定理1.3 设a1,a2,?,an是n个全不为零的整数，则有 i) ii) iii)

0?[a1,a2,?,an]?|a1a2?an|. [a1,a2,?,an]?[|a1|,|a2|,?,|an|]. [a1k,a2k,?,ank]?[a1,a2,?,an]|k|.

以上性质请读者自证.

定理1. 8 设a,b是任意两个全不为零的整数，若m是a,b的任意一公倍数，则有 i) ii)

[a,b]|m；

[a,b](a,b)?ab (ab?0);

iii)

m?mm?. ,????ab?[a,b] 6

类似于定理1. 7，我们有：

定理1. 9 设

a1,a2,?,an是n个全不为零的整数，[a1,a2]?m2，[m2,a3]?m3，?，

[mn?1,an]?mn，则有 [a1,a2,?,an]?mn.

例1. 4 i）求[136,221,391]?? 解 i)

?136,221,391??[[136,221],391]?[?136?221,391]??1768,391?.

171768?391?40664. （其中因为?136,221??17）. ▋

17练习1. 3

1. 对给定正整数a,b,c，证明

1) 如果a2) 如果a3)

b，那么abc. b且ac，那么a2bc.

ab当且仅当acbc，其中c?0.

2. 对于任意的正整数a，则三个整数a, a?2, a?4中必有一个能被3整除. 3. 对于任意的正整数a，证明2|a(a?1)，3|a(a?1)(a?2). 4. 设n是正整数，证明[an,bn]?[a,b]n.

5. 证明[a1,a2,?,ak,ak?1,?,an]?[[a1,a2,?,ak],[ak?1,?,an]]. 6. 证明下列结论

1) 如果a是奇数，那么24|a(a2?1)；

22) 如果a,b都是奇数，那么a|(a?b2)；

23) 对于任意的整数a，都有360|a(a2?1)(a2?4).

§1. 4 质数与合数

我们可以将整数分成两类，即奇数类与偶数类；当我们讨论正整数时，也可以将大于1的正整数分为两类，对于任何一个正整数a,它至少有两个正约数，即1与a, 称a得当然约数.有些正整数只是这两个当然约数，如3，5，7等，而另一些正整数则还有其它正约数，如6，还有约数2与3，这类约数称非当然约数或真约数.

7

定义1. 6 设a是一个大于1的正整数，如果a只有当然约数，则称a为质数或素数；若a有真约数，则称a为合数.

于是，正整数={1}?质数集?合数集. 性质定理1.4 设

p是任一质数，则有

i) 对任一整数a, 有(a,ii) 如果iii) 如果

p)?1或p|a.

p|ab, 则p|a或p|b.

p|a1a2?an则存在某i, 使p|ai.

p)|p, 而p为质数，于是(a,p)?1或p, 若(a,p)?p，即有pa.

证 i） 因为(a,ii) 如果

p?a, 则由（i）知(a,p)?1，由已知pab，于是由性质定理1. 4知pb.

iii) 此条是ii）的推广. ▋ 例1. 5 如果m是合数，试证nm证 设m?1?1也是合数. ?m?ab，那么

10m?1?(10a)b?1?(10a?1)(10?即

ab?1????10a?1)

9?1?1?9?1?1?(10a(b?1)???10a?1). ??m个a个所以1?1是nm的因数. ▋ ?a个练习1. 4

1. 证明奇素数可表示为两个自然数的平方差. 2. 设n是大于2的整数，则如果23. 试证正整数10?01是合数. ?2000个n?1和2n?1中有一为素数，那么另一数必为合数.

4. 设

p和pn+1均为素数，则p?2且n为2的方幂.

§1. 5 整数的分解—算术基本定理

任一大于1的整数a或者是素数，或者是合数，如果a是一个合数，设约数，则

p1是a的大于1的最小的正

p1是一个素数，且存在正整数q1使a?p1q1,(1?q1?a). 如果q1是一个素数，则a就表

p2，于是a?p1p2a2.如果a2是素数，则就表成

8

成了两个素数之积，如果q1非素数，则q1有素因数

三个素数之积，否则a2有素因数p3，如此继续下去，可知a一定可以表成若干个素数之积.

算术基本定理 设a是任一大于1的整数，则a能表成若干个素数的积： a=

其中

p1p2?pn, p1?p2???pn. (1.5.1)

p1,p2,?,pn是素数，且表达式(1.5.1)是唯一的.

我们将相同的pi可能有相同的，

算术基本定理也可以称为整数的唯一分解定理.(1.5.2)式中的素数素因数合写成方幂的形式，则有

a?p1?1p2?2?pk?k,?i?0,(i?1,2,?,k),其中pi?pj(i?j)是素数.

推论1.4 设a与b是任意两个正整数，其标准分解式为

a?p1?1p2?2?ps?s,?i?0,(i?1,2,?,s), a?p1?1p2?2?ps?s,?i?0,(i?1,2,?,s),

则

(a,b)?p1?1p2?2?ps?s,，其中?i?min(?i,?i) (1.5.4) [a,b]?p1?1p2?2?ps?s,其中?i?max(?i,?i) (1.5.5)

及

(a,b)[a,b]?ab.

练习1. 5

1. 分别求2160及99?99的标准分解式. ?????12个2. 利用Maple或Mathematica函数求8203513468500的标准分解式. 3. 设a,b,c是任意整数，则有

1）max(min(a,b),min(a,c))?min(a,max(b,c))； 2)

[(a,b),(a,c)]?(a,[b,c]).

§1. 6 Euler函数

定义1. 7 对任意正整数n, 定义?(n)为不超过n且与n互质的正整数的个数. 则?为?的一个函数, 称为Euler(L.Euler,1707—1783)函数.

如?(1)?1, ?(2)?1, ?(4)?1, ?(10)?4. 易知Euler函数有如下性质：

9

?n?是定义域

Euler函数的基本性质定理1.5： i). 若

p是素数, 则?(p)?p?1; 反之亦成立. 即若p为合数, 则有?(p)?p?2；

ii) 不超过n且与n互质的所有自然数的和为1n?(n)；

2iii) 若

p是素数, 则?(pk)?pk?1(p?1)；

iv) 若m?m1m2, 且(m1,m2)?1, 则?(m)??(m1)?(m2)； v) 若n?p1?1p2?2?pt?t是n的质数分解, 则

?(n)?n(1?1)(1?1)?(1?1)

p1p2pt?n?(1?1)或n?(1?1)（p为素数）;

ppip|ni?1证 i) 显然.成立. ii) 若a1,a2,?,a?t?n?是不超过n且与n互质的所有自然数, 则

(n?a1),(n?a2),?,(n?a??n?)

亦是不超过n且与n互质的所有自然数, 因此必有

a1?a2???a??n??(n?a1)?(n?a2)???(n?a?(n)).

于是

2(a1?a2???a?(n))??(n)?n,

即ii) 成立.

iii) 因为不超过个整数, 故不超过

pk且与

pk不互素, 即与

p不互素的所有自然数为p,2p,?,pk?1p, 共为pk?1kk?1p?p, 即

pk且与

pk互素的所有正整数的个数为

?(pk)?pk?1(p?1).

iv) 我们运用概率知识来证明该条. 记???1,2,?,m?;E??x??|(x,m)?1?; Ei??x??|(x,mi)?1?,i?1,2. 则

??m,E??(m),E1?m2?(m1),E2?m1?(m2).

设事件

A指从?中随机取一数, 该数属于E；事件Ai指从?中随机取一数, 该数属于Ei(i?1,2).

A发生当且仅当事件A1因为任意的x??,有(x,m)?1当且仅当且(x,m1)?1,(x,m2)?1, 即事件

10

与事件

A2同时发生. 由于(m1,m2)?1, 故A1与A2是相互独立的. 从而

P(A)?P(A1?A2)?P(A1)P(A2).

但是

P(A)?E???(m)m,

P(A1)?E1??m2?(m1)m??(m1)m1, P(A1)?E2??m1?(m2)m??(m2)m2.

所以

?(m)m??(m1)m1??(m2)m2.

即

?(m)??(m1)?(m2). ▋

1), i?1,2,?,t. 从而由ⅳ）得 pi2tv）由ⅲ）有?(pi?i)?pi?i?1(pi?1)?pi?i(1?1?(n)??(p1?)?(p2?)??(pt?)

?p1?1(1?111)p2?2(1?)?pt?t(1?) p1p2pt?n(1?t111)(1?)?(1?) p1p2pt?n?(1?i?11) (pi为n的全部不同的素因子) pi1?n?(1?) (p为素数) . ▋

pp|n下面我们介绍Euler函数的若干应用. 例1. 6 证明：素数有无穷多个. 证 设素数只有有限个

p1,p2,?,pn.令a?p1p2?pn, 则在1到a的所有正整数中与a互素的

只有一个, 即1. 因此?(a)?1, 但

?(a)??(p1p2?pn)

??(p1)?(p2)??(pn)

11

?(p1?1)(p2?1)?(pn?1)?1,

矛盾. 所以素数有无穷多个. ▋

例1. 7 设?(n)解 设n?1?n, 求n?? 3是n的素因数分解, 且

p1?1p2?2?pt?tp1?p2???pt, 则由?(n)?1n得等式

31p1?1p2?2?pt?t(1?1)?(1?1)?p1?1p2?2?pt?t.

p1pt3即有

因为果t. (2.2.2) 3(p1?1)?p(t?1)?p1p?2ptp1?p2???pt, 且pt|3(p1?1)?(pt?1)及pt为素数知pt?3, 从而t?1或2. 如

?1, 则n?3?1. 由(2.2.2)式得3(3?1)?3, 矛盾. 故t?2. 从而p1?2,p2?3. 此时,

1n?2?13?2且(2.2.2)成立. 即?(n)?n成立. 所以

3n?2?13?2,

其中?1,?2是大于0的整数. ▋

练习1. 6

1. 计算欧拉函数值?(2008). 2. 求下列数论方程的所有正整数解.

1）?(x)??(2x); 2)

?(3x)??(4x);

3. 证明分母不大于n的既约真分数的个数等于?(2)??(3)????(n). 12

§1. 7 同余的定义及性质

定义1. 8设m是一给定的正整数, 则称a与b关于模m同余, 记作a模m不同余, 记作aa与b是两个整数, 如果用m分别去除a与b.若得到的余数相同,

?b(modm),并称为同余式；若得到的余数不相同, 则称a与b关于

??b(modm).

依定义,任何一个偶然与0关于模2同余,任何一个奇数与1关于模2同余, 即有

2n?0(mod2), 2n?1?1(mod2)(n??).

再如365?5(mod12)??7(mod12). 显然对任何一整数a与b均有a?b(mod1).对任意两个不同的素数p与q有：q??p(modq)及

p??q(modp).

关于同余的性我们有如下定理

同余的性质定理1. 5 设m是给定的正整数,a,b,c,a1,b1,c1,a2,b2,c2是整数,则有 i)

a?b(modm),成立的充要条件是m|a?b.

ii) 同余是一个等价关系, 即有

a)

a?a(modm), （反身性）.

?b(modm), 则b?a(modm)（对称性）.

?b(modm)且a?c(modm),则a?c(modm)（传递性）.

b) 若ac) 若aiii) 若a1?b1(modm),a2?b2(modm), 则

a1?a2?b1?b2(modm)及a1a2?bb12(modm).

iv) 若av) 若a?b(modm).d?b(modm),d是m的任一因数, 则a?b(modd).

abm?(mod). ddd是a,b及m的任一公因数,则

vi) 若ac?bc?m?,则a?bmodmodm????.特别当(c,m)?1时,有a?b(modm).

(c,m)???1,2. 则a?b(mod[m1,m2]), 反之亦成立.特别当(m1,m2)?1时,

vii) 若a?b(modmi),i有a?b(modm1) 且a?b(modm2)的充要条件是a?b(modm1m2).

viii) 若

(a,m)?1, 则存在

b使

ab?1(modm)13

.可称

b为

a关于模

m的逆, 记为

b?a?1(modm)或a?1|m.

以上性质的证明均较易,我们证明其中几条为,为方便证明,用符号“?”表示“当且仅当”. 证 i)

a?b(modm)?a与b用m去除有相同的余数?a?b与0用m去除有相

同的余数?m|a?b.

ii)?c) 由i)

a?b(modm)且b?c(modm)?m|a?b且m|b?c

?m|(a?b)?(b?c)?a?c(modm).

iii) 由i) 得

a1?b1(modm)及a2?b2(modm)?m|a1?b1及m|a2?b2

?m|(a1(a2?b2)?(a1?b1)b2)?m|(a1a2?bb12)?a1a2?bb12(modm).

vi) 由i)

ac?bc(modm)?m|c(a?b)

??mmcmc?|(a?b)?|(a?b)（因为?,??1）

(c,m)(c,m)(c,m)(c,m)(c,m)???m??a?b?mod?.

(c,m)??vii) 由i) 知a?b(modm1)且a?b(modm2)?m1|a?b且m2|a?b, 即a?b是m1与

i)

m2的公倍数, 从而[m1,m2]|a?b. 再由m1,m2,???mt的情形.

a?b(mod[m1,m2])此性质可推广至任意有限个模数

viii) 若(a,m)?1,则存在整数b与c使ab?mc?1.于是ab?1?m(?c). 即m|(ab?1). 由

i) 得ab?1(modm) . ▋

以上性质形式简单, 证明容易, 但同余式类似普通等式的特点使其具有广泛的应用价值.下面是若于同余式性质的应用实例.

例1. 8 求2008365的个位数字.

365解 即要求一个0到9之间的数a使2008?a(mod10). 由于

2008365?(2?103?8)365?10k?8365.

所以2008365?8365(mod10).又82?60?4?4(mod10),84?42?6(mod10).因此

8365?84?91?1?(84)91?8?691?8?6?8?8(mod10).

14

故a?8. ▋

例1. 9 设?是正整数,?是?的各数位上的数字之和, 证明???(mod9). 证明 设??an?10n?????a1?10?a0,0?ai?9,an?0. 则??an?????a1?a0.由于

ii,10?1?1(mod9), i为正整数. 所以 10?1(mod9)an?10n?????a1?10?a0?an?1?????a1?1?a0?an?????a1?a0(mod9),

即???(mod9). ▋

例1. 10 设正整数

a?an?1000n?????a1?1000?a0,0?ai?1000.

则7整除a的充要条件是7|?(?1)a.

iii?0n证 因为1000??1(mod7),1000i?(?1)i(mod7), 所以由性质定理得

a?an?(?1)n?????a1?(?1)?a0(mod7).

故

7|a?7|?(?1)iai. ▋

i?0i?11|?(?1)ai及

i?0nn同样，因为1000??1(mod11)及1000??1(mod13).我们可得11|a13|a?13|?(?1)iai.

i?0n例1. 11 证明不定方程x证 设x0、

2?y2?8az2?6对任何给定的整数a无整数解.

y0及z0是该不定方程的一组整数解, 即有

222x0?y0?8az0?6. (1.6.1)

将上式关于2取模得x0模得x0222?y0?0(mod2). 因此x0与y0有相同的奇偶性. 再将(3.1.1)关于4取

222?y0?2(mod4).因此x0与y0同为奇数.于是x0?y0?1(mod8). 将(1.6.1)式关于8取

模便得0?6(mod8)矛盾. 故原不定方程无整数解. ▋

15

例1. 12 证明对任何整数n, 证 只要证对任意正整数n有 即可.

由于

f(n)?7n?1n3?1n5均是一个整数.

15357n?5n3?3n5?0(mod15) (1.6.2)

7n?5n3?3n5?n?2n3?n3?n(mod3),

而

n3?n?n(n?1)(n?1)?(n?1)?n(n?1)

是3的倍数, 故

7n?5n3?3n5?0(mod3). (1.6.3)

又

7n?5n3?3n5?2n?2n5?2(n?n5)(mod5)或

, 而

n5?n?(n?1)n(n?1)(n2?1)时,

及当

n?0?1或

?2(mod5). 当

n?0或

?1(mod5)(n?1)n(n?1)?0(mod5)n??2(mod5)时, (n2?1)?0(mod5), 因此不论n为何整数, 均有n5?n?0(mod5), 故

7n?5n3?3n5?0(mod5). (1.6.4)

因为(3,5)?1,所以由性质定理vii) 及(1.6.3)与(1.6.4)即可推得(1.6.2)成立. ▋

练习1.7

1. 1) 求19992) 求19992. 证明32000365的最后两位数字.

表示成17进制数时的个位数及最后两位数.

2000?41999?0(mod5).

3. 证明若一个三位数的数字（0到9之间的数）是相邻的三个数字, 且百位上的数字大于个位上的数字, 则该位数与它的数字次序相反的三位数的差等于是198.

4. 设十进制自然数21a39b8（其中0?a,b?9）为99的倍数, 求a与b. 5. 设n为正整数, 证明330|62n?52n?11.

?1, 求n6. 假设131|11?n??

16

§1. 8 同余类与剩余类

定义1. 9 设m是一给定的正整数, 则任意整数a关于模m同余0或1, 或2,???, 或m?1. 于是我们可将整数集划分成m个类：所有与r(0?r?m?1)同余的整数归为一类. 显然, 在同一类中的任两个

整数关于模m一定同余, 而不在同一类中的任两个整数关于模m一定不同余. 每一个这样的类称之为模

m的同余类或模m的剩余类. 从每个类中任取出一数, 则得到的这m个数就称为模m的完全剩余系, 又

简称m的完系.

若记r?m?为r所在的模m的同余类（或在明确模m的情况下简记为r）, 则有下列性质定理.

定理1. 10 设m是一给定的正整数, 则有 i) ii)

r?m???r?kmk???. r?m??s?m??mr?s.

iii) 对任意两整数r,s,或者riv)

?m??s?m?, 或者r?m??s?m???.

k个数a1,a2,???,ak构成的完系的充要条件是k?m,且当i?j时有ai??aj(modm).

以上性质由定义可直接得知.

根据完系的定义, 对于给定的正整数m, 模m的完系有无限个,下面我们给出几个常用的完系. 1) 模m的最小非负完全剩余系：

0,1,?,m?1.

2) 模m的最小正完全剩余系：

1,2,?,m

3) 模m的最大非正完全剩余系：

?(m?1),?(m?2),?,?1,0.

4) 模m的绝对值最小完全剩余系：

m为偶然时：?m,?,?1,0,1,?,m?1 或 ?m?1,?,?1,0,1,?,m.

2222m为奇数时：?m?1,?,?1,0,1,?,m?1. 22定理1. 11 若a1,a2,?,am是m的一个完系,

a与b是任意两整数且(a,m)?1, 则

aa1?b,aa2?b,?,aam?b

亦是m的完系.

证 由定理3. 2—iv), 只要证明对任何i如果aai?j,有aai?b??aaj?b(modm) 即可.

?b?aaj?b(modm), 则有aai?aaj(modm). 因(a,m)?1,由定理3.2—vii)即得

17

ai?aj(modm)▋

,这与

a1,a2,???,am为

m的完系矛盾,所以

aai?b?aaj?b(momd. )

例1. 13 若a1,a2,???,am是m的完系, 数之和为1m(m?1).

a,b??且(a,m)?1, 则aai?b除以m的最小非负余

2证 由定理3. 3知aa1?b,aa2?b,???,aam?b是m的一个完系. 因此aai?b （i?1,2

,???,m）除以m而得的m个最小非负余数构成m的一个完系, 即它们构成m的最小非负完全剩余系，

所以它们的和为0?1?2?????(m?1)1m(m?1). ▋ 2在模m的同余类中, 有些类中的每个数均与m互素, 如1所在的同余类中每个数均与m有互素. 若

?m?8, 则同余类1,3,5,7中的每个数均与8互素, 这样的同余类我们将给它们一个特定的名称.

定义1. 10 设m是一个大于1的正整数, 定义

i）模m的同余类r称为模m的一个简化同余类；如果(r,m)?1.

ii） 在模m的所有简化同余类中各取一数, 我们称这组数为模m的一个简化剩余系, 又称简系. 如果r是模m的一个简化同余类,

a是r中任一整数, 则a?r?0(modm), 即存在整数k使

a?r?km, 从而由(r,m)?1得(a,m)?1. 因此模m的同余类是模m的一个简化同余类的充要条

件该余类中的每个数均与m互素, 且由此可知,

定理1.12 i)

m的简系中的每个数皆与m互素, 于是我们有下列定理：

k个整数a1,a2,???,ak构成m的简系的充要条件是：

k??(m)；ii) (ai,m)?1；iii) ai??aj(modm), i?j.

证 (必要性) 由简系的定义知

a1,a2,???,ak是从模

m的所有简化剩余类中各取一数而构成

的.1,2,???,m是模m的一个完全剩余类, 于是模m的所有简化剩余类组成的集合是

?r|(r,m)?1,1?r?m?.

由Euler函数的定义可知：满足上面集合中条件的r共有?(m)个, 因此模m的简化剩余类共有

?(m), 故k??(m), 即i) 成立, 而ii) 及iii) 由简系的定义即知成立.

(充分性) 由必要性证明知，模m的简化剩余类共有?(m),条件i)及ii)说明a1,a2,

???,ak是模m的简化剩余类中选取的?(m)个整数,再由条件iii)即知:a1,a2,???,ak是从模m的全部

?(m)个简化剩余类中各选取的一数而成,所以依定义,a1,a2,???,ak是的一个简系. ▋

18

利用定理1. 12 我们便有下列结论：

定理1.13 设a与b是满足(a,m)?1及m|b的两整数, 若a1,a2,???,a??m?是m的简系, 则

aa1?b,aa2?b2,???,aa??m??b

亦是m的一个简系.

证 利用定理1.12, 由(a,m)?1及m|b便得(aai. 且若当?b,m)?(aai,m)?(ai,m)?1, 于是由

得(a,m?)1,

i?j时, 有

aai?b?aaj?b(modm), 则

aai?abj(modm)ai?aj(modm)这与a1,a2,???,a??m?为m的简系矛盾. 故aai?b?aaj?b(modm), 所以

aa1?b,aa2?b2,???,aa??m??b

构成m的简系. ▋

定义1.11 设m是一正整数, 则所有不超过m且与m互素的?(m)个数构成m的一个简系, 我们称该系为m的最小正简化剩余系（可简称最小正简系或缩系）.

例如, 8的最小正简系为1, 3, 5, 7.15的最小正简系为1, 2, 4, 7, 8, 11, 13, 14.

例1. 14 若

p为奇数, m是任一正整数且满足2m?1(modp), 证明

1m?2m?????(p?1)m?0(modp)

证 因

p为素数, 故1,2,???,p?1是p的简系, 又(2,p)?1, 从而由定理1.13知

2?1, 2?2, ???, 2?(p?1)

也是

p的简系, 因此得

1m?2m?????(p?1)m?(2?1)m?(2?2)m?????(2?(p?1))m(modp).

即有

(2m?1)(1m?2m?????(p?1)m)?0(modp),

亦即

p|(2m?1)(1m?2m?????(p?1)m),

但

p?(2m?1), 所以必有

p|1m?2m?????(p?1)m,

于是

19

1m?2m?????(p?1)m?0(modp). ▋

例1. 15 设m?m1m2,(m1,m2)?1, 数, 则

i) 当x跑遍m1的完系,ii) 当x跑遍m1的简系,我们只证明ii).

证 首先, 设x1,x2,???,x?a与b是满足条件(a,b)?1, m1|b及m2|a的任意两整

y跑遍m2的完系时,ax?by跑遍m的完系. y跑遍m2的简系时,ax?by跑遍m的简系.

?m1?是m1的简系, x1,x2,???,x??m2?是m2的简系, 则

{ax?by|x?{x1,???,x?(m1)}, y?{y1,???,y?(m2)}}

共有?(m1)?(m2)个数, 即?(m1m2)（??(m)）个数, 定理1.12的第i) 条成立.

其次, 如果

axi?byj?ax??byk(modm1m2),

. 再由

那么

, axi?byj?ax)??byk(mod1m从而有

, xi?x?(modm1)由

m1|b得axi?ax?(modm1)(a,b)?1知(a,m1)?1,

即有

i??. 同理可证j?k. 因此, 定理1.12的第iii)条成立.

最后证(axi?byj,m1m2)?1成立.

?1及m1|b知(a,m1)?1, 故(axi,m1)?1. 再由m1|b可得

因为(xi,m1)?1, 又由(a,b)(axi?byj,m1)?1.

同理可证

(axi?byj,m2)?1.

因此, 由(m1,m2)?1, 即得

(axi?byj,m1m2)?1.

从而根椐定理1.12便知

axi?byj（i?1,???,?(m1),j?1,???,?(m2)）

是m?m1m2的简系. ▋

特殊情形, 可取a?m2,b?m1.

定理1. 15（Euler定理） 设m是任一给定的正整数，a是任一整数且(a,m)?1, 则有

20

(1.8.1) a??m??1(momd. )证 设x1,x2,???,x?(m)是m的一个简系, 则由(a,m)?1及定理1.13知ax1,ax2,???,ax??m?亦是

m的一个简系, 因此有

x1?x2???x?(m)?ax1?ax2???ax?(m)(modm).

即

a?(m)?x1x2???x?(m)?1?(x1x2???x?(m))(modm). (1.8.2)

而由于(xi,m)?1, i?1,2,????(m), 故(x1?x2???x??m?,m)?1, 于是便得

定理1. 16（Fermat定理） 若

a??m??1(modm). ▋

p是一素数, a是任一整数, 则有

ap?a(modp). (1.8.3)

证 若(p,a)?1, 则由Euler定理及?(p)?p?1得ap?1?1(modp),再由a?a(modp)便有

ap?a(modp).

若(p,a)▋

例1. 16 求19992001?1, 即p|a, 则ap成立. ?0?a(modp), 即有ap?a(modp), 所以(1.8.3)除70的余数是多少？

解 因(1999,70)?1, ?(70)??(2)??(5)??(7)?24, 所以由Euler定理得

199924?1(mod70).

而2001?83?24?9及1999?28?70?39, 故

8319992001?(199924)?19999

?183?19999?19999?399?29(mod70).

所以19992001除70的余数是29. ▋

1998例1. 17 求证1?21998?????20001998是1999的倍数.

证 因1999是素数, 故?(1999)?1998.于是由Euler定理得

k1998?1(mod1999), k?1,2,???,1998,2000

从而

21

11998?21998?????19981998?19991998?20001998 ?1?1?????1?0?1?1999?0(mod1999).

这说明11998?21998?????20001998是1999的倍数. ▋

7例1. 18 证明对于任意整数n, 有n 证 由Fermat定理,

?n(mod42).

n7?n(mod7). 此外

n7?n?n(n6?1)?n(n2?1)(n4?n2?1） 从而有

?(n?1)n(n?1)(n4?n2?1)?0(mod6)，

n7?n?0(mod42). ▋

练习1.8

1．分别针对下列三种情况求模15的一个完系, 使

i) 该完系的每个数是偶数； ii）该完系的每个数是奇数； iii）该完系的每个数是绝对值最小的.

2．将上题1的“模15”换成“模12”后能否完成此题？ 3．设a1,a2,???,ak是模m(?2)的一个简系, 证明?ai?0(modm).

i?1k4．求模3的一个完系

i) ii）

完系.

?a1,a2,a3?及模5的一个完系?b1,b2,b3,b4,b5?使得

?abiij|i?1,2,3;j?1,2,3,4,5? 构成模15的一个完系.

j?a?b|i?1,2,3;j?1,2,3,4,5?及?aibj|i?1,2,3;j?1,2,3,4,5?同时是模

15的

5．将题7的“完系”换成“简系”后结论仍成立吗？ 6．设m1,m2是正整数, 证明当x跑遍m1的完系及完系.

§1. 9 一次同余方程

同余方程可以说是同余理论的核心, 象著名的中国剩余定理（孙子定理）及在公钥密码学很有应用价值的Legendre符号均源自于同余方程.

y跑遍m2的完系时, 则x?m1y跑遍m1m2的

22

定义1. 12 设m是一个大于1的正整数，a(?0),b是两个整数, 称同余式

ax?b?0(modm), 其中m?a. (1.9.1)

为x的模m的一次同余方程, 简称模m的同余方程.

如果整数x0满足ax0由此, 我们称x?b?0(modm), 那么所有关于模m同余于x0的整数均满足方程(1.9.1).

?x0(modm)是方程(1.9.1)的一个解.

x?x0(modm), 则ax0?b?0(modm),于是由dm及

设(a,m)?d, 如果(1.9.1)有解

dax0知db.这说明db是(1.9.1)有解的必要条件.

下面我们证明该条件也是(1.9.1)有解的充分条件, 即有 定理1. 17 同余方程

(1.9.1)有解的充要条件是db.

个解为

当

(1.9.1)有解时, 其解数为

d,若

x?x0(modm)为(1.9.1)的一个, 则其dx?x0?mk(modm), k?0,1,?,d?1. (1.9.2) d证明 必要性已经证明. 现证明充分性. 设db, 由(1.9.1)得

abm??x??0?mod? (1.9.1)* ddd???am?因?,??1, 故由?dd?得

Euler

?a?定理知???d?m??????d?m???a??1?mod?. 将(1.9.1)*两端乘??d???d?m??????1?d?便

即

?a????d?m??????d?x?b?a????d?d?m??????1?d?m???0?mod?,

d??

b?a?x????d?d?m??????1?d?m??mod??. (1.9.3)

d??b?a?????d?d?m??????1?d?这说明(1.9.3)是方程(1.9.1)*的一个解.进而可以验证x一个解, 充分性得证.

若xm??mod??是(1.9.1)的

d???x0(modm)是(1.9.1)的一个解, 则易证

23

x?x0?是(1.9.1)的d个不同的解.

如果x?mk(modm) (k?0,1,?,d?1) dx1(modm)是(1.9.1)的任一解, 即ax1?b?0(modm), 则由x?x0(modm)得

a(x1?x0)?0(modm).

于是m|a(x1?x0), 从而

mma?ma?(x1?x0).因为?,??1, 故有|(x1?x0), 亦即存在整数t,

ddd?dd?使得x1?x0?mt.设t?ld?k,0?k?d?1, 则 dmmmx1?x0?(ld?k)?x0?k?ml?x0?k(modm),

dddx1?x0?mk(modm),0?k?d?1. d即

所以(1.9.1)的任一解均是(1.9.2)的形式. ▋

由定理1. 17的证明中的(1.9.3)式, 我们有下列结论: 推论 当(a,m)?1时, 同余方程(1.9.1)有唯一解

x??b?a?(m)?1(modm). (1.9.4)

?(m)?1直观上看, 当模m较大时, 由于计算a实际.

例1. 19 求下列同余方程的解. i)

不易, 所以利用(1.9.4)来求得同余方程的解一般不大

3x?5?0(mod4)； ii) 58x?87?0(mod47)； 129x?831(mod1101).

?1(mod4)是所求方程的解.

iii)

解 i) 因(3,4)?1, 该方程有唯一解. 由(1.9.4)可得xii) 因(58,47)?1, 该方程有唯一解. 由于58?(47)?1不易计算, 我们不可利用(1.9.4)来求其解. 因

58?11(mod47), 87?40(mod47), 故原方程等价于

11x??7(mod47).

由于(4,47)?1, 将方程两端乘4后得：

24

44x??28(mod47),

即

3x?28(mod47),

再由(16,47)?1, 方程两端乘16后得

48x?448(mod47),

即

x?25(mod47).

iii) 因(129,1101)?3831, 故原方程有三个解. 化简原方程得

43x?277(mod367). (1.9.5)

因(43,367)?1, 故(1.9.5)有唯一解. 将其解形式地表为

277(mod367). 43277?367644?(mod367). 再分子、分母约去2得将分子、分母同加模数367得x?43?367410322?45?9x?(mod367). 将分子加上?367, 得x?(mod367), 约去5得x?(mod367).

20520541?81286(mod367). 将分子加367, 分母加?367后得x?(mod367). 约分子、分母同乘9得x?3692143(mod367). 即x?143(mod367)是同余方程(1.9.5)的解. 从而x?143(1101)去2得x?1x?是原方程的一个解.依据定理1.17, 原方程的三个解为

x?143, 143?367, 143?367?2(mod1101),

即x?143,510,877(mod1101). ▋

在例1.19的求解同余方程的过程中, 求解i)用的是公式法(1.9.3), 或称定理求解法.

求解ii) 是用与模互素的数乘或除同余方程的两端, 使x的系数逐渐减小, 以达到求解的目的, 此法可称为“数乘除法”.

求解iii) 的方法其原理同求解i) 的方法, 只不过这里是采用一种简便的形式表达法, 均是利用同余式的性质求解, 其步骤是：先将同余方程(1.9.1)两边约去因数得同余方程.

a1x1?b1?0(modm1), (a1,m1)?1. (1.9.1)**

然后将(1.9.1)**的解形式地表为x?ab1(modm1), 此处1b1a125

仅是一个分数形式的符号, 再将分子或分

母减去或加上模的倍数及分子、分母乘以不为0的整数或约去一个与模数互素的数等若干次（这相当于对同余式的两边使用同余的性质）, 使分母的绝对值变小, 直至最后将“分数”变成整数, 即得(1.9.1)**的解, 由此便可求得(1.9.2)的解, 此法可称为“分式法”. 又例：

例1. 20 求解同余方程1593x?1125(mod1926).

解 因(1593,1926)?91125, 所以同余方程有九个解,将其简化得

177x?125(mod214).

因此

x?125125?214339113113?5565????? 1771771775959?5295137137?2143511313?7192367??????? 81818133?71213?1??67?147(mod214).

所以原方程的9个解为：

x?147,361,575,789,1003,1217,1431,1645,1859(mod1926). ▋

对于给定的一个同余方程, 用何种方法求解简单方便？若模m较小, 则用公式法直接简单. 若模m较大, 则用“数乘除法 ” 、还是“分式法”求解简捷, 应视具体情况而定.

练习1. 19

1. 下列同余方程有无解？有解时有几个解？

1) 3) 2.

1998x?1999(mod2000); 2) 111x?1110(mod1011); 891x?918?0(mod198); 4) ax?54?0(mod45).

b取何值时, 方程14x?b(mod114)

1) 在0?x?114中有多于一个的解？ 2) 无解.

3．利用本节提到的几种方法, 求解下列同余方程.

1) 3)

3x?12?0(mod15); 2) 49x?84?0(mod104); 5x?2(mod7) ; 4) 71x?1997(mod1999);

4. 知某一正整数的99次方除以97后得余数7, 而该正整数的100次方除97后得余数79, 问该正整数除以97后得到的余数是多少？

26

§1. 10 一次同余方程组与孙子定理

定义1. 13 有多个同余方程构成的组合称为同余方程组；称(1.10.1)式为一次同余方程组.

d1)?a1x?b1?0(mom?ax?b?0(momd2)?22 (1.10.1) ? ?????anx?bn?0(modmn)其中m1,m2,?,mn是正整数.

如果存在整数

x0使aix0?bi?0(modmi),(i?1,2,?,n),则称x?x0(modm)是(1.10.1)的一个解, 这里m??m1,m2,?,mn?.

本节的目的就是讨论(1.10.1)的解问题.

若(1.10.1)有解, 则(1.10.1)中每个同余方程有解；反之, 若(1.10.1)中某个同余方程无解, 则

(1.10.1)无解, 所以要研究(1.10.1)的解,可转化为研究下列同余方程的解.

?x?c1(modm1)?x?c(modm)?22 . (1.10.2) ? ?????x?cn(modmn)关于模

定理1.18(中国剩余定理) 若

m1,m2,?,mn是n个两两互素的正整数,则(1.10.2)m?m1m2?mn有唯一解

其中xi是

x?mx1c1?mx2c2???mxncn(modm), (1.10.3)

m1m2mnmx?1(modm)的一个整数解?i?1,2,?,n?. imim,m)?1.于是由定理1. 17知, 同余方 mii证 （存在性） 由m1,m2,?,mn两两互素知(程

mx?1(modm)(i?1,2,?,n) (1.10.4)

imi（i有唯一解. 设为x?x(modm). 即有mxi?1(modmi). 从而由mi|miimjmi?j）得

27

mxc?mxc???mxc?mxc?1?c?c(modm).

iiim111m222mnnnmiii这说明

x?mx1c1?mx2c2???mxncn(modm)

m1m2mn是(1.10.2)的一个解.

(唯一性) 若x?x1(modm)及x?x2(modm)是(1.10.2)的两个解, 则有x1?ci(modmi)及

?,n)两两互素得x2?ci(modmi)(i?1,2,?,n).于是x1?x2(modmi),从而由mi(i?1,2,, 亦即x1?x2(modm). 这说明x1(modm)与x2(modm)是(1.10.2)的x1?x2(modm1?mn)同一个解, 所以(1.10.2)只有一个解. ▋

定理1.18的存在性的证明过程具体给出了在mi两两互素的情况下同余方程组(1.10.2)的解法：首先分别求出每个方程

mx?1(modm) (i?1,2,?,n)

imi的一个整数解xi, 然后代入(1.10.3)式计算化简即得(1.10.2)的解.

定理1.18其实就是著名的孙子剩余定理, 国际上一般称之为中国剩余定理（Chinese Remainder Theorem， 又简称为CTR定理）.

历史回顾：公元五世纪前后, 我国出现了一部著名的著作-《孙子兵法》, 书中提出了这样一个问题：“今有物不知其数, 三三数之剩二, 五五数之剩三, 七七数之剩二, 问物几何?”该问题简称“物不知数”问题.

如设所要求的物数为x, 则x就是下列同余方程组(1.10.5)的一个正整数解.

?x?2(mod3)??x?3(mod5). (1.10.5) ?x?2(mod7)?对于“物不知数”问题的解法,《孙子算经》中记述：“凡三三数之剩一, 置七十；五五数之剩一, 置二十一；七七数之剩一, 则置十五；一百零六以上, 以一百零五减知即得.”

明朝程大位在一五九三年出的一部著作《算经统宗》中关于“物不知数”问题有一首解法歌诀：

“三人同行七十稀, 五树梅花二十一支, 七子团圆整半月, 除百零五便得知.”

也就是说 , 该问题的解答是x例1. 21 解同余方程组

?70?2?21?3?15?2?233?23(mod105).

28

? x?1(mod5)??3x?2(mod7). ?5x?7(mod9)?解 该方程组形同(1.10.1), 先化为(1.10.2)的形式：即

?x?1(mod5)??x?3(mod7). ?x?5(mod9)?再利用孙子定理, 解形如

(1.10.4)的三个方程：

63x?1(mod, 545x?3(mod7)及

35x?5(mod9). 分别解之得x1?2,x2??2及x3??1各是上述同余方程的一个整数解.于是由(1.10.3)得原同余方程组的唯一的解为

x?63?2?1?45?(?2)?3?35?(?1)?5

??319??4(mod315). ▋

例1. 22 解同余方程组

?3x?11(mod28). ??5x?17(mod44)解

3x?11(mod285x?17(mod28)分别等价于 及

?3x?11(mod4) 及 ?3x?11(mod7)?从而原方程等价于

?5x?17(mod4), ?5x?17(mod11)??3x??1(mod4)?3x?4(mod7)?, 亦即 ?5x?1(mod4)???5x?6(mod11)然后如例1. 21那样解最后这个方程组即可.

例1. 23 解同余方程组

?x?1(mod4)??3x?4(mod7). ?5x?6(mod11)?? 2x? 4(mod8). ?15x?18(mod33)?解 因方程

2x?4(mod8)有两个解x?2,6(mod8), 方程15x?18(mod33)有三个解

x??1,10,21(mod33).

29

于是原同余方程组的解为下列六个同余方程组的全部解.

?x?2(mod8) ； ??x??1(mod33)?x?6(mod8) ； ?x??1(mod33)??x?2(mod8)； ??x?10(mod33)?x?6(mod8)； ?x?10(mod33)??x?2(mod8); ??x?10(mod33)?x?6(mod8). ?x?21(mod33)?分别利用孙子定理解之便得原同余方程组的六个解：

x?98,10,186,230,142,54(mod264). ▋

练习1.10

1. 解下列同余方程组

?x?1(mod7)?1）?x?2(mod8); 2)

?x?3(mod9)?2. 解答下列各题：

?11x?7(mod10)??3x?10?0(mod11); ?5x?3?0(mod13)?1) 有物不知其数. 三数余一, 五数余二, 七数余三, 11数余四, 问该物数.

2) 今有数不知总数. 以五累减之无剩, 以七百十五累减之剩十, 以二百四十七累减之剩一百四十,

以三百九十一累减之剩二百四十五, 以一百八十七累减之剩一百零九, 问总数若干？

3．有一电脑病毒每隔十三天连续发作两天, 有一次该病毒刚好在星期六、星期日发作,问该病毒至少要几星期后再在星期六发作？

4. 求既能被7除余3, 又能被11除余4的所有三位自然数之和.

5．试求一个满足下列条件的最大的负整数：该负整数用15除余8, 用10除余3, 用8除余1.

§1. 11 原根的定义

设m是大于1的正整数. 若(a,m)?1, 则由欧拉定理知a定义1. 14 1）设m?(m)?1(modm).

为模数

?1且(a,m)?1. d是方程ax?1(modm)的最小正整数解, 则称dm的阶，记作ordm(a). 2）设m?1且(a,m)?1. 如果对于所有的正整数k??(m), 都有ak?m, )则称a为模数m的一个原根. ?1(mod例如, 若m?7, a?2, 则20?1, 21?2, 22?4, 23?1(mod7), 因此ord7(2)?3.

例如,3是模数7的原根, 也是模数10的原根. 但是并非所有的模数m都有原根, 例如模数8就没有原根, 因为?(8)?4,而12?32?52?72?1(mod8).

例1. 24 设(a,m)?1, m?1,

a1 ,a2 ,? ,a?(m)是小于m且与m互素的不同的正整数.如果

30

a是模数m的一个原根, 那么

a ,a2 ,? ,a?(m)

与a1 ,a2 ,? ,a?(m)按一定的顺序对应关于模m同余.

证明 因为(a,m)?1, 所以对任何k:1?k??(m), 有(ak,m)?1, 于是ak与某个ai关于模

m同余, 且集合?a,a2,?,a?(m)?中的?(m)个数关于模m两两不同余, 因此集合?a,a2,?,a?(m)?中的每个数“与且仅与”集合▋

定理1. 19 设m数.

这里略去证明，有兴趣的读者可参考其它初等数论书籍. 定理1. 20 设m集合

?a,1a2?,,?am(?)中

的某个数关于模

m同余.

?1, 若模数m有原根的充要条件是m等于2, 4, pl或2pl, 其中l?1, p为奇素

?1, 模数m有原根g, 则m恰有?(?(m))个关于模m不同余的原根,它们是由

S??gt|1?t??(m),(t,?(m))?1?

中的数给出.

证明 设g是m的一个原根, 则ordm(g)??(m). 由于?(m)个整数

1,g,?,g?(m)?1

关于模m两两不同余, 因此它们构成m的一组简化剩余系. 设a是m的任一原根, 则存在某个整数

k: 1?k??(m)，使gk?a(modm). 由定理4. 2可知a关于模的阶为

?(m)??(m).

(?(m),k)故(?(m),k)?1, 即a与S中的一个数关于模m同余. S中的任意一个数关于模m的阶均为?(m), 因而均是原根. 而S中的数关于模m两两

另一方面,

不同余, 因此S给出了关于模m全部两两不同余的原根, 共?(?(m))个. ▋

例1. 25 已知2是模数11的一个原根, 求出模数11的所有原根. 解 因为?(11)?10且2是模数11的一个原根, 所以

?1,2,?,2?是模数11的一组简化剩余系.

9 31

由于

1,2?,,中9与10

互素的整数有

?(10?)4个,它们是1,3,7,. 9所以由定理

1.20及

21?2(mod11),23?8(mod11),27?7(mod11),29?6(mod11)可得, 模数11的所有原根是

2,6,7,8. ▋

练习1. 11

1. 证明5是6的一个原根，也是7的一个原根. 2. 证明2是13的一个原根，并由此求出13的所有原根. 3. 求出41的一个原根. 4. 证明：如果素数5. 设

, 则a是p的一个原根. p?2??1, (ap)??12p是奇素数, 求同余式xp?1?1(modps), s?1的全部解.

22素数71有一个原根7, 求出71的所有原根, 并求71和2?71的一个原根.

§1.12 二次剩余

定义1.15 设m是正整数，a是整数且满足(a,m)?1, 如果同余方程

x2?a(modm) (1.12.1)

有整数解, 则称a是模m的二次剩余或平方剩余(Quadratic Residue), 记作a?QRm. 否则称a是模m的二次非剩余或平方非剩余(Non-Quadratic Residue), 记作a?NQRmm.

例如，1，3，4，5，9模11的二次剩余.2, 6，7，8，10是模7的二次非剩余.1，9，11是模14的二次剩余，3，5，13是模14的二次非剩余.

显然, 如果a?b(modm), 那么a是模m的二次剩余当且仅当b是模m的二次剩余. 因此, 一个

给定的整数是否为模m的二次剩余? 只需要考虑模m的简系中的对应元素是否为模m的二次剩余.

由于一般正整数模的二次剩余问题可转化成其不同素因子的二次剩余问题，所以下面只涉及素数模的二次剩余的情形.

例1.26 对于模剩余？

解 为了确定1,2,?,12中哪些是模13的二次剩余，需要知道，当a跑遍集合些同余方程

32

p?13, 判断1,2,?,12中哪些数是模13的二次剩余？那些数是模13的二次非

?1,2,?,12?时，哪

有解.

已知整数1,2,?,12的平方是

x2?a(mod13)

12?122?1(mod13), 22?112?4(mod13), 32?102?9(mod13), 42?92?3(mod13), 52?82?12(mod13), 62?72?10(mod13).

由上面的计算结果可知, 模13的二次剩余是1,3,4,9,10,12. 二次非剩余是▋

对于给定的奇素数

2,5,6,7,8,11.

p, Euler 给出了判断一个整数a是否为模p的二次剩余的判别方法.

p是奇素数且(a,p)?1, 那么整数a是模p的二次剩余的充分且必要

定理1.21（Euler准则） 设条件是

a(p?1)2?1(modp).

证 设a是模

p的二次剩余. 则x2?a(modp)有一个整数解, 设为x1.由Fermat小定理可得

a(p?1)2?(x12)(p?1)2?(x1)p?1?1(modp).

反之，设

a(p?1)2?1(modp), r是模

p的一个原根, 那么存在整数

k(1?k?p-1)使得

. 因此 a?rk(modp)rk(p?1)/2?a(p?1)/2?1(modp).

由r是模

p的一个原根可得(p?1)k(p?1)2, 于是k是偶数. 设k?2j, 则有

(rj)2?r2j?rk?a(modp).

这说明r是同余方程xj2?a(modp)的一个解, 即a是模p的二次剩余. ▋

p是奇素数且(a,p)?1, 那么整数a是模p的二次非剩余的充分

例1.27(Euler准则的推论) 设且必要条件是

a(p?1)2??1(modp).

证 如果

p是奇素数且(a,p)?1, 由Fermat小定理可得ap?1?1?0(modp).于是

(a(p?1)2?1)(a(p?1)2?1)?ap?1?1?0(modp)，

33

因此

a(p?1)2?1(modp) 或 a(p?1)2??1(modp)

成立，且不能同时成立.假若同时成立,则有1??1(modp)或p2，这与p是奇素数矛盾.

既然模

p的二次非剩余不满足a(p?1)2?1(modp)，那么必满足a(p?1)2??1(modp).

(p?1)2反之，若a??1(modp)，则由定理1. 21可知a是模p的二次非剩余. ▋

练习1. 12

1．分别找出素数11，13的所有二次剩余. 2. 分别找出整数7，11的所有二次非剩余. 3．证明对于奇素数

?12p，模p的二次剩余与整数12,22,32,?,(p2)关于模p同余.

4．证明若a是奇素数模5．证明若

p的二次剩余，那么a不是模p的原根.

(p?5)(p?1)??2?8. ???(?1)?p?p是奇素数，则

6．对于奇素数或者同为模

p, 如果ab?r(modp), 且r模p的二次剩余, 那么a,b同为模p的二次剩余,

p的二次非剩余.

7. 是奇素数. 如果

a,b同为模p的二次剩余，或者同为模

p的二次非剩余, 那么同余式

有解. a?x2?b(modp)§1.13 Legendre符号与Jacobi符号

由Euler准则我们可以判定一个整数是否为模

p的二次剩余.但是当p很大的时候，这种判断方法计算

起来有一定困难，不实用.利用下面我们介绍的勒让德（Legendre）符号，则可得到一个计算上相对简便的判别方法.

定义1. 16 设

p是奇素数，模p的勒让德（Legendre）符号定义为：

? 1 如果(a,p)?1且 a 是模数 p 的二次剩余;?a???p????1 如果(a,p)?1且 a 是模数 p 的二次非剩余; ???? 0 如果 pa.注意：如果

p是奇素数，那么同余式且

p)，而且如果x2?1(modp)只有解x??1(mod?,?????1,0,1?

???? (modp)，那么

p(????) ，因此????.特别地，如果

34

?a??a??p???(modp)，那么?p???????.

定理 1.22 ( Legendre符号性质定理) 设

p是奇素数，(a,p)?1，(b,p)?1, 那么

i) 如果a?????b(modp)，那么?a???b?；

?p??p?ii)

?a2??p??1; ???a??p?1?2(modp)(在某些教科书中, 该性质也称为Euler准则)； ?p??a???ab??a??b?rkr0rr21?p???p??p?,一般地,如果整数a的素因子分解式为a??2q1q2?qk, 那??????iii)

iv)

么

?ap????p1??? v)

证明 i）显然. ii）对于同余式x2rkr0qr1qr2q??????k212?p??p???p?； p????????1??1?p?12?(?1)，. ?1???????p??p??2??a2(modp)，a就是它的解, 因此?a??1.

?p?iii) 由定理1. 21直接可得?iv) 由ii)可得：

?a?(p?1)2(modp). ??a?p??ab?????(p?1)2(modp)?a(p?1)2?b(p?1)2(modp)??a??b?(modp). ?p??(ab)???p??p?由于勒让德符号为1或

?1,

假若

?ab??a??b?p, )矛盾. ?p???p??p, ?那么1??1(mod??????因此

?ab??a??b??p???p??p. ???????v） 由iii)直接可得. ▋ 例1. 28 设

p是奇素数，则有

35

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