《数学竞赛二次剩余及其应用讲义》由会员分享，可在线阅读，更多相关《数学竞赛二次剩余及其应用讲义（4页珍藏版）》请在金锄头文库上搜索。
1、二次剩余二次剩余及其应用及其应用 一、一、 二次剩余的定义：二次剩余的定义： 正整数m 1，n Z，(m,n) = 1，若存在x Z，使得x2 ( )，则称 n 为模 m 的二次剩余。 否则，称为二次非剩余。 勒勒让德让德(Legendre)符号符号： 设 p 为奇素数，a Z 且(a,p) = 1，定义：( ) = 1，若 a 为 p 的二次剩余 1，若 a 为 p 的二次非剩余，称为勒让德符号。当 a b(mod p)时，显然( ) = ( b )。 例1、 证明具有下列形式的素数有无穷多个. （1）8k + 3 （2）8k + 5 （3）8k + 7 例2、 求有序整数对(a,b)的个数
2、，使得x2+ + = 167有整数解(x,y)，其中1 a、b 2004. 二、二、 与与素数的二次剩余相关的定理：素数的二次剩余相关的定理： 定理定理 1、设 p 为奇素数，模 p 的缩系中有p1 2 个二次剩余，有有p1 2 个二次非剩余。且12、22、 (p1 2 )2即为其p1 2 个二次剩余。 定理定理 2、设 p 为奇素数，a Z 且(a,p) = 1，则(p 1)! ( ) p1 2(mod p)。 定理定理 3（欧拉（欧拉(Euler)判别判别条件）条件） 、设 p 为奇素数，a Z 且(a,p) = 1， p1 2则 ( )(mod p)。 定理定理 4、设 p 为奇素数，则
3、(1 ) (1) p1 2(mod p)。即当p 1(mod 4)时，-1 为 p 的二次剩余；当 p 3(mod 4)时，-1 为 p 的二次非剩余。 例3、 已知 pqr 均为素数，n 为正整数，p+ = 2，求证：n=1. 例4、 若 p 为奇素数，证明：当且仅当p 1(mod 4)时，p 可以表示成两个非零完全平方数之和，且表示 方法唯一. 三三、二次互反律、二次互反律 定定理理 5(高斯高斯(Gause)引理引理)、设 p 为奇素数，a Z 且(a,p) = 1，若a、2a、 p1 2 a关于模 p 的最小正 余数中有个大于p 2，则( ) = (1) 。 定理定理 6、 设 p 为
4、奇素数， (2 ) = (1) 21 8。 即当p 1(mod 8)时， 2 为 p 的二次剩余； 当p 3(mod 8) 时，2 为 p 的二次非剩余。 定理定理 7(二次互反律二次互反律)、设 p、q 为奇素数，p q，则( )( ) = (1) 1 2 1 2。 例5、 证明素数 p 为费马数当且仅当 p 的二次非剩余均为 p 的原根. 例6、 若 P 为奇素数，则梅森数的每个素因子必形如8k 1. 例7、 求方程x2014= 42013+ 42012+ 2011 + 2010的整数解. 思考题： 证明：存在两个严格递增的正整数数列a和b，使得对于任意正整数 n，都有a (a + 1)|( 2 + 1).
