完系、简系、剩余类(讲稿)

2014年希望联盟数学竞赛(兰州)

有无穷多个，但常用的是“最小简化剩余系”，即由1，2， ，m－1中与m互质的那些数组成的数组.

说明：由于任何整数都属于模m的某一剩余类，所以，在研究某些整数性质时，选取适当的(模)m，然后在模m的每个剩余类中取一个“代表数”(即组成一个完全剩余系)，当弄清了这些代表数的性质后，就可弄清对应的剩余类中所有数的性质，进而弄清全体整数的性质，这就是引入剩余类和完全剩余系的目的.

例1、设n为偶数，a1, a2, , an与b1, b2, , bn均为模n的完全剩余系，试证：a1＋b1, a2＋b2, , an＋bn不是模的完全剩余系.

证明：假设a1＋b1, a2＋b2, , an＋bn是模的完全剩余系. ∴ (ai bi) 1+2+i 1nnn+n n(n 1)n (modn) 22nn(n 1)nn (modn)，同理有： bi (modn) ∵a1, a2, , an也是模的完全剩余系. ∴ ai i

i 1i 1i 1222

(ai bi) n 0(modn)，∴n|2矛盾！故假设不成立，从而原命题成立.

i 1nn

例2、设m＞1, (a, m)＝1，b∈Z, 求和： {

i 0m 1a i b, 其中{x}为x的小数部分. m

解：∵i取遍模m的完系，令xi＝a·i＋b，则也取遍模m的完系.

m 1km 1ka i bm 1xi11m 1} {} {} m(m 1) 故 {

i 0i 0mk 0mk 0mmm22m 1

总结：若a1, a2, , am是模m的一个完系，则①a1＋a2＋ ＋am≡1＋2＋ ＋m (mod m)；

②a1·a2· ·am≡1·2· ·m (mod m)； ③(a1)n＋(a2)n＋ ＋(am)n≡1n＋2n＋ ＋mn (mod m).

例3、已知m, n为正整数, 且m为奇数, (m, 2n－1)＝1. 证明：m| k

k 1mn.

证明：∵1, 2, , m构成模m的完系, (m, 2)＝1，∴2, 4, , 2m也构成模m的完系.

∴ (2k)

k 1mn k(modm)，即(2 1) k 0(modm). ∵(m, 2－1)＝1，∴m| kn得证. nnnnmmmk 1k 1k 1

例4、求八个整数n1, n2, , n8满足：对每个整数k (－2014＜k＜2014)，有八个整数a1, a2, , an∈{ 1, 0, 1},

使得k＝a1n1＋a2n2＋ ＋a8n8

解：令G＝{k| k＝a1＋a2·2＋a3·32＋ ＋an+1·3n，ai∈{ 1, 0, 1}，i＝1，2， ，n＋1}.

3n+1－12n显然maxG＝1＋3＋3＋ ＋3＝记为H)，minG＝－1－3－32＋ －3n＝－H. 2

n+1且G中的元素个数有3＝2H＋1个， 又∵G中任意两数之差的绝对值不超过2H，

∴G中的数对模2H＋1不同余，∴G的元素恰好是模2H＋1的一个绝对值最小的完系，

于是凡满足－H k H的任意整数都属于G，且可唯一地表示为a1＋a2·2＋a3·32＋ ＋an+1·3n形式，

当n＝7时，H＝3208＞2014，而n＝6时，H＝1043＜2014，故n1＝1，n2＝3， ，n8＝37为所求.

1111a例5、已知p为大于3的质数，且＋＋＋ ＋，a，b∈N*. (a, b)＝1，证明：pa. 123(p－1)b

证明：对于不超过p 1的自然数k，由于(k, p)＝1，所以存在唯一的不超过p 1的自然数x，满足kx 1(modp)而且，当k＝1或p 1有x＝1或p 1，当2 k p 2时，有2 x p 2,x k，

故当k取遍1，2， ，p 1时，x也取遍1，2， ，p 1，因为(p,(p 1)!) 1,由kx 1(modp)可得到