记录许多数论方面的公式等小东西

裴蜀：

存在整数 $x,y$ ，使得 $ax+by=\gcd(a,b)$ 成立。
二元一次不定方程：

a_1x_1 + a_2x_2 = b.

裴蜀定理指出，该方程有解，当且仅当

d = \gcd(a_1,a_2) \mid b.

对于 $n$ 元一次不定方程

a_1x_1 + a_2x_2 + \cdots + a_nx_n = b,\quad (n>3)

由裴蜀定理可知，方程有解当且仅当

\gcd(a_1,a_2,\cdots,a_n) \mid b.

费马小：

设 $p$ 是素数。对于任意整数 $a$ 且 $p\nmid a$ ，都成立 $a^{p-1}\equiv 1\pmod p$ .
设 $p$ 是素数。对于任意整数 $a$ ，都成立 $a^{p}\equiv a\pmod p$ .

欧拉：

对于素数 $p$ ，有 $\varphi(p)=p-1$
$\varphi(n) = n \times \prod_{i = 1}^s{\dfrac{p_i - 1}{p_i}}$
对于整数 $m>0$ 和整数 $a$ ，且 $\gcd(a,m)=1$ ，有 $a^{\varphi(m)}\equiv 1\pmod{m}$
对于任意正整数 $m$ 、整数 $a$ 和非负整数 $k$ ，有

a^k \equiv \begin{cases}a^{k \bmod \varphi(m)}, &\gcd(a,m) = 1, \\a^k, &\gcd(a,m)\ne 1, k < \varphi(m), \\a^{(k \bmod \varphi(m)) + \varphi(m)}, &\gcd(a,m)\ne 1, k \ge \varphi(m).\end{cases} \pmod m

lucas：

对于素数

p

，有

\binom{n}{k}\equiv \binom{\lfloor n/p\rfloor}{\lfloor k/p\rfloor}\binom{n\bmod p}{k\bmod p}\pmod p.

lagrange：

Lagrange 插值的形式为：

f(x)=\sum_{i=1}^ny_i\cdot\prod_{j\neq i}\dfrac{x-x_j}{x_i-x_j}

莫比乌斯：

莫比乌斯函数（Möbius 函数）定义为

\mu(n)=\begin{cases}1,&n=1,\\0,&n\text{ is divisible by a square }>1,\\(-1)^k,&n\text{ is the product of }k\text{ distinct primes}.\\\end{cases}

扩欧

扩展欧几里得算法求逆元：

乘法逆元是数论中的一个重要概念。给定整数

a

和模数

m

，如果存在整数

x

使得

ax≡1 ( \bmod m )

，则称

x

是

a

在模

m

下的乘法逆元，记作

a^{−1}

。

使用欧几里得算法求

\gcd(a,m)

。如果

\gcd(a,m)=1

，则

a

在模

m

下没有逆元。如果

\gcd(a,m)=1

，则通过扩展欧几里得算法求出

x

和

y

，使得：

ax+my=1

此时，

x

就是

a

在模

m

下的逆元。

记录许多数论方面的公式等小东西

文章操作

裴蜀：

费马小：

欧拉：

lucas：

lagrange：

莫比乌斯：

扩欧

相关推荐

评论

记录许多数论方面的公式等小东西