周期引理 PL (Periodicity Lemma.)

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135121747

在这里插入图片描述

在这里插入图片描述

原先串：若干 pp ，加一个前缀，因此是 A(x)1−xp mod xn+1\dfrac {A(x)}{1-x^p}\bmod x^{n+1}

这个： 在这里插入图片描述

 mod xn+1\bmod x^{n+1} 为0。（多项式）

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

我们有 R(x) mod xn+1=0,deg(R)∈nR(x)\bmod x^{n+1}=0,deg(R)\in n ，所以 R(x)=0R(x)=0 ，所以左式恒为0。

在这里插入图片描述

右边度数可以分析。（多项式除法度数相减）