同余 #数论，数学

同余

2020-07-03 22:09:00

若两数除以$c$的余数相等，则称$a,b$膜$c$同余，记做$a \equiv b (mod \ c)$

1.自反性:$若a \equiv a (mod \ m)$

2.对称性:$若a \equiv b (mod \ m), 则b \equiv a (mod \ m)$

3.传递性:$若a \equiv b (mod \ m), b \equiv c (mod \ m), 则a \equiv c (mod \ m)$

4.同加性:$若a \equiv b (mod \ m),则a + c\equiv b+c (mod \ m)$

5.同乘性:$若a \equiv b (mod \ m),则若a \times c \equiv b \times c (mod \ m)$

$若a \equiv b (mod \ m), c \equiv d (mod \ m), 则a \times c\equiv b \times d (mod \ m)$

6.同幂性:$若a \equiv b (mod \ m), 则a^n \equiv b^n (mod \ m)$

7.推论1：$a \times b \ mod \ k = (a \ mod \ k) \times (b \ mod \ k) mod \ k$

8.推论2：若$a \equiv b \ (mod \ c) \ d \mid c $ 则 $a \equiv b \ (mod \ d)$

试证明$8888^{2222} + 7777^{3333} \equiv 0 \ (mod \ 37)$

证明:

$8888^{2222} + 7777^{3333}$

$\equiv 8^{2222} + 7^{3333} \ (mod \ 37)$

$\equiv 64^{1111} + 343^{1111} \ (mod \ 37)$

$\equiv (-10)^{1111} + 10^{1111} \ (mod \ 37)$

$\equiv 0 \ (mod \ 37)$

同余