简化剩余系.ppt

文档介绍：简化剩余系
定义
取定
若
是与模
互素的
中的每一个数
都与
互素,
则称
剩余类.
从所有与模
互素的
剩余类
中各取一数所组成
的一组数称为
模
的一个简化剩余系.
例如,
是与模
互素的
剩余类.
给定模
的一个简化剩余系
则
恰与其中的一数同余
模
的一个简化剩余系
模
的一个完全
可从
剩余系中取出.
定义
设
到中与互素的数
的个数,
记为
称为Euler函数.
如
模
的一个简化剩余系中共
个数
与模
互素的
剩余类共
个
与模
互素,
则其中至少有两数
若有
个数
对模
同余
简化剩余系的判定及构造
定理1
一组数
是
模
的一个简化
剩余系
模
对
两两互不同余
定理2
若
是
模
的
一个简化剩余系,
设
则
也是
模
的
一个简化剩余系.
定理3
若
模
的
一个简化剩余系,
设
则
的
一个简化剩余系.
分别通过
通过模
简化剩余系的判定及构造
如
通过模6的一个简化剩余系
通过模5的一个简化剩余系
则
通过模30的一个简化剩余系
简化剩余系的性质
若
是
模
的
两个简化剩余系,
则
和
例1
模
的
一个简化剩余系,
其中每一个数
写出
都是偶数.
例2
模
的
一个简化剩余系,
其中每一个数
写出
对模
同余
例3
设
证明
定理4(Wilson)
是素数,
设
是模
的一个简化剩余系,
则
特别地,
证明
唯一的
不妨设
是模
的一个简化剩余系,
则在该剩余系中,每个
又
都存在
使得
或
则
可两两分组,我们得到
例4
是奇素数,
设
证明
证