第3章 同余式 |
您所在的位置:网站首页 › n次方根的定义为什么n是正整数 › 第3章 同余式 |
![]() 设m是一个正整数,f(x)为多项式f(x) = anxn + ··· + a1x + a0,其中ai是整数,则f(x) ≡ 0(mod m)(*)叫做模m同余式。 若an 如果整数x = a使得 * 式成立,即f(a) ≡ 0(mod m)则a叫做该同余式 * 的解。 事实上,满足x ≡ a(mod m)的所有整数使得同余式 * 成立,即a所在剩余类Ca = { c | c ∈ Z,c ≡ a(mod m)}中的每个剩余都使得同余式 * 成立,因此,同余式 * 的解a通常写成x ≡ a(mod m)。 在模m的完全剩余系中,使得同余式 * 成立的剩余个数叫做同余式 * 的解数。 同余式求解的基本思路: 求解归约(f(x)(mod m) ax ≡ b(mod m)0 定理1.1:设m是一个正整数,a是满足m 设m是一个正整数,a是一个整数。如果存在整数a'使得a · a' ≡ a' ` a ≡ 1(mod m)成立,则a叫做模m可逆元。 根据定理1.1,在模m的意义下,a'是唯一存在的。这是a'叫做a的模m逆元,记作a' = a-1(mod m)。 因此,在定理3.1的条件下,同余式(*)即ax ≡ 1(mod m)的解可写成x ≡ a-1(mod m)。 定理1.2:设 m 是一个正整数,则整数 a 是模 m简化剩余的充要条件是整数 a 是模 m 逆元。 定理1.3:二、中国剩余定理: 1、中国剩余定理:“物不知数”与韩信点兵 三、高次同余式的解数及解法: 1、高次同余式的解数 定理3.1: 四、素数模的同余式: 1、素数模的多项式欧几里得除法 引理4.1(多项式欧几里得除法): 设f(x) = anxn + ··· + a1x + a0为n次整系数多项式,g(x) = xm + ··· + b1x + b0为m ≥ 1次首一整系数多项式,则存在整系数多项式q(x)和r(x)使得f(x) = q(x) · g(x) + r(x),deg r(x) < deg g(x)。 2、素数模的同余式的简化 定理4.1:同余式 设1 ≤ k ≤ n。如果x ≡ ai(mod p),i = 1,···,k,是同余式 同余式 次数 < p的整系数多项式对所有整数取值模p为0的充要条件是其系数被p整除。 定理4.5:设p是一个素数,n是一个正整数,n ≤ p。那么同余式f(x) = xn + ··· + a1x + a0 ≡ 0(mod p)有n个解得充分必要条件是xp - x被f(x)除所得余式的所有系数都是p的倍数。 推论:设p是一个正整数,d是p - 1的正因数,那么多项式xd - 1模p有d个不同的根。
上一篇: https://www.cnblogs.com/3cH0-Nu1L/p/14267885.html 本文来自博客园,作者:3cH0_Nu1L,转载请注明原文链接:https://www.cnblogs.com/3cH0-Nu1L/p/14300666.html |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |