欧拉费尔马定理证明
01-07
欧拉费尔马定理证明:
证明:
0(f)简记作N,Fp[x]内次数f(x)且与f(x)互素的
多项式。共有N个分别记作
(1)r1(x),r2(x),,rN(x)
这N个多项式modf(x)互不同余,任何一个与f(x)互素的多项式必与(1)中之一同余,而且只与其中之一同余,用x乘(1)中各项得:
(2)xr1(x),xr2(x),,xrN(x)
(2)中每个多项式与f(x)互素,因而(2)中每个xri(x)必与而且只与(1)之一同余,设xri(x)与(x)同余。 i
(3)xri(x)(x)modf(x),i1,2,,N,由于x与f(x)i
互素,按照定理【1】,当ij时(x)r(x)modf(x) ij
(x) (x),,因而(x)r(x)modf(x) 可见(x),ij12N
不过是r1(x),r2(x),
个同余式相乘,得
NN
ii,rN(x)的某一个排列。将(3)中NxNr(x)(x)mod
i1
Nf(x) i1N
i但是ri(x)(x)而且与f(x)互素,按照定理【1】,
i1i1
N
消去
i1ri(x) 即得 xN1modf(x)。
定理证毕。
定理【1】:如果(x)f(x)(x)g(x)modk(x)但((x),k(x))1,则(x)可以消去。f(x)g(x)modk(x)。