简化剩余系

1. 概述

于 初等数论 中, 简化剩余系 只保留模 的 可逆剩余类 的代表元. 它是 Euler 函数 与 Euler 定理 的自然载体.

2. 定义

定义 1 (简化剩余系)

设 . 若 有限集 满足：

1. 对任意 , 均有 ;
2. 对任意满足 的 , 存在唯一的 使 .

则称 为模 的一个 简化剩余系.

3. 例子

例子 2 (模 的简化剩余系)

集合 是模 的一个 简化剩余系. 集合 也是模 的一个简化剩余系.

4. 相关性质

命题 3 (简化剩余系的基数)

设 , 是模 的 简化剩余系. 则：

其中 是 Euler 函数.

证明 4 (简化剩余系的基数)

集合 是模 的 完全剩余系. 其中与 互素 的元素恰为每个可逆 剩余类 的一个代表元, 其个数按 Euler 函数 的定义等于 . 任意 简化剩余系 也从这些剩余类中各取一个代表元, 故其基数相同.

命题 5 (互素乘法置换简化剩余系)

设 , 是模 的 简化剩余系, 且 . 则：

关于模 仍是一个简化剩余系; 换言之, 乘以 仅 置换 了 所代表的 剩余类.

证明 6 (互素乘法置换简化剩余系)

对任意 , 由 及 互素性对乘积的保持, 有 . 若 , 则由 同余式中的互素消去律 得 , 从而 . 因此 给出全部可逆 剩余类 的不同代表元, 是模 的 简化剩余系.

5. 相关概念

• 完全剩余系
• 剩余类
• 模逆元
• Euler 函数

6. 术语翻译

中文	英文
简化剩余系	reduced residue system

初等数论