数论ch2-5节--模是素数的同余式.pptVIP

* §5 模是素数的同余式 定理5.1 设p是一个素数, n 0, f (x) ? anxn ? an?1xn?1 ? … ? a1x ? a0 是一个整系数多项式. 则同余式 f (x) ? 0 (mod p) (1) 最多有n个解. 定理5.1证明 证 对f(x)的次数n进行归纳. 当n???1时, 设一次同余式为 a1x???a0???0 (mod p), (p,a1)=1. 因为pa1, 故恰有一解. 假设定理对次数为n???1(n???2)的同余式成立, 现在证明f (x) ? 0 (mod p)最多有n个解. 当n???p时结论显然成立, 故可设n???p???1. 用反正法, 假设有n???1个解 x0, x1, …, xn, xi?xj (mod p), 0???i??j???n, 定理5.1证明 但 f(x)???f(x0)???(x ??x0)g(x), 其中g(x)是首项系数为an的n???1次整系数多项式, 因此有 f(xk)???f(x0)???(xk???x0)g(xk) ??0 (mod p), 当k??0时, xk???x0 0 (mod p), 故n???1次同余式g(x)???0 (mod p)有n个解, 与归纳假设矛盾. # 应用 推论5.2 若同余式 f (x) ? anxn ? … ? a1x ? a0 ? 0 (mod p) 的解的个数大于n, 其中p是素数, ai (i ? 0, 1, …, n)是整数, 则 p | ai (i ? 0, 1, …, n). 应用 定理5.3 对于任给素数 p, 多项式 f (x) ? (x?1) (x?2) ??? (x?p?1) ? x p?1 ? 1 的所有系数被 p 整除. 证 如有某些系数不被p整除, 设这些系数的足标最大的为k, 则k???n, k次同余式 akxk ? … ? a1x ? a0 ? 0 (mod p), pak 的解的个数大于k, 与定理1矛盾. # 威尔逊定理 (Wilson定理) 设p是一个素数, 则 (p?1) ! ?1 ? 0 (mod p). 推论 证 设g(x)????(x?1) (x?2) ??? (x?p?1) , 则1, …, p???1是同余式 g(x)???0 (mod p) 的p???1个解. 由费马小定理他们也是x p?1 ? 1 (mod p)的p???1个解. 从而可得同余式f(x)???0 (mod p)有p???1个解, 而f(x)是p???2次多项式, 由定理2, 其所有系数被p整除. # 推论的证明 Wolstenholme定理 定理5.4 设素数 p 3, 则有 Wolstenholme定理的证明 证设g(x)???(x?1) (x?2) ??? (x?p?1)???xp???1???s1xp?2??…??sp?2x?? (p???1)!,其中sj(j???1,…, p???2)是整数, 且 sp?2????k?=?1p?1(p???1)!/k. 由定理3知, p?|?sj(j???1, …, p???2), 在上式中令x???p, 由于g(p)?=?(p???1)!, 故g(x)给出 pp???1???s1pp???2???…???psp??2???0. 因为p??3, 对上式取p3, 得psp???2???0 (mod p3), 故sp???2???0 (mod p2). 推广的Wolstenholme定理 设 n 1, (n, 6) ? 1, 则有 * 归纳法证明, 对多项式次数归纳. * f(x)mod p为零多项式. * g(x)= (x?1) (x?2) ??? (x?p?1) ? 0 (mod p), h(x) = x p?1 ? 1 ? 0 (mod p), 各有p ?1个解, 故f(x) ? 0 (mod p)有p ?1个解, 超过多项式次数, 故f(x) 系数被p整除. * * 令g(x)= (x?1) (x?2) ??? (x?p?1), 考虑次高项系数? s p?2. 同余式左边为g(x)次高项系数的绝对值. * 证明见§10. * * * * 归纳法证明, 对多项式次数归纳. * f(x)mod p为零多项式. * g(x)= (x?1) (x?2) ??? (x?p?1) ? 0 (mod p), h(x) = x p?1 ? 1 ? 0 (mod p), 各有p ?1个解, 故f(x) ? 0 (mod p)有p ?1个解, 超过多项式次数, 故f(x) 系数被p整除. * * 令g(