第二讲 同余(数论复赛辅导)(2)

包头市数学联赛辅导 复赛数论初步选讲----------北重三中 樊增平

同余组定义：设fj(x)为整系数多项式（1?j?k），我们把含有x的一组同余式fj(x)?0(modmj)（1?j?k）称为同余方程组。特别地，当fj(x)均为x的一次整系数多项式时，该同余方程组称为一次同余方程组.若整数c同时满足：fj(c)?0(modmj)，则剩余类Mc?{x|x?Z,x?c(modm)}1?j?k，（其中m?[m1,m2,?,mk]）称为同余方程组的一个解，记作x?c(modm).

定理3：（中国剩余定理，也称孙子定理）设m1,m2,?,mk是两两互素的正整数，那么对于任意整数

a1,a2,?,ak，一次同余方程组x?aj(modmj)，1?j?k有唯一解：

x?M1N1a1?M2N2a2???MkNkak(modm)

其中 m?m1m2?mk，Mi?m(1?i?k)， Nj满足MjNj?1(modmj)，1?j?k. mi【例题分析】

【欧拉定理及其应用举例】

1.设(91,ab)?1，求证：91|(a12?b12)。

,a)?1，从而(7,a)?1,(13,a)?1，但是证明：因为91?7?13，故由(91,ab)?1知(91?(7)?6,?(13)?12，故由欧拉定理得：a12?(a6)2?12?1(mod7)，a12?1(mod13)，从而a12?1(mod91)；同理，b12?1(mod91)。

于是，a12?b12?1?1?0(mod91)，即91|(a12?b12)。

1012、设?n,10??1,求证n与n的末三位数相同.

101证明:由条件只需证明 1000n也即证明 n100?n，即: n101?n?mod1000??????1?

?1?mod1000??????2?

100事实上，由 ?n,125??1，??125??100，利用欧拉定理有 n再由n是奇数知: 8?1?mod125??????3?

n?1,n21002?进而 n100?1?mod8??????4? ??n?1?1????50由(3)、（4），并注意到?125,8??1可得（2），于是（1）成立. 【Fetmat小定理及其应用举例】 3．求证：对于任意整数x，求证 证明：令f(x)?

15137x?x?x 是整数. 531515137x?x?x，则只需证15f(x)?3x5?5x3?7x是15的倍数即可。 53156

包头市数学联赛辅导 复赛数论初步选讲----------北重三中 樊增平

由3，5是素数及Fetmat小定理得x5?x(mod5)，x3?x(mod3)，则

3x5?3x(mod5)，5x3?0(mod5)，7x?7x(mod5)

于是有 3x5?5x3?7x?3x?0?7x?10x?0(mod5)； 同理 3x5?5x3?7x?5x?7x?12x?0(mod3)

而（3，5）=1，故3x?5x?7x?0(mod15)，即15f(x)是15的倍数，所以f(x)是整数. 4．求证：2730|n13?n（n为任意整数）。 证明：令f(n)?n1353?n，则f(n)?n(n?1)(n?1)(n2?n?1)(n2?n?1)(n6?1)；

所以f(n)含有因式n7?n,n5?n,n3?n,n2?n

由Fetmat小定理，知13|n13?n,7|n7?n,5|n5?n,3|n3?n,2|n2?n 又13，7，5，3，2两两互素，所以2730=13?7?5?3?2能整除n13?n。

5．设a,b,c是直角三角形的三边长，且a,b,c都是整数，求证：abc可以被30整除。 证明：不妨设c是直角三角形的斜边长，则c?a?b。

①若2 a，2 b，2 c，则c2?a2?b2?1?1?0(mod2)，这与c2?1(mod2) 矛盾！所以2|abc. ②若3 a，3 b，3 c，因为(3k?1)?1(mod3)，则a?b?1?1?2(mod3)，这与c?1(mod3)矛盾！从而3|abc.

③若 5 a，5 b，5 c，因为(5k?1)?1(mod5)，(5k?2)??1(mod5)，

2所以a?b??2或0(mod5)，这与c??1(mod5)矛盾！从而5|abc.

22222222222又(2,3,5)=1，所以30|abc. 【中国剩余定理应用举例】

6．证明：对于任意给定的正整数n，均有连续n个正整数，其中每一个都有大于1的平方因子。 证明：由于素数有无穷多个，故我们可以取n个互不相同的素数p1,p2,?,pn，而考虑同余组

x??i(modp2),i?1,2,?,n ①

因为p1,p2,?,pn显然是两两互素的，故由中国剩余定理知，上述同余组有正整数解。于是，连续n个数x?1,x?2,?,x?n分别被平方数p1,p2,?,pn整除。

注：本题的解法体现了中国剩余定理的一个基本功效，它常常能将“找连续n个正整数具有某种性质”的

7

222222包头市数学联赛辅导 复赛数论初步选讲----------北重三中 樊增平

问题转化为“找n个两两互素的数具有某种性质”，而后者往往是比较容易解决的。 7．证明：对于任意给定的正整数n，均有连续n个正整数，其中每一个都不是幂数。

分析：我们来证明，存在连续n个正整数，其中每一个数都至少有一个素因子，在这个数的标准分解中仅出现一次，从而这个数不是幂数。

证明：取n个互不相同的素数p1,p2,?,pn，考虑同余组x??i(modpi),i?1,2,?,n.

因为p1,p2,?,pn，显然是两两互素的，故由中国剩余定理知，上述同余组有正整数解，pi|(x?i). 同理知，同余组x??pi-i?(modpi2)有整数解，即x?i?pi(modpi2)，故pi2 (x?i)，即pi在(x?i)的标准分解中恰好出现一次，所以 x?1,x?2,?,x?n都不是幂数.

8． 设k是给定的偶数，n?N，证明：存在整数x,y使得:(x,n)?(y,n)?1，且x?y?k(modn). 证明：（1）当n为素数幂p?时，能够证明，存在x,y使p xy且x?y?k.

实际上，若p?2，则n=2，此时可取x?1,y?k?1.显然2 xy=k-1，且x?y?k. 若p?2，则x?1,y?k?1与x?2,y?k?2中有一对满足要求. (2) 一般情形下，设n?p11p22?prr,i?1,2,,?,r是n的一个标准分解.

上面已经证明，对每个pi存在整数xi,yi使得pi xiyi且xi?yi?k(i?1,2,?r). 由中国剩余定理知，

同余式x?xi(modpii)(i?1,2,?,r) ①有解x， 同余式y?yi(modpii)(i?1,2,?,r) ②有解y.

现不难验证解x,y符合问题中的要求：因pi xiyi，故pi xy(i?1,2,?r)，于是(xy,n)?1. 又由①②知x?y?xi?yi(modpii)(i?1,2,?,r)，故x?y?k(modn).

?aaa???? 8

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第二讲 同余(数论复赛辅导)(2)在线全文阅读。