同余的概念与性质
同余：设m 是大于1的正整数，若用m 去除整数b a ,，所得余数相同，则称a 与b 关于模m 同余，记作)(mod m b a ≡，读作a 同余b 模m ；否则称a 与b 关于模m 不同余记作)(mod m b a ≠。

性质1：)(mod m b a ≡的充要条件是Z t mt b a ∈+=,，也即)(|b a m -。

性质2：同余关系满足下列规律：
（1）自反律：对任何模m 都有)(mod m a a ≡；
（2）对称律：若)(mod m b a ≡，则)(mod m a b ≡；
（3）传递律：若)(mod m b a ≡，)(mod m c b ≡，则若)(mod m c a ≡。

性质 3:若,,,2,1),(mod s i m b a i i =≡则
).(mod ),
(mod 21212121m b b b a a a m b b b a a a s s s s ≡+++≡++
推论： 设k 是整数，n 是正整数，
（1）若)(mod m c b a ≡+，则)(mod m b c a -≡。

（2）若)(mod m b a ≡，则)(mod m a mk a ≡+；)(mod m bk ak ≡；)(mod m b a n n ≡。

性质4：设)(x f 是系数全为整数的多项式，若)(mod m b a ≡，则 ))(mod ()(m b f a f ≡。

性质5：若)(mod m bd ad ≡，且1),(=m d ，则)(mod m b a ≡。

性质6：若)(mod m b a ≡，且m d b d a d |,|,|，则)(mod d m d b d a ≡。

性质7：若)(mod m b a ≡，且m m |1，则)(mod 1m b a ≡。

性质8：若)(mod i m b a ≡，s i ,,2,1 =，则
]),,,(mod[21s m m m b a ≡
这里],,,[21s m m m 表示s m m m ,,,21 的最小公倍数。

（算术基本定理）任何一个大于1的整数均可分解为素数的乘积，若不考虑素数相乘的前后顺序，则分解式是惟一的。

例如322224⨯⨯⨯=。

一个整数分解成素数的乘积时，其中有些素数可能重复出现，例如上面24的分解式中2出现了三次。

把分解式中相同的素数的积写成幂的形式，我们就可把大于1的整数n 写成 s s p p p n ααα 2121= ，0>i a ，s i ,,2,1 =。

上述式子称为a 的标准分解式。

定理3（欧拉定理）若1),(=m a ，则
)(mod 1)(m a
n ≡ϕ。

其中)1()1)(1()(211121121---=---s s p p p p p p n s αααϕ为n 的欧拉
函数
定理4（费尔马定理） 若p 是素数，则
)(mod p a a p
≡
例6：求使2n +1能被3整除的一切自然数n.
例7：设
101010=a ，问某星期一后的第a 天是星期几？
（2011年）证明：对任意整数4≥n ，存在一个n 次多项式
0111)(a x a x a x x f n n n ++++=--
具有如下性质：
（1）110,,,-n a a a 均为正整数；
（2）对任意正整数m ，及任意k （2≥k ）个互不相同的正整数k r r r ,,,21 ，均有
)()()()(21n r f r f r f m f ≠。