中国剩余定理 。利用中国剩余定理求解同余式方程组 x≡2mod3 x=3mod5 x=2mod 7 解：由前面定理可知n1=3,n2=5,n3=7,b1=2,b2=3,b3=2 由计算得N=3×5×7=105,N=105/3=35,N2=105/5=21,N3=105/7=15, y1351m0d3=2m0d3,y2=211m0d5=1mod5,y3=151mod7=1mod7 则x=2×35×2+3×21×1+2×15×1m0d105=23m0d105
利用中国剩余定理求解同余式方程组 解：由前面定理可知n1=3, n2=5, n3=7, b1=2, b2=3, b3=2 由计算得N=3×5×7=105, N1=105/3=35, N2=105/5=21, N3=105/7=15， y1≡35-1mod 3=2 mod 3，y2≡21-1mod 5=1 mod 5，y3≡15-1mod 7=1 mod 7 则x≡2×35×2+3×21×1+2×15×1 mod 105=23 mod 105. 中国剩余定理 2mod 3 3mod5 2mod 7 x x x
例 9 6.2二次剩余
6.2 二次剩余
二次剩余 ·二次剩余定义 ■令n为正整数，若一整数a满足gcd(a,n)=1且x2≡a mod ni有 解，则称a为模n的二次剩余(quadratic residue);否则称a为 模n的二次非剩余(quadratic non-residue)。 ·欧拉判别法则 ■设p为奇素数，如果a是模p的二次剩余，则： p-] a2≡1modp 如果a是模p的二次非剩余，则： p-l a2≡-1modp
二次剩余定义 令n为正整数，若一整数a满足gcd(a, n)=1且𝒙 𝟐 ≡ a mod n有 解，则称a为模n的二次剩余(quadratic residue)；否则称a为 模n的二次非剩余(quadratic non-residue)。 欧拉判别法则 设p为奇素数，如果a是模p的二次剩余，则： 如果a是模p的二次非剩余，则： 二次剩余 1 2 1mod p a p 1 2 1mod p a p
二次剩余举例 ■设n=7,因为 12≡1m0d7,22≡4m0d7 32≡2m0d7,42≡2m0d7 52=4m0d7,62≡1mod7 1、2、4是模7的二次剩余，而3、5、6是模7的二次非剩余。 ■如p是素数，则模p的二次剩余的个数为(p-1)/2,模p的二次非剩余 的个数也为(p-1)/2
二次剩余举例 设n=7，因为 1 2 1 mod 7，2 2 4 mod 7 3 2 2 mod 7，4 2 2 mod 7 5 2 4 mod 7，6 2 1 mod 7 1、2、4是模7的二次剩余，而3、5、6是模7的二次非剩余。 如p是素数，则模p的二次剩余的个数为(p-1)/2，模p的二次非剩余 的个数也为(p-1)/2