（精）第五章 原根与指标.ppt

4.2 勒让德符号（Legendre） 高斯（gauss）引理 现要证这(p-1)/2个数各不相同,只需证ri=p-sj,若ri=p-sj, 则ri+sj?0(mod p). 又因为ri?ta(mod p), sj?ua(mod p), 其中t和u是小于或等于(p-1)/2的两个正整数. 于是,(t+u)?a(mod p). 因为, (a,p)=1, 所以(t+u)?0(mod p), 这是不可能的, 因为2≤t+u≤p-1, 故有: 而此式左端 故 4.2 勒让德符号（Legendre） 定理4.2.1 若p是奇素数,则 思路：在高斯引理中, 令a=2, 则: 2,2·2,2·3,…,3,(p-1)/2·2 已在1与p之间, 令计算满足p/22kp,有p/4kp/2的k个数 则： 令 p=8a+r, r=1,3,5,7, 则得: 该定理表明, 若 p??1(mod 8), 则 2是模p的二次剩余; 若 p =?3 (mod p), 则2是模p的二次非剩余. 4.2 勒让德符号（Legendre） 定理4.2.1 思路2：当1≤k≤(p-1)/2时, 有: 令: 则： 由高斯引理的证明知ri和p-sj与1, 2, …, (p-1)/2中之一相同(1≤i≤k, 1≤j≤m), 因此得: （1） 又 （2） 4.2 勒让德符号（Legendre） 定理4.2.1 （3）-（2） 故若a=2 若a奇数 4.3 二次互反定理 定理4.3.1 二次互反定理：数论酵母 若p和q是二奇素数, 且p≠q, 则有: 思路： 同理 剩下只需证明: （3） 4.3 二次互反定理 定理4.3.1 作为(0,0),(0,q/2),(p/2,0),(p/2,q/2)为顶点的长方型连接(0,0)和(p/2,q/2)之对角线l,则l上无整点(即二座标为整数的点).否则有整点(x,y)在l上,则xq-yp=0,其中,1≤x≤(p-1)/2, 1≤y≤(p-1)/2, 即得p|x, q|y, 这是不可能的. 由于长方型内的整点数为(p-1)/2.(q-1)/2, 而l下三角型之整点数为: l上三角形中之整点数为: 因此,(3)得证明. 4.3 二次互反定理 推论 若p?q?3(mod 4), 则: 否则, 这是因为, 除非p?q?3(mod 4)，否则 (p-1)(q-1)/4总是偶数 4.3 二次互反定理 对于x2?a(mod p), (p,a)=1设 ,则有: ①当p?3(mod 4)时, 解为±a(p+1)/4. ②当p?5(mod 8)时, ±a(p-1)/4?1(mod p)时, ±a(p+3)/8为(1)的解; 当±a(p-1)/4?-1(mod p)时, ± ·a(p+3)/8为(1)的解. 思路：①当p?3(mod 4)时, a(p-1)/2?1(mod p), 即(a(p+1)/4 )2 ?a(mod p). ②当p?5(mod 8)时, 先求a=-1的解, 由威尔逊定理知: 因a(p-1)/2?1(mod p). a满足: a(p-1)/4?1(mod p)或a(p-1)/4?-1(mod p)时,分别给出(a(p+3)/8)2?a(mod p)和: 4.3 二次互反定理 对于x2?a(mod p), (p,a)=1设 ,则有: ③p?1(mod 8), 则同余式(1)有解±a(s+1)/2·btk, 其 中s满足: p=2k·S+1, 2|s, tk≥0是某个整数. 思路: 由p?1(mod 8), 可设p=2k·S+1, k≥3, 2|s, 所以 所以， ? ± 1(mod p) 故有非负整数 t2=sf(f=0或1)使下式成立: 故又有非负整