有关数论的重要公式定理
1.有关同余性质:
同余的性质
性质 1:a≡a(mod m),(反身性)
这个性质很显然.因为 a-a=0=m·0。
性质 2:若 a≡b(mod m),那么 b≡a(mod m),(对称性)。
性质 3:若 a≡b(mod m),b≡c(mod m),那么 a≡c(mod m),(传递性)。
性质 4:若 a≡b(mod m),c≡d(mod m),那么 a±c≡b±d(mod m),(可加减性)。
性质 5:若 a≡b(mod m),c≡d(mod m),那么 ac≡bd(mod m)(可乘性)。
性质 6:若 a≡b(mod m),那么 an≡bn(mod m),(其中 n 为自然数)。
性质 7:若 ac≡bc(mod m),(c,m)=1,那么 a≡b(mod m)
性质 8:若 a≡b(mod m),那么 a 的 n 次方和 b 的 n 次方也对于 m 同余。
性质 9:若 a≡b(mod m)、c≡d(mod m)、e≡f(mod m)……x≡y(mod m),
那么:a+c+e+……+x 和 b+d+f+……+y 也对于 m 同余。
同余方程的性质
1.交换律 (w+x)mod n≡(x+w)mod n
(w*x)mod n≡(x*w)mod n
2.结合律 [(w+x)+y]mod n≡[w+(x+y)]mod n
[(w*x)*y]mod n≡[w*(x*y)]mod n
3.分配律 [w*(x+y)]mod n≡[(w*x)+(w*y)]mod n
4.单位元 (0+w)mod n≡w mod n
(1*w)mod n≡w mod n
5.加法逆元: 对 w 属于 Zn,存在 x 属于 Zn,使得 w+x≡0 mod n,称 x 为 w 的加法逆元,记作 x=-w。
6.乘法逆元 : 设 w 属于 Zn,如果存在 x 属于 Zn,使得 w*x≡1 mod n,就说 w 是可逆的,称 x 为 w 的乘法逆元,记作 x=w 求
解模线性方程;并不是每个元素都又乘法逆元,可以证明,w 属于 Zn 是可逆的,当且仅当 gcd(w,n)=1.如果 w 是可逆的,则可
顶一除法。
2.费马小定理:
当 p 为素数,a 为任意整数时:,如果 a 不是 p
的倍数,即(a,p)=1 时
3.有关最大公约数和最小公倍数证明
辗转相除法的证明
设两数为 a、b(a > b),求它们最大公约数的步骤如下:
设 q = a / b,r = a % b, 得 a=bq+r(0≤r<b)。
1)若 r = 0, 则 b 是 a 和 b 的最大公约数。
2)若 r≠0,则继续考虑。首先,应该明白的一点是任何 a 和 b 的公约数都是 r 的公约数。要想证明这一点,就要考虑把 r 写成 r=a-
bq。现在,如果 a 和 b 有一个公约数 d,而且设 a=sd , b=td, 那么 r = sd-tdq = (s-tq)d。因为这个式子中,所有的数(包括 s-
tq )都为整数,所以 r 可以被 d 整除。对于所有的 d 的值,这都是正确的;所以 a 和 b 的最大公约数也是 b 和 r 的最大公约数。因
此我们可以继续对 b 和 r 进行上述取余的运算。这个过程在有限的重复后,可以最终得到 r=0 的结果,我们也就得到了 a 和 b 的