Th1:设p是素数，f(x)=an(xn)+an-1(x*n-1)+…+a1x+a0,n≥1，an≠0 (mod p) (f(x)∈Z[x]),则f(x)≡ 0 (mod p)的解数不超过n(拉格朗日定理)
证明：
(f(x)的解集∈{C0,C1,C2…,Cp-1})
①若p≤n,则解数≤n
②若p>n,(使用归纳法证明)
当n=1时，a1*x+a0 ≡ 0 (mod p),∵(a1,p)=1(根据an≠0 (mod p)),且(a1,p)|a0,故恰有1个解，此时解数≤n(次数)
假设当n=n-1时，假设成立，即解数≤n-1,则当n=n时，
假设f(x)≡ 0 (mod p)有n+1个解，即{Cx0,Cx1,Cx2,…Cxn}(0≤x0,…,xn≤p-1)
有带余除法(针对多项式)可得，f(x)=(x-x0)*g(x)+r(x)（以(x-x0)为除数，且r(x)的次数会小于除数，∵（x-x0）次数为1，故r(x)次数为0 ，即常数，这里变成r）
将x=x0带入得，f(x0)=r
∵f(x0)≡0 mod(p)
∴r ≡ 0 (mod p)（两边同时加上(x-x0)*g(x)）
∴r+(x-x0)*g(x) ≡ 0 (mod p)
∴f(x)≡(x-x0)*g(x) (mod p)(这里g(x)的最高次项为n-1)
∴f(xk)≡(xk-x0)*g(xk) (mod p)
又∵f(xk) ≡ 0 (mod p), (Cxk-x0,p)=1
∴g(xk) ≡ 0 (mod p)
故g(xk)的最高次数为n-1且有n个解
又∵根归纳假设，当n=n-1时，解数
Original: https://www.cnblogs.com/jane315/p/13792104.html
Author: jane_315
Title: 数论-模数是素数的同余式（拉格朗日定理）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/583752/
转载文章受原作者版权保护。转载请注明原作者出处！