第五讲_二次剩余.pptVIP

第5讲 二次剩余 教师：李艳俊 本讲内容 一、二次剩余的概念 二、模为奇素数的平方剩余与平方非剩余 三、勒让德符号 四、雅可比符号 五、小结 一、二次剩余的概念 二次同余式的一般形式是 其中m是正整数， 。 上式等价于同余式 定义1 设m是正整数，若同余式 有解，则a叫做模m的平方剩余(或二次剩余)；否则a叫做模m的平方非剩余(或二次非剩余)。 例1 分别求出模11，12的二次剩余和二次非剩余。 解： 模11的二次剩余是：1，3，4，5，9； 二次非剩余是：2，6，7，8，10。 模12的二次剩余是：1； 二次非剩余是：5，7，11。 例2 求满足同余式 的所有的点。 解： 模7的二次剩余是：1，2，4；二次非剩余是：3，5，6。 对 ，分别求出 对应的的值为 无解 无解 二、模为奇素数的平方剩余与平方非剩余 定理1(欧拉判别条件) 设p是奇素数， ，则 (1) a是模p的平方剩余的充分必要条件是 (2) a是模p的平方非剩余的充分必要条件是 当a是模p的平方剩余时，同余式 恰有两解。 解: 例 判断137是否为模227平方剩余。 定理2 设p是奇素数，则模p的简化剩余系中平方剩余与平方非剩余的个数各为 ，且 个平方剩余与序列 中的一个数同余，且仅与一个数同余。 所以137是模227平方非剩余。 三、勒让德符号 由此定义，欧拉判别法则可以表示成如下形式： 定义 设p是素数，定义勒让德符号如下： 定理 设p是奇素数，则对任意整数a，有 设p是奇素数，则勒让德符号有如下性质： (2) ，进一步，若 ，则 ； (3) ，进一步，若 ，则 ， 若 ，则 ； (1) ， ； (5) 若 是互素的奇素数，则 。 (4) ； 例1 计算如下勒让德符号的值。 (1) (2) (3) m是否为素数 q=0 q=1 q=-1 q=2 out:0 1 停止 否 是，计算nmodm=q 返回 为奇数； 为偶数。 例2 判断同余式 是否有解？有解时，求出其解数。 例3 判断同余式 是否有解？有解时，求出其解数。 注意：雅可比符号为1时，不能判断a是否为模m的平方剩余。例如 四、雅可比符号 定义 设 是奇素数 的乘积。对任意整数 ，定义雅可比(Jacobi)符号为 因为 ，而同余式组 的每个同余式都无解，所以3是模119的平方非剩余。 当m为奇素数时，则上式为勒让德符号。 如果 ，则 ； 设m是奇数，则雅可比符号有以下性质： ，如果 ，则 ； (3) (2) ； (1) ， (4) (5) 设m,n都是奇数，则 。 例 判断同余式是否有解？ 解：不用考虑563是否为素数，直接计算雅可比符号: 所以同余式无解。 当n是合数的时候，若（a/n）=1，则a不一定是模n的二次剩余。定义 则有 。集合 中的数称为模n的伪二次剩余。 1 2 4 5 8 10 11 13 16 17 19 20 1 4 16 4 1 16 16 1 4 16 4 1 1 -1 1 -1 -1 1 -1 1 1 -1