#多项式笔记

---

$ ext{GCD}$要注意的一个东西是唯一性跟首项系数有关，两个多项式的$ ext{GCD}$在差一个非零常数倍时是唯一确定的，这样所有$ ext{GCD}$们都是$ ext{$unicode{9996}unicode{4e00}$GCD}$的倍数。

另外整除关系不因系数域的扩大而改变，但是$Z[x]$中不能做除法，并不能直接算带余除法，扩域如复数域能分解的，实数域和有理数域及整数域不一定能分解。

但是，如果$f(x)=g(x)q(x)+r(x)$中，若$g(x)$的首项系数为$pm 1$，则，存在唯一的$q(x),r(x)$具有带余除法的式子。

#模p同余

---

prime number 是如此重要，mod m 时也可以定义，并且有一些基本性质，但是这里有一个提及的重要性质并不能保持，并且还有一些坏的性质，没太大用处。

$$egin{align*}f^p(x)equiv fleft(x^p ight)( ext{mod} p) ag{1}end{align*}$$

Table[Factor[x^10 - 1, Modulus -> i], {i, 12}]

    (*
        {Factor[-1+x^10,Modulus->1],(1+x)^2 (1+x+x^2+x^3+x^4)^2,(1+x) (2+x) (1+x+x^2+x^3+x^4) (1+2
     x+x^2+2 x^3+x^4),Factor[-1+x^10,Modulus->4],(1+x)^5 (4+x)^5,Factor[-1+x^10,Modulus->6],(1
    +x) (6+x) (1+x+x^2+x^3+x^4) (1+6 x+x^2+6 x^3+x^4),Factor[-1+x^10,Modulus->8],Factor[-1+x^1
    0,Modulus->9],Factor[-1+x^10,Modulus->10],(1+x) (2+x) (3+x) (4+x) (5+x) (6+x) (7+x) (8+x)
    (9+x) (10+x),Factor[-1+x^10,Modulus->12]}
    *)

(1 + x)^2 (1 + x + x^2 + x^3 + x^4)^2 // Expand

    (*
        1+4 x+8 x^2+12 x^3+16 x^4+18 x^5+16 x^6+12 x^7+8 x^8+4 x^9+x^10
    *)

Factor[#, Modulus -> 2] & /@ {(x + 1)^2, x^2 + 1, (x - 1)^2, x^2 - 1}

    (*
        {(1+x)^2,(1+x)^2,(1+x)^2,(1+x)^2}
    *)

#费马小定理

---

[Fermat's Little Theorem](http://mathworld.wolfram.com/FermatsLittleTheorem.html)

#二项式系数的数论性质

---

$p$ is an prime number, $k$ is a positive integer, then

(i) $pleft|left(egin{array}{c} p k end{array} ight) ight.$, holds for $k=1,2, ext{...},p-1$

(ii) $left(egin{array}{c} p-1 k end{array} ight)equiv (-1)^k( ext{mod} p)$, holds for $k=0,1, ext{...},p-1$

(iii) $left(egin{array}{c} k p end{array} ight)equiv left[frac{k}{p} ight]( ext{mod} p)$

#证明(1)式

---

$f(x)=left[a_nx^n+left(a_{n-1}x^{n-1}+ ext{...}+a_0 ight) ight]^p\&equiv a_n^px^{n p}+left(a_{n-1}x^{n-1}+ ext{...}+a_0 ight)^pequiv a_nx^{n p}+left(a_{n-1}x^{n-1}+ ext{...}+a_0 ight)equiv ext{...}\&equiv a_nx^{n p}+a_{n-1}x^{(n-1)p}+ ext{...}+a_1x^p+a_0=fleft(x^p ight)( ext{mod} p)$