同余的性质

日期: 2023-11-09 18:39 查看: 10 次更新导出Word

**同余的性质**
从同余的概念和上面的探究, 我们不难发现, 同余式 $a \equiv b(\bmod n)$ 与等式 $a=b$ 有许多类似的性质.

类比等式的性质, 你能猜想同余式的一些性质吗? 试根据同余的概念, 探究同余的下列性质:

1. 若 $a \equiv b(\bmod n)$, 且 $c \equiv d(\bmod n)$, 则
   (1) $a+c \equiv b+d(\bmod n)$;
   (2) $a c \equiv b d(\bmod n)$;
   (3) $k a \equiv k b(\bmod n), k$ 为任意整数;
   (4) $a^m=b^m(\bmod n), m$ 为正整数.
2. 若 $a b \equiv a c(\bmod n)$, 且 $(a, n)=1$, 则 $b \equiv c(\bmod n)$.

我们给出性质 1(1) 及性质 2 的证明, 余下的请同学们自己证明:
$1^{\circ}$ 证明：因为 $a \equiv b(\bmod n), c \equiv d(\bmod n)$,
所以 $n|a-b, n| c-d$,
因此 $n \mid c-d+a-b$, 即 $n \mid(a+c)-(b+d)$.
所以 $a+c=b+d(\bmod n)$.
性质 1 说明, 类似整数集中两个等式两端对应加、减、乘仍得到等式, 同余式两端对应加、减、乘仍然是同余的.
$2^{\circ}$ 证明: 因为 $(a, n)=1$,
所以存在一对整数 $k, l$, 使得

$$
a k+n l=1 .
$$

因此 $n \mid n l=1-a k$, 即

$$
a k \equiv 1(\bmod n) .
$$

又因为 $a b \equiv a c(\bmod n)$,
所以 $k a b \equiv k a c(\bmod n)$. 而 $k a \equiv 1(\bmod n)$,
因此 $b \equiv c(\bmod n)$.
性质 2 可以看作是同余意义下的消去律, 消去律的前提是 $a$ 与 $n$ 必须互素, 否则结论不一定成立.
利用同余的这些性质, 我们可以简化数论中的许多问题.
先看星期几问题. 如果今天为星期天, 过 $n$ 天后的今天是星期几? 这个问题并不难回答, 我们只需对 $n$ 和 7 用带余除法, 由余数即可确定. 但是, 有时直接应用带余除法求余数是困难的, 特别是当被除数较大时, 如下例.

**例 1** 今天为星期日, 过 $2004^{2004}$ 天后的今天是星期几?
分析: $2004^{2004}$ 这个数很大, 我们很难直接判断 7 除 $2004^{2004}$ 的余数是几. 现在, 我们想办法把 $2004^{2004}$ 变小. 一个自然的考虑是 7 除底数 2004 的余数是几, 利用这个余数替换底数 2004 , 然后降次, 反复进行这个过程, 直至去掉指数.
解: 因为 $2004=7 \times 286+2$, 所以 $2004 \equiv 2(\bmod 7)$.
由同余的性质, 有

$$
2004^{2004} \equiv 2^{2004}(\bmod 7),
$$

而 $2^{2004}=8^{668}$, 所以 $2^{2004} \equiv 8^{668}(\bmod 7)$.
又因为 $8 \equiv 1(\bmod 7)$, 所以 $8^{668} \equiv 1^{668}=1(\bmod 7)$.
因此 $2004^{2004} \equiv 1(\bmod 7)$, 即 7 除 $2004^{2004}$ 的余数为 1 , 所以过 $2004^{2004}$ 天后的今天是星期一.
再看一个整除问题的例子.

**例 2** 证明: $17 \mid 19^{1000}-1$.
分析: 类似例 1 , 我们想办法把 $19^{1000}$ 变小, 用 17 除底数 19 的余数替换底数 19 , 然后降次, 反复进行这个过程, 直至去掉指数.
证明: 要证 $17 \mid 19^{1000}-1$, 只需证 $19^{1000} \equiv 1(\bmod 17)$,因为 $19 \equiv 2(\bmod 17)$, 所以

$$
19^{1000} \equiv 2^{1000}=16^{250}(\bmod 17) .
$$

又由于 $16 \equiv-1(\bmod 17)$, 故 $16^{250} \equiv(-1)^{250}=1(\bmod 17)$.因此 $17 \mid 19^{1000}-1$.

上一篇：同余

下一篇：剩余类及其运算

知识库是科数网倾心打造的大型数学知识网站，欢迎各位老师、数学爱好者加入,联系微信 18155261033，制作不易，也欢迎赞助本站。