同余

1. 概述

于 初等数论 中, 同余 按一个非零整数模数比较两个 整数 的余数. 两个整数模 同余, 当且仅当它们的差能被 整除; 这一关系把 划分为 剩余类, 并构成 整数模 加法群 与 整数模 环 的基础.

2. 定义

定义 1 (同余)

设 且 . 称 与 模 同余, 当：

记号 2 (同余)

与 模 同余 记为 ; 若二者模 不同余, 则记为 .

注记 3 (模数的符号)

由 同余 的定义, 模 同余与模 同余是同一关系, 因此讨论同余时常取正模数.

3. 例子

例子 4 (初步例子)

• , 因为 ;
• , 因为 ;
• , 因为 .

4. 相关性质

命题 5 (同余是等价关系)

设 且 . 模 同余 是 上的 等价关系, 即对任意 ：

1. ;
2. 若 , 则 ;
3. 若 且 , 则 .

证明 6 (同余是等价关系)

1. 因 , 有 .
2. 若 , 则 , 故 .
3. 若 且 , 则由 整除的基本性质 的 (4), 有 , 故 .
   

命题 7 (同余与整数运算相容)

设 且 . 若 且 , 则：

1. 且 ;
2. ;
3. 对任意 , .

证明 8 (同余与整数运算相容)

1. 因 且 , 由 整除的基本性质 的 (4), 整除 , 即 .
2. 由：

以及 整除的基本性质 的 (4), 得 .
3. 对 使用 数学归纳法. 当 时结论成立; 若 , 则由第 (2) 条得 .

命题 9 (同余的余数判据)

设 , . 则 当且仅当 与 除以 所得的 余数 相同.

证明 10 (同余的余数判据)

由 整数上的带余除法, 写：

其中 .

充分性 ( )

若 , 则 , 从而 . 又因 , 只能有 , 即 .

必要性 ( )

若 , 则 , 故 , 即 .

5. 相关概念

• 整除
• 余数
• 剩余类
• 完全剩余系
• 线性同余方程
• 同余方程组
• 二次剩余
• 整数模 加法群
• 整数模 环

6. 术语翻译

中文	英文
同余	congruence
模 同余	congruent modulo

初等数论