除法取模运算(费马小定理+逆元) 一看就懂！

• lily_fung 发布于
• 1106 收藏

原文地址：除法取模与逆元/费马小定理 加了部分自己的理解，希望大家更容易理解，这个算法真的很重要！对于正整数和，如果有，那么把这个同余方程中的最小正整数解叫做模的逆元。逆元一般用扩展欧几里得算法来求得，如果为素数，那么还可以根据费马小定理得到逆元为。（都要求a和m互质） 推导过程如下(摘自Acdreamer博客)这个为费马小定理，m为素数是费马小定理的前置条件。其实就是推出:(1/a)%m = a...