二次剩余（上）【考百分kao100.com】.doc

第五讲 数论复习：质数、二次剩余与指数 本讲概述 本讲重点讨论：关于质数相关的一些问题，比如质数的分布，二次剩余和指数的概念。 例题精讲 【例1】 形如4n + 3的素数有无限多个。 【例2】记p(n)为1-n之间的素数的个数，证明对于n ³ 1， (ⅰ) p(n) ³log2n； (ⅱ) pn £ 22n。 【例3】（欧拉判别条件）设p是奇素数，(a, p)＝1，则 （i）a是模p的平方剩余的充要条件是 ≡1（mod p） （1） （ii）a是模p的平方非剩余的充要条件是 ≡－1（mod p） （2） 并且当a是模p的平方剩余时，同余方程（1）恰有两个解。 【例4】判断方程x2 º 5 (mod 11)有没有解。 【例5】形如4m + 1（kÎZ）的素数有无穷多个。 【例6】4k+3形的正整数不能表示成两个整数的平方和。 【例7】 设n，m, x，y，和k都是整数，p是素数， x2 + y2 = p，n2 + m2 = pk， (3) 则k可以表示成二平方之和。 【例8】 对于任意的自然数n，n2 + 1的素因数都可以表示成二平方数之和。 【例9】正整数n能表示成二平方数之和的充要条件，是在它的标准分解式中，形如4k + 3的素因数的指数是偶数。 【例10】设素数p > 2，则存在整数x0，y0与m0，1 £ m0 < p，使得 x02 + y02 + 1 = m0p。 【指数与原根，联赛不做要求】 设m > 1，(a, m) = 1，则使 a r º 1 (mod m) 成立的最小的正整数r，称为a对模m的指数，记为dm(a)，在不致误会的情况下，简记为d(a)。 由Euler定理，当r = j(m)时式(1)成立，因此，恒有dm(a) £ j(m)。若dm(a) = j(m)，则称a是模m的原根。以后，在谈到a对模m的指数时，总假定m > 1，(a, m) = 1。 【例11】 记d = dm(a)，则 a0, a1, L, a d - 1对模m两两不同余。 【例12】设d = dm(a)，r与r¢是正整数，则 a r º a r ¢ (mod m) 的充要条件是 r º r ¢ (mod d)。 特别地，a r º 1 (mod m)的充要条件是d½r。 大显身手 1. 证明：形如6n + 5的素数有无限多个。 2. 设d 是正整数，6d，证明：在以d为公差的等差数列中，连续三项都是素数的情况最多发生一次。 3. 证明：对于任意给定的正整数n，必存在连续的n个自然数，使得它们都是合数。 4. 设n是整数，证明n2 + 1的任何奇因数都是4m + 1（mÎZ）的形式。 5. 若(x, y, z) = 1，则不存在整数n，使得x2 + y2 + z2 = 4n2。 6. 设p是素数，a ³ b > 0，x ³ y > 0，(a, b) = (x, y) = 1，且 p = a2 + b2 = x2 + y2， 则a = x，b = y。 7. 证明： (ⅰ) 设p奇素数，则Mp = 2p - 1的素因数必为2pk + 1型； (ⅱ) 设n ³ 0，则Fn =+ 1的素因数必为2n + 1k + 1型。 3 高二 ·联赛班·寒假班第一讲·学生版