数论进阶

Function0816 · 2024-11-30 16:15:58 · 算法·理论

简单数论

在模意义下，所有分数都是非法的。比如： 5/3 (mod 11)就是非法的。但是，如果将这个分数乘上一个数后变成了整数，那么它就是合法的。比如:(5/3)*12 (mod 11)就是合法的。

现在要求能够实现模意义下的除法，对于一个模数 p 和除数 x ，往往能找到一个数，使乘上这个数，可以起到除法的效果。这个数称为逆元。

逆元 inv(x)需要满足:

x·inv(x)≡1$ $(mod$ $p)

例如：计算 5÷3×12 (mod 11)

在(mod 11)下，n÷3可以代换为n×4。所以：

5÷3×12=5×4×12=9$ $(mod$ $11)

只有x与p互质时，才有x的逆元inv(x)。

要求inv(x),可使用费马小定理：

若p为质数

x^{p-1}≡1

所以，x·x^{p-2}≡1，inv(x)为x^{p-2}。注意，x与p不互质时不存在inv(x)。