奥数余数相关.pdfVIP

余数相关

余数

定义

a÷b（b≠0）,余数为c,记作amodb=c

可加性

a与b的和除以c的余数于a，b分别除以c的余数之和

（这个和大于c时，于这个和再除以c的余数)

(a+b)modc=(amodc)+(bmodc)

可减性

a与b的差除以c的余数于a，b分别除以c的余数之差

（这个和为负数时，于这个差再加上除数c)

(a-b)modc=(amodc)-(bmodc)

可乘性

a与b的乘职除以c的余数于a，b分别除以c的余数之积

（这个积大于c时，于这个积再除以c的余数)

(a×b)modc=(amodc)×(bmodc)

同余

规则

定义

a÷m与b÷m的余数相同，称a、b对于模m同余。

记作a≡b(modm)

同余定理

m|(a-b)，则a≡b(modm)

必要性

a≡b(modm)，则（a-b)|m

传递性

a≡b(modm),b≡c(modm),则a≡c(modm)

和差性

a≡b(modm),c≡d(modm),则a±c≡b±d(modm)

相乘性

a≡b(modm),c≡d(modm),则a×c≡b×d(modm)

乘方性

a≡b(modm),则

同倍性

a≡b(modm),则a×c≡b×c(modm×c)