定义

剩余类

由前面的性质知，对给定的模 同余类和 Euler 函数 - 图1 整数的同余关系是一个等价关系，因此全体整数可按对模 同余类和 Euler 函数 - 图2 是否同余分为若干个两两不相交的集合，使得在同一个集合中的任意两个数对模 同余类和 Euler 函数 - 图3 一定同余，而属于不同集合的两个数对模 同余类和 Euler 函数 - 图4 一定不同余。每一个这样的集合称为是模 同余类和 Euler 函数 - 图5 的同余类，或模 同余类和 Euler 函数 - 图6 的剩余类。我们以 同余类和 Euler 函数 - 图7 表示 同余类和 Euler 函数 - 图8 所属的模 同余类和 Euler 函数 - 图9 的同余类。

完全剩余系

一组数 同余类和 Euler 函数 - 图10 如果对任意的 同余类和 Euler 函数 - 图11 有且仅有一个 同余类和 Euler 函数 - 图12 是 同余类和 Euler 函数 - 图13 对模 同余类和 Euler 函数 - 图14 的剩余，即 同余类和 Euler 函数 - 图15 同余于 同余类和 Euler 函数 - 图16 模 同余类和 Euler 函数 - 图17 则这组数组成的集合称为是模 同余类和 Euler 函数 - 图18 的完全剩余系。根据其中元素可有以下几种特殊剩余系，模 同余类和 Euler 函数 - 图19 的最小非负完全剩余系，最小正完全剩余系，绝对值最小完全剩余系，最大非正完全剩余系，最大负完全剩余系。

Euler 函数

如果 同余类和 Euler 函数 - 图20 则模 同余类和 Euler 函数 - 图21 的同余类 同余类和 Euler 函数 - 图22 称为是模 同余类和 Euler 函数 - 图23 的既约（或互素）同余类，模 同余类和 Euler 函数 - 图24 的所有既约同余类的个数记作 同余类和 Euler 函数 - 图25 称为 Euler 函数。

既约剩余系

一组数 同余类和 Euler 函数 - 图26 如果 同余类和 Euler 函数 - 图27 且对任意的 同余类和 Euler 函数 - 图28 有且仅有一个 同余类和 Euler 函数 - 图29 是 同余类和 Euler 函数 - 图30 模 同余类和 Euler 函数 - 图31 的剩余，即 同余类和 Euler 函数 - 图32 同余于 同余类和 Euler 函数 - 图33 模 同余类和 Euler 函数 - 图34 则这组数称为是模 同余类和 Euler 函数 - 图35 的既约（或互素）剩余系。

定理

  1. 同余类和 Euler 函数 - 图36
  2. 同余类和 Euler 函数 - 图37 的充要条件是 同余类和 Euler 函数 - 图38
  3. 对任意的 同余类和 Euler 函数 - 图39 要么 同余类和 Euler 函数 - 图40 要么 同余类和 Euler 函数 - 图41 与 同余类和 Euler 函数 - 图42 的交集为空集
  4. 对给定的模 同余类和 Euler 函数 - 图43 有且恰有 同余类和 Euler 函数 - 图44 个不同的模 同余类和 Euler 函数 - 图45 的同余类，它们是同余类和 Euler 函数 - 图46
  5. 在任意取定的 同余类和 Euler 函数 - 图47 个数中，必有两个数对模 同余类和 Euler 函数 - 图48 同余
  6. 存在 同余类和 Euler 函数 - 图49 个数两两对模 同余类和 Euler 函数 - 图50 不同余
  7. 设 同余类和 Euler 函数 - 图51 那么，对任意的 同余类和 Euler 函数 - 图52 有 同余类和 Euler 函数 - 图53 等号当且仅当 同余类和 Euler 函数 - 图54 时成立。更精确的说，若同余类和 Euler 函数 - 图55 是模 同余类和 Euler 函数 - 图56 的一组完全剩余系，则同余类和 Euler 函数 - 图57右边和式中的 同余类和 Euler 函数 - 图58 个模 同余类和 Euler 函数 - 图59 的同余类两两不同，特别地有同余类和 Euler 函数 - 图60
  8. 此定理是上一个定理的不同表述，设 同余类和 Euler 函数 - 图61 那么，对任意的 同余类和 Euler 函数 - 图62 有 同余类和 Euler 函数 - 图63 成立的充分条件式以下 同余类和 Euler 函数 - 图64 个同余式有且仅有一个成立 同余类和 Euler 函数 - 图65
  9. 模 同余类和 Euler 函数 - 图66 的一个同余类中的任意两个整数 同余类和 Euler 函数 - 图67 与 同余类和 Euler 函数 - 图68 的最大公约数相等，即 同余类和 Euler 函数 - 图69
  10. 模 同余类和 Euler 函数 - 图70 的所有不同的既约同余类是同余类和 Euler 函数 - 图71且 同余类和 Euler 函数 - 图72 等于 同余类和 Euler 函数 - 图73 中和 同余类和 Euler 函数 - 图74 互素的数的个数
  11. 在任意取定的 同余类和 Euler 函数 - 图75 个均和 同余类和 Euler 函数 - 图76 互素的整数中，必有两个数对模 同余类和 Euler 函数 - 图77 同余
  12. 存在 同余类和 Euler 函数 - 图78 个数两两对模 同余类和 Euler 函数 - 图79 不同余且均和 同余类和 Euler 函数 - 图80 既约
  13. 设 同余类和 Euler 函数 - 图81 是素数且 同余类和 Euler 函数 - 图82 那么同余类和 Euler 函数 - 图83以及模 同余类和 Euler 函数 - 图84 的既约同余类是同余类和 Euler 函数 - 图85
  14. 设 同余类和 Euler 函数 - 图86 是任意整数，那么当 同余类和 Euler 函数 - 图87 遍历模 同余类和 Euler 函数 - 图88 的一组完全剩余系时 同余类和 Euler 函数 - 图89 也遍历模 同余类和 Euler 函数 - 图90 的一组完全剩余系。也就是说序列 同余类和 Euler 函数 - 图91 是模 同余类和 Euler 函数 - 图92 的一组完全剩余系的充要条件是 同余类和 Euler 函数 - 图93 是模 同余类和 Euler 函数 - 图94 的一组完全剩余系。
  15. 设 同余类和 Euler 函数 - 图95 是任意整数，那么 同余类和 Euler 函数 - 图96 是模 同余类和 Euler 函数 - 图97 的一组既约剩余系的充要条件是同余类和 Euler 函数 - 图98 是模 同余类和 Euler 函数 - 图99 的一组既约剩余系
  16. 设 同余类和 Euler 函数 - 图100 那么，当 同余类和 Euler 函数 - 图101 遍历模 同余类和 Euler 函数 - 图102 的完全（既约）剩余系的充要条件是 同余类和 Euler 函数 - 图103 遍历模 同余类和 Euler 函数 - 图104 的完全（既约）剩余系。也就是说 同余类和 Euler 函数 - 图105 是模 同余类和 Euler 函数 - 图106 的完全（既约）剩余系的充要条件是 同余类和 Euler 函数 - 图107 是模 同余类和 Euler 函数 - 图108 的完全（既约）剩余系
  17. 设 同余类和 Euler 函数 - 图109 是模 同余类和 Euler 函数 - 图110 的完全剩余系 同余类和 Euler 函数 - 图111 是模 同余类和 Euler 函数 - 图112 的完全剩余系。那么有 同余类和 Euler 函数 - 图113 是模 同余类和 Euler 函数 - 图114 的完全剩余系，也就是说当 同余类和 Euler 函数 - 图115 分别遍历模 同余类和 Euler 函数 - 图116 的完全剩余系时同余类和 Euler 函数 - 图117 遍历模 同余类和 Euler 函数 - 图118 的完全剩余系
  18. 设 同余类和 Euler 函数 - 图119 及同余类和 Euler 函数 - 图120那么，当 同余类和 Euler 函数 - 图121 分别遍历模 同余类和 Euler 函数 - 图122 的完全剩余系时 同余类和 Euler 函数 - 图123 遍历模 同余类和 Euler 函数 - 图124 的完全剩余系

证明