同余的性质与应用

同余的性质及应用

1 引言

数论的一些基础内容的学习，一方面可以加深对数的性质的了解，更深入的理解某些其他邻近学科，另一方面，可以加强数学训练.而整数论知识是学习数论的基础，其中同余理论有时整数论的重要组成部分，所以学好同余理论是非常重要的.

在日常生活中，我们所要注意的常常不是某些整数，而是这些数用某一固定的数去除所得的余数，例如我们问现在是几点钟，就是用24去除某一个总的时数所得的余数；问现在是星期几，就是问用7去除某一个总的天数所得的余数，假如某月2号是星期一，用7去除这月的号数，余数是2的都是星期一.

我国古代孙子算经里已经提出了同余式xb1(modm1),xb2(modm2),?,

xbk(modmk)这种形式的问题，并且很好地解决了它.宋代大数学家秦九韶在他的《数

学九章》中提出了同余式x?Mi1(modmi), i?1,2,...,k, mi是k个两两互质的正整数，

m?m1m2...mk,m?miMi的一般解法.

同余性质在数论中是基础，许多领域中一些著名的问题及难题都是利用同余理论及一些深刻的数学概念，方法，技巧求解.例如，数论不定方程中的费尔马问题，拉格朗日定理的证明堆垒数论中的华林问题，解析数论中，特征函数基本性质的推导等等.在近现代数论研究中，有关质数分布问题，如除数问题，圆内格点问题，等差级数问题中的质数分布问题，an2?bn?c形式的质数个数问题，质数个数问题，质数增大的快慢问题，孪生质数问题都有一定程度的新成果出现，但仍有许多尚未解决的问题.

数论的发展以及现代数学发展中提出的一些数论问题，都要求我们对于近代数论的一些方法和基础知识，必须熟练掌握.所以，本文主要介绍了同余理论中同余基本性质的一些简单应用，通过本文的阐述，希望可以为对数论有兴趣的读者，增加学习数论知识的兴趣，并能为他们攻破那些经典的数论难题开展数论课题课题提供一些帮助.

2 同余的概念

给定一个正整数m，把它叫做模，如果用m去除任意两个整数a与b所得的余数相同，我们就说对模m同余，记作a?b(modm),如果余数不同，就说对模m不同余. 由定义得出同余三条性质： （1）a?a(modm)；

（2）a?b(modm),则b?a(modm)；

（3）a?b(modm),b?c(modm),则a?c(modm).

定义也可描述为:整数a,b对模m同余的充分必要条件是ma?b,即a?b?mt,t是整数.

3 同余的八条基本性质

由同余的定义和整数的性质得出[1]：

（1）若a?b(modm),c?d(modm),则a?c?b?d(modm) 若a?b?c(modm), 则a?c?b(modm) （2）若a?b(modm),c?d(modm), 则ac?bd(modm)特别地,若a?b(modm),则ak?bk(modm)

（3）若A?...??B?...?(modm), xi?yi(modm), i?0,1,...,n1k1k则?A?...?x1?...xk??1k1k?B?1...?ky11...ykk(modm)

??（4）若a?a1d, b?b1d, (d,m)?1, a?b(modm),则a1?b1(modm) （5）若a?b(modm),k?0, 则ak?bk(modm)；

若a?b(modm), d是a,b及m任一正公因数,则

ad?bd(modmd)

（6）若a?b(modmi),i?1,2,...,k,则a?b(mod[m1,m2,...,mk])

1

其中[m1,m2,...,mk]是m1,m2,...,mk, k个数最小公倍数 （7）若a?b(modm), dm,d?0,则a?b(modd)

（8）a?b(modm), (a,m)?(b,m),若d能整除m及a,b两数之一,则d必整除a,b另一个.

4 同余性质在算术里的应用

4.1 检查因数的一些方法

例1 一整数能被3(9)整除的充要条件是它的十进位数码的和能被3(9)整除. 证:按照通常方法,把任意整数a写成十进位数形式,即

a?an10?an?110nn?1?...?a0, 0?ai?10.

因10?1(mod3), 所以由同余基本性质,即3a当且仅当3同法可得9a当且仅当9?ai；

?ai，i?0,1,...,n.

例2 设正整数a?an1000n?an?11000n?1?...?a0，0?ai?1000，则7（或11或13）整除a的充要条件是7（或11或13）整除(a0?a2?...)?(a1?a3?...)?i?0,1,...,n.

?(?1)aii，

证：1000与-1对模7（或11或13）同余，

根据同余性质知，a与?(?1)iai对模7（或11或13）同余

即7（或11或13）整除a当且仅当7（或11或13）整除?(?1)iai，i?0,1,...,n. 例3 a=5874192，则?ai?5?8?7?4?1?9?2?36，i?0,1,...,n能被3，9整 除，当且仅当a能被3，9整除 解：由例1证法可知，该结论正确.

?3?5?6?9?3?30例4 a=435693，则?ai?4，但?aii?0,1,...,n能被3整除，

不能被9整除当且仅当3是a的因数，9不是a的因数.

2

解：由例1的证法可得.

例5 a=637693，则a?637?1000?693，?ai?693?637?56，i?0,1,...,n能被7整除而不能被11或13整除当且仅当7是a的因数但11，13不是a的因数. 解：由例2的证法可知，该结论正确.

例6 a=75312289，a?75?10002?312?1000?289i?0,1,...,n能被

?ai?289?312?75?52，

13整除，而不能被7，11整除当且仅当13是a的因数，而7与

11不是a的因数. 解：由例2的证法可知.

例7 应用检查因数的方法求出下列各数标准分解式

①?? 1535625 ②1158066

解：①1535625?1?106?5?105?3?104?5?103?6?102?2?101?5， ?ai?1?5?3?5?6?2?5?27，927 ?91535625， 1535625?1?10002?535?1000?625，

(a0?a2)?a1?625?1?535?91，由例2得1391，791， ?71535625，131535625， 又51535625，9?5?13?7?4095， 5375，

3755?7515356254095?375，

，2575，

?1535625?35?54?13?7.

②1158066?1?106?1?105?5?104?8?103?6?101?6， ?ai?1?1?5?8?6?6?27，927?91158066， 1158066?1?10002?158?1000?66，

(a0?a2)?a1?66?1?158??91，由例2得791，1391 ?71158066，131158066，

3

又21158066，9?7?13?2?1638， ?1158066?2?9?72?13?101.

11580661638?707，7707，

4.2 弃九法（验证整数计算结果的方法）

我们由普通乘法的运算方法求出整数a，b的乘积是P，并令

a?an10?an?110b?bn10?bn?110nnnn?1?...?a0，0?ai?10 ?...?b0，0?bi?10， ?...?c0，0?ci?10，

n?1P?cn10?cn?110n?1如果(?ai)(?bj)与?ck对模9不同余，那么所求得的乘积是错误的.

特别的，在实际验算中，若ai，bj，ck中有9出现，则可去掉（因9?0(mod9)）. 例1 a=28997，b=39495，按普通计算方法算得a，b乘积是P=1145236515， 按照上述弃九法a?8(mod9)，b?3(mod9)，P?5(mod9). 但8?3与5对模9不同余，所以计算有误.

例2 若a=28997，b=39495，P=1145235615，那么P?a?b？ 解：按照上述弃九法，a?8(mod9)，b?3(mod9)，P?6(mod9).

虽然8?3与6对模9同余，但是由通常乘法计算得到a?b?1145236515， 故P?a?b不成立.

注：当使用弃九法时，得出的结果虽然是(?ai)(?bj)??ck(mod9)也还不能完全肯

定原计算是正确的.

4.3 同余性质的其他应用 例1 求7除4750的余数.

解：由47?(?2)1??2(mod7)，472?(?2)2?4(mod7)，475?(?2)5??1(mod7)，

4

?4750?(475)16?472?1?4?4(mod7)， 即4750除以7余数为4.

例2 试证：形如8k?7(k?N)的整数不能表为三个平方数之和.

证：假定N?8k?7?a2?b2?c2(a,b,c?Z)，则a2?b2?c2?7(mod8)，但这不可

能.因为对模8而论.每一个整数最小非负余数只能是0，1，2，3，4，5，6，7中的一个数.

而02?0(mod8)，12?1(mod8)，22?4(mod8)，32?1(mod8)，42?0(mod8)，

5?1(mod8)，6?4(mod8)，7?1(mod8).

222 因此，任一整数平方对模8必与0，1，4三个数之一同余，而从｛0，1，4｝

中任取三个数，其和都不可能与7对模8同余，所以对于任何整数a，b，

c都有a?b?c与7对模8不同余.

222 即形如8k?7(k?N)的整数不能表为三个平方数之和. 例3 试证：5353?3333能被10整除.

证：由已知条件有53?3(mod10)，532?32?9(mod10)，535?35?7(mod10)，

53?3?1(mod10)，

44 ?5353?(534)15?53?(34)15?3?1?3?3(mod10) 又

433?3(mod10)4，

33?3?9(mod10)22，

33?3?7(mod10)55，

33?3?1(mod10)，

?3333?(334)8?33?(34)8?3?1?3?3(mod10) ?5353?3333(mod10)，即10(5353?3333) 也就是说，5353?3333能被10整除.

例4 设a,b,c?N且6(a?b?c)，求证：6(a3?b3?c3)

5

证：对模6来说每一个整数的最小非负数余数为0，1，2，3，4，5

03?0(mod6)，13?1(mod6)，23?2(mod6)，33?3(mod6)，43?4(mod6)，

5?5(mod6)，即对任何整数k3，k3?k(mod6)

?a3?a(mod6)，b3?b(mod6)，c3?c(mod6) ?(a3?b3?c3)?(a?b?c)(mod6)

又(a?b?c)?0(mod6)?(a3?b3?c3)?0(mod6) 故6(a3?b3?c3)

例5 若(5,n)?1，证明n5?n能被30整除. 证：设n?N，n?k(mod6)则k?0,1,2,3,4,5

5555 由05?0(mod6)，1?1(mod6)，2?2(mod6)，4?4(mod6)，3?3(mod6)，

5?5(mod6)，

5 ?k5?k(mod6)即n5?k5?k?n(mod6)，6(n5?n) 同理可知5(n5?n) 又(5,6)?1 ?30(n5?n) 故n5?n能被30整除.

5 同余性质在数论中的应用：求简单同余式的解

5.1一次同余式、一次同余式解的概念

在代数里面，一个主要问题就是解代数方程.而同余性质在数论中的应用主要体现在同余在方程中的应用，也就是求同余式的解.

一次同余式的定义：若用f(x) 表示多项式anxn?an?1xn?1?...?a0，其中ai是整数，又设m是一个正整数，则f(x)?0(modm) 叫做模m的同余式.若an与0

6

对m不同余，则n叫做f(x)?0(modm)的次数.

定义：若a是使f(a)?0(modm)成立的一个整数，则x?a(modm) 叫做同余式f(x)?0(modm) 的一个解.

定理 一次同余式ax?b(modm),a与0对模m不同余,它有解充要条件是(a,m)b.[3]

5.2 孙子定理解一次同余式组

引例 今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何? 解:设x是所求物数，则依题意有，x?2(mod3),x?3(mod5),x?2(mod7) 孙子算经里介绍用下列方法求解 除数 余数 最小公倍数 衍数 3 5 7 2 3 2 5?7 3?5?7=105 7?3 3?5 乘率 2 1 1 各 总 35?2?2 21?1?3 15?1?2 140+63+30=233 233-2?105=23 答 数 最 小 答 数 由表格知，所求物数是23.

孙子定理：设m1,m2,?,mk是k个两两互质的正整数，m?m1m2...mk，m?miMi，

i?1,2,...,k,则同余式组x?b1(modm1), x?b2(modm2),... ,

112x?bk(modmk)的解是x?M1M1b1?MM2b2?...?M1kMkbk(modm),

其中M1iMi?1(modmi), i?1,2,...,k用表格形式概括如下

除数 余数 最小公倍数 衍数 m1 [4]

乘率 MM11 各 总 M1M1b1 M2M2b2 11答 数 b1 b2 M?m1m2...mkM1 M2 m2 1 2 kx??Mi?11iMibi(modm) ? mk ? bk ? Mk ? M1k 1? MkMkbk 7

例1 解同余式组x?b1(mod5), x?b2(mod6)，x?b3(mod7)，x?b4(mod11). 解：此时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.

解M1iMi?1(modmi), i?1,2,3,4 得M11?3, M12?1, M13?1, M14?1 即x?1386b1?385b2?330b3?210b4(mod2310).

例2 韩信点兵：有兵一队，若列成五行纵队，则末行一人，成六行纵队，则末

行五人，成七行纵队，则末行四人，成十一行纵队，则末行十人，求兵数？ 解:由题意，有x?1(mod5)，x?5(mod6)，x?4(mod7)，x?10(mod11)

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

5.3 简单高次同余式组f(x)?0(modmi), i?1,2,...,k及f(x)?0(modp?) ,p为

质数，??0的解数及解法的初步讨论

定理1 若m1,m2,?, mk是k个两两互质的正整数, m?m1m2...mk,则同余式

f(x)?0(modm)与同余式组f(x)?0(modmi),i?1,2,...,k等价.

若用Ti 表示f(x)?0(modmi),i?1,2,...,k,对模mi的解数, T表示

f(x)?0(modm)对模m [5]

的解数，则T?T1T2...Tk.

例1 解同余式f(x)?0(mod35)，f(x)?x4?2x3?8x?9.

解: 由定理1知f(x)?0(mod35)与同余式f(x)?0(mod5) , f(x)?0(mod7)等

价.

同余式f(x)?0(mod5)有两个解，即x?1,4(mod5) 同余式f(x)?0(mod7)有三个解，即x?3,5,6(mod7) 即f(x)?0(mod35)有六个解，即x?b1(mod5),x?b2(mod7) 由孙子定理有，x?21b1?15b2(mod35)

8

即得f(x)?0(mod35)的解为x?31,26,6,24,19,34(mod35).

定理2 设x?x1(modp),即x?x1?pt1, t1?0,?1,?2,...是f(x)?0(modp)的一解，并且

p不整除f1(x),( f1(x)是f(x)的导函数),则x?x1?pt1刚好给出

?f(x)?0(modp)，px?x(modp)??为质数，??0的一解x?x??p?t?,t??0,?1,?2,..., 即

, 其中x??x1(modp).[6]

例2 解同余式6x3?27x2?17x?20?0(mod30).

解: 由定理1知f(x)?0(mod30)与f(x)?0(mod2),f(x)?0(mod3),f(x)?0(mod5)等价.

显然，f(x)?0(mod2)有两解x?0,1(mod2)

f(x)?0(mod3)有一解x?2(mod3) f(x)?0(mod5)有三解x?0,1,2(mod5)

同余式f(x)?0(mod30)有六个解

即x?b1(mod2),x?b2(mod3),x?b3(mod5),b1?0,1；b2?2；b3?0,1,2 由孙子定理得x?15b1?10b2?6b3(mod30),以b1,b2,b3值分别代入，得

f(x)?0(mod30)全部解为x?20,2,26,5,11,17(mod30).

例3 解同余式f(x)?0(mod27)，f(x)?x4?7x?4.

解: f(x)?0(mod3)有一解x?1(mod3)，并且3不整除f1(1)，

以x?1?3t1 代入f(x)?0(mod9)得f(1)?3t1f1(1)?0(mod9) 但f(1)?3(mod9)，f1(1)?2(mod9)

即3?3t1?2?0(mod9)即2t1?1?0(mod3)

因此t1?1?3t2而x?1?3(1?3t2)?4?9t2是f(x)?0(mod9)的一解；

9

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