《用同余理论解决整除问题》由会员分享，可在线阅读，更多相关《用同余理论解决整除问题（11页珍藏版）》请在金锄头文库上搜索。
1、用同余理论解决整除问题重庆沙坪坝杨公桥小学 蒋焘摘 要：在数的整除理论中，经常要判断一个数能否被另一个数整除。虽然用初等方法也能证 明判断的正确性，但其技巧性很强,而技巧性的东西是一时难于捕捉到的。如果用同余理论解决这类 问题，就简捷明了。本文主要利用同余性质给出一些整除问题的判别方法并阐述同余理论在整除问题 中的一些应用。关键词：同余;整除;判别方法1 同余的基本概念和性质整除性的证明被公认为是中学数学、特别是数学竞赛的难题之一，但用同余思想方 法指导解决整除性问题就要容易和易于掌握得多。本文主要阐述同余理论在整除问题中 的一些应用。定义1. 1设a,b是任意两个整数，其中bHO,如果存在一
2、个整数q使得等式a = bq 成立，我们就说b能整除a或a能被b整除，记作b|a，否则记作b* a。定义1. 2给定一个正整数m，把它叫做模。如果用m去除任意两个整数a和b所得 的余数相同，我们就说a，b对模m同余，记做a三b(modm)。如果余数不相同，我们就 说a，b对模m不同余，记做a丰b(modm)。定理1.1a三b (modm)的充分必要条件是m 1 a - b。性质 1.1a 三 a (mod m)。性质 1.2若 a 三 b (mod m)，贝U b 三 a (mod m)。性质 1.3若 a 三 b(modm)，b 三 c(modm)，贝U a 三 c(modm)。性质 1.4
3、若 a 三 b (mod m )，a 三 b (mod m)，则 a 土 a 三 b 土 b (mod m)。1 1 2 2 1 2 1 2若 a + b 三 c(mod m)，贝U a 三 c - b(mod m)。性质 1.5若 a 三 b (mod m )，a 三 b (mod m )，1 1 2 2则a a三bb (modm)， a c三bc(modm)， c为任意整数。1 2 1 2 1 1性质 1.6性质 1.7若 a 三 b(modm),且 a = a d,b = bd,(d,m) = 1，贝U a 三 b (modm)。1 1 1 1若 a 三 b(modm), k o，贝U
4、ak 三 bk(modmk)。若 a 三 b(modm), d为a,b及m的任一正公因数，则a三-(mod-)。 d d d 性质1.8同余式组a三b(modm ), i=l,2,k,同时成立的充要条件是ia 三 b (mod m , m , , m )。12k性质 1.9 若a 三b(modm ), d|m,d 0，则 a 三b(modd)。定理1.213设f (x)= a xn + a xn-1 + + a是整系数多项式，nn-10若a 三 B (modm)，则 f G)三 f(B)(modm)。定理1.311 (Euler)设m是大于1的整数，(a,m)= 1，则a咲炕三1(modm)。
5、定理 1.414若 m 1,(d, m)= 1,则存在 c e Z , 使 ca 三 1(modm) 我们称c是a对模m的逆，记作a-1。2 利用同余性质给出一些整除的判别法例 2 . 1 任何一个整数 a = a a a a，其中 0 a 10,a 丰 0 i = 0,1,2,n.则n n -11 0i n2、la o 2、5la0证法一设 a = a a a x 10 + an n -110/ 21 a a a x10n n -1121 a a a x 10 + a o 21 an n -1100故 21a o 21a 0 同理可证 5 | a o 5 | a0 。证法二 设f (x)=
6、a xn + a xn-1 + + a是整系数多项式。nn-10V 10三0 (mod2 )由定理 1.2 得 f (10)三 f (0)(mod2 )即 a 三 a (mod2 )0则 2|a o 2|a0对模 m=5 的情形同理论证。例 2. 2 a = a an n-1a a a，其中 0 a 10,a 丰 0 , i = 0,1,2,2 1 0in, n. 则4、25|a o 4、25|a a10证明 a = a an n-1又 100 三 0 (mod4 )a x 100 + a a210a a a x100 三 a an n -12n n -1于是 a 手.a a (mod4 )1
7、 0a x 0(mod4 )2故 4 | a o 4 | a a10对模 m=25 的情形同理论证。例 2.3 a = a a a a a，其中 0 a 10, a 丰 0, i = 0,1,2,n n-12 1 0in, n.则 8、25l a o 8、25l a a a210证明 T a = a a a x 1000 + a a an n-13又 1000 三 0 (mod8)210a a a x1000 三 a an n -13n n -1于是 a 三a.a a (mod8)2 1 0a x 0 (mod8 )3故 8| a o 8| a a a2 1 0对模 m=125 的情形同理论证
8、。例 2.4任何一个整数a = a a a a，其中0 a 10,a丰0, n n-11 0in证法一a=aaaan n-11 0+ a xnn -1=a x(9q +1)+ a x(9q+1)+n nn -1n -1=a x10n + a x10n-i + a x10 + ann -110=a x(9 + 1)n + a x(9 +.l)n-1 + a x(9 +1)+ a1 0 + a x (9 +1)+ a 10证法二= 9 q + a + a +nn-1= 9 q +a ii=0n31 a o 31 乙 aii=0n同理可证91 a o 91 a。 i 设 f (x) = a xn +
9、 a xn-1 +nn -1+ a是整系数多项式。0V 10 三 1(mod3)由定理12得f (10)三f (1)(mod3) 又 f (10 )= a f (1)=2 ai所以a三工a (mod3)即31 a o 31工ii =0ni =0同理可证91 a o 91乙a。ii = 0a a，其中 0 a 10,a 丰 0，则10innn-1例 2.5 任何一个整数 a = a a 11| a o11| 2n (-1)iai证明 V各位数字都是9的偶数位整数都能被11整除，且形如10001的偶数位整数也能被 11 整除。若记整数a = a a a a为10nn-1a = a x 10i (1
10、)n + (1)n + a x 10-1 ( 1)n-1 + ( 1)n-1 + + a x 10 ( 1) + ( 1) + a nn -110=a x10 ( 1)n + a x10ni ( 1)ni + a X 10(-1)+工(1)iann11ii=0前n项中的每一项都有偶数位因数99 9或10001,都能被11整除。a。i因此，若工(1)ia能被11整除，a就能被11整除；若11|a,则11| 艺(1)ii=0例 2.6 正整数 a = a xlOOOn + a x 1000n-1 + + a x 1000 + an1100 a 1000,a 主 0,i = 0,1,2, ,n.则
11、11、13l a o 1T、13I 工(1)iainii=0证明 设f (x)= a xn + a.xn-1 + + a是整系数多项式。nn 10 1000 三1(mod11).由定理12得f (1000)三f (1)(mod11) 又 f(1000)= af(1)=2n (1)iai所以 a 三工1)a (mod11)i故 111 a o 111 工(1) ai对模 m=7、 13 的情形同理论证。例2.7 12 a = a xlOOOn + a x 1000n-1 + + a x 1000 + ann1100 a 1000, a 主 0, i = 0,1,2, n.则 37 I a o 3
12、7 J .工 ainii=0证明 设f (x)= a xn + a xn-i + ax + a是整系数多项式。nn-110V 1000 三 l(mod37).由定理 1.2 得 f (1000)三 f (1)(mod37 )艮卩 a 三 a + a + a =工 a (mod37)n n -10 i.i=0故 37 I a o 371 ai例2. 8 设正整数a = a x 100n + a x 100n-1 + + a x 100 + ann -1100 a 0 时，T64三7 (mod57)64n 三 7n (mod57)于是 7 n+2 +82n+1=49 - 7 n + 64 n - 8三 7n(49 + 8)三 0 (mod57 )故
