平方剩余、二次互反律一、平方剩余定义：设p为奇素数且\(\mathsf{a\neq0\mod\p}\)，如果a在模p下是另一个数的平方，即\(\mathsf{a\equivb^{2}\mod\p}\)，则称a为模p下的平方剩余，否则称a为平方非剩余。而二次同余式\(\mathsf{x^{2}\equiva\mod\p}\)可能有0—2个解例子：\(\mathsf{p=5}\)时，因为\(\mathsf{1^{2}\equiv1\mod\5\qquad2^{2}\equiv4\mod\5\qquad3^{2}\equiv4\mod\5\qquad4^{2}\equiv1\mod\5}\)则1，4

平方剩余、二次互反律一、平方剩余定义：设p为奇素数且\(\mathsf{a\neq0\mod\p}\)，如果a在模p下是另一个数的平方，即\(\mathsf{a\equivb^{2}\mod\p}\)，则称a为模p下的平方剩余，否则称a为平方非剩余。而二次同余式\(\mathsf{x^{2}\equiva\mod\p}\)可能有0—2个解例子：\(\mathsf{p=5}\)时，因为\(\mathsf{1^{2}\equiv1\mod\5\qquad2^{2}\equiv4\mod\5\qquad3^{2}\equiv4\mod\5\qquad4^{2}\equiv1\mod\5}\)则1，4

Hensel引理、原根一、Hensel引理Hensel引理：\(\mathsf{f(x)}\)是一个整系数多项式\(\mathsf{(\f(x)\inZ(x)\)}\)，对于素数p，整数a使得\(\mathsf{p^{k}\midf(a)}\)，\(\mathsf{(\f^{'}(a)，p\)=1}\)，即\(\mathsf{f(a)\equiv0\mod\p^{k}，f^{'}(a)\neq0\mod\p}\)。则在模p意义下恰有一个整数t使得\(\mathsf{f(a+tp^{k})\equiv0\(mod\p^{k+1})}\)。也就是在模\(\mathsf{p^{k+1}}\)的意义下

同余、中国剩余定理一、同余(Congruence)1.令\(\mathsf{a,\b,\m}\)为整数，且$\mathsf{m\neq0}$。当满足\(\mathsf{m\mid(a-b)}\)时，称a与b模m同余，写作\(\mathsf{a\equivb\mod\m}\)例子：\(\mathsf{3\equiv27\mod\12}\)，\(\mathsf{-3\equiv11\mod\7}\)2.基本性质：同余兼容常用加法与乘法运算。如果\(\mathsf{a\equivb\(mod\m)}\)并且\(\mathsf{c\equivd\(mod\m)}\)，那么\(\mathsf{a+c\e

Hensel引理、原根一、Hensel引理Hensel引理：\(\mathsf{f(x)}\)是一个整系数多项式\(\mathsf{(\f(x)\inZ(x)\)}\)，对于素数p，整数a使得\(\mathsf{p^{k}\midf(a)}\)，\(\mathsf{(\f^{'}(a)，p\)=1}\)，即\(\mathsf{f(a)\equiv0\mod\p^{k}，f^{'}(a)\neq0\mod\p}\)。则在模p意义下恰有一个整数t使得\(\mathsf{f(a+tp^{k})\equiv0\(mod\p^{k+1})}\)。也就是在模\(\mathsf{p^{k+1}}\)的意义下

同余、中国剩余定理一、同余(Congruence)1.令\(\mathsf{a,\b,\m}\)为整数，且$\mathsf{m\neq0}$。当满足\(\mathsf{m\mid(a-b)}\)时，称a与b模m同余，写作\(\mathsf{a\equivb\mod\m}\)例子：\(\mathsf{3\equiv27\mod\12}\)，\(\mathsf{-3\equiv11\mod\7}\)2.基本性质：同余兼容常用加法与乘法运算。如果\(\mathsf{a\equivb\(mod\m)}\)并且\(\mathsf{c\equivd\(mod\m)}\)，那么\(\mathsf{a+c\e