Number Theory

Baby Step, Giant Step 解决这样一类同余方程的方法 $$a^x \equiv b\pmod c$$ 结合原根的知识还能解决模数有原根的$N$次剩余问题 $$x^n \equiv b\pmod c$$ ...

对于二次剩余式 $$x^2\equiv n\pmod p$$ 其中$p$为奇素数，且$p \nmid n$，求$x$。 ...

$\forall a<m,(a, m)=1$，均有$a^{\varphi(m)}\equiv1\pmod{m}$，于是就有欧拉定理： $$a^n\equiv a^{n \mod \varphi(m)} \pmod{m}$$ 对于$n$取值较大的情况（比如$10^{30000}\mod 13$），欧拉降幂的作用不可忽视，但局限的是必须满足$(a,m)=1$才能有上式恒成立。 由于上述形式流传甚广，读者大抵早已熟记于心，这里便不再赘述。本文的最终目的是介绍另一个适用范围更广的版本，即所谓拓展欧拉定理。 $$a^n\equiv a^{n \mod \varphi(m) + \varphi(m)} \pmod{m} \quad \textrm{if }n \geq \varphi(m)$$ ...

题外话：好像文章有点长，本地调的时候加载目录都掉帧了。虽然一度想删点题目，但思前想后还是一题没删，总感觉每一题都代表了一种典型，实在不好取舍，或许只写推导会好一点，但还是有点怕代码的实现未有较好交代。。。 好了，闲言少叙。 本篇是平时刷的反演题目的解题记录，个人认为这方面的知识点和写题目是有点脱节的，题目要么是纯套路，要么就是有些不太友好的小技巧。 题目来源：Luogu, LibreOJ, HDU等。 ...

info Update 2021.10.03 增加PN筛 包含有: 线性筛，杜教筛，Min25筛，PN筛 TODO: 州阁筛 本篇主要用于入门数论中的一些简单的筛法 虽然不是特别全面，但是后面会一步步完善的。 注意：不会对用到的数论函数解释，默认读者对数论有基本认知。 ...

之前介绍Lucas定理时，内容涉及到了中国剩余定理，以及欧拉定理。 后者应该是广为人知的定理（之后也会写拓展欧拉定理的吧），然而前者的名气似乎远有不如。 本篇以证明为主，（不喜欢证明的可以关了）当然也会遵循传统给出板子。 ...

info Update at 2022.1.19 修正FastMod代码来源。 证明和代码分开，可以根据自己的需要跳转。 ...

由费马小定理可以知道，如果$p$是一个素数，且$(x, p)=1$，我们可以得到： $$\begin{aligned} x^{p-1} \equiv 1 \pmod{p} \end{aligned}$$ 那么反之，如果有$x$满足$\forall a>1,(a,x)=1,s.t. a^x \equiv 1 \pmod{x}$，这样的$x$一定是素数吗？ ...

三次剩余，以及一个可以继续推广至k次剩余的随机算法 ...