2.7.3　方程求解

下面考虑一个方程:

其中是已知整数，需要求解变量。这个方程在后面介绍的RSA加密系统中有至关重要的作用。一般情况下，这个方程比较难解，但如果是一个素数，那么就会变得较容易了。

令为素数，且为整数，若满足。此时就存在一个整数，使得：

将方程改写成：

如何求解这个方程呢?需要考虑两种情况，首先假设，那么就得到，很容易求得。

假设，由于，那么就有，。并且因为是素数，所以，就有。该结论也称费马小定理，将在定理7.5.3中详细介绍并证明。引用这个定理，继续推导可得出：

此时就很容易发现，方程的唯一解为：

例2.7.5　求解下列方程：

解：由于8017是一个素数，为了求解，可以转化成另一个关于求解的方程：

那么根据欧拉定理，就有。代入公式，就可以得到: