数论进阶

简单数论

在模意义下，所有分数都是非法的。比如：

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)

。