成都七中高一竞赛数论专题
2.同余
设m为正整数,若整数a和b被m除的余数相同,则称a和b对模m同余,记做a?b(modm).
a?b(modm)?m|a?b?b?a?mq,q?Z.
设m是一个给定的正整数,Cr?{x?Z|x?r(modm)},r?0,1,2,模m的同余类(或剩余类).显然C0,C1,C2,
在模m的同余类C0,C1,C2,,m?1.我们称C0,C1,C2,,Cm?1为
,Cm?1构成整数集Z的一个划分.
,Cm?1中各取一数aj?Cj,j?0,1,,m?1,这m个数a0,a1,a2,,am?1称
为模m的一个完全剩余系(简称完系).最常用的完系0,1,2,
,m?1称为模m的非负最小完全剩余系.
如果一个模m的同余类里面的数与m互素,就把它叫做一个与模m互素的同余类,在与模m互素的全部同余类中,各取一数所组成的集叫做模m的一个简系.模m的一个简系的元素个数记为欧拉函数?(m). 欧拉函数?(m)是一个定义在正整数集上的函数,?(m)的值等于0,1,2,
1.证明ac?bc(modm)?a?b(mod,m?1中与m互素的数的个数.
m). (m,c)(特别地若(m,c)?1,则ac?bc(modm)?a?b(modm).
2若m?c,则ac?bc(modc)?a?b(modc).)
2
2.设
p是素数,k?1,证明?(pk)?pk?1(p?1).
3.(Euler定理)设(a,m)?1,证明：a(Fermat小定理)设
4.(Wilson定理)设
?(m)?1(modm).
p一个素数,对任意的整数a ,证明ap?a(modp).若(a,p)?1,则ap?1?1(modp).
p是素数,r1,r2,,rp?1是模p的一个简系,证明r1r2rp?1??1(modp).
特别地,有(p?1)!??1(modp).
5.(Lucas定理)设
p是一个素数,将m和n写成p进制数：
m?akpk?ak?1pk?1?n?bkp?bk?1pkk?1?a1p?a0?b1p?b0?
其中0?ai,bi?p(i?0,1,2,
6.已知正整数n?2,a1,a2,bi,k). 证明：C??Ca(modp). inmi?0k,an为整数,且其中任何一个均不为2017n?1的倍数.证明：存在不全为零的整数
??nan为2017n的倍数,其中|?i|?2017,i?1,2,,n.
?1,?2,
,?n,使得?1a1??2a2?2m?1?1p7.已知素数p?6k?1(k?N,k?1),证明：为整数,其中m?2?1.
127m*
8.设素数p?3,证明
(p?1)!(p?1)!??12?(p?1)!?0(modp2). p?1
高一竞赛数论专题
2.同余解答
设m为正整数,若整数a和b被m除的余数相同,则称a和b对模m同余,记做a?b(modm).
a?b(modm)?m|a?b?b?a?mq,q?Z.
设m是一个给定的正整数,Cr?{x?Z|x?r(modm)},r?0,1,2,模m的同余类(或剩余类).显然C0,C1,C2,
在模m的同余类C0,C1,C2,,m?1.我们称C0,C1,C2,,Cm?1为
,Cm?1构成整数集Z的一个划分.
,Cm?1中各取一数aj?Cj,j?0,1,,m?1,这m个数a0,a1,a2,,am?1称
为模m的一个完全剩余系(简称完系).最常用的完系0,1,2,
,m?1称为模m的非负最小完全剩余系.
如果一个模m的同余类里面的数与m互素,就把它叫做一个与模m互素的同余类,在与模m互素的全部同余类中,各取一数所组成的集叫做模m的一个简系.模m的一个简系的元素个数记为欧拉函数?(m). 欧拉函数?(m)是一个定义在正整数集上的函数,?(m)的值等于0,1,2,
1.证明ac?bc(modm)?a?b(mod,m?1中与m互素的数的个数.
m). (m,c)(特别地若(m,c)?1,则ac?bc(modm)?a?b(modm).
2若m?c,则ac?bc(modc)?a?b(modc).)
2
证明：ac?bc(modm)?m|c(a?b)?c(a?b)?mq,q?Z. 因为
mccmcm(a?b). ?Z,?Z.所以c(a?b)?mq?(a?b)?q.即
(m,c)(m,c)(m,c)(m,c)(m,c)(m,c)mccmmm,)?1.所以(a?b)?q?(a?b)?a?b(mod).(m,c)(m,c)(m,c)(m,c)(m,c)(m,c)
因为(即ac?bc(modm)?a?b(mod 2.设
m). (m,c)p是素数,k?1,证明?(pk)?pk?1(p?1).
相关推荐：
loading