如何求一个数的模逆元？

本文共计1561个文字，预计阅读时间需要7分钟。

日记 1. 最近几天连续锻炼，累s了，钓鱼属性正在觉醒.....+ 注意：文章逻辑较为繁琐，请耐心阅读。建议阅读后适当放松，感受最佳。引入多个主题中，要运用除法取模等技巧，但在取模等式中等价于等式。

diary

1.最近这几天连着训练,累s了,咸鱼属性正在觉醒.....

attention

文章逻辑较为繁琐,请仔细耐心阅读
建议放大后远距离阅读,感受最佳

引入

许多题目中要用到除法取模
但在取模等式等价变形中没有除法,为啥?

\((6\div3)\bmod 4 \not= (6 \bmod 4\div 3 \bmod 4) \bmod 4\)

说明如果在计算数字过大时可能超范围,那么应该怎么办呢?

前置知识 快速幂

不懂可以去看鄙人的博客关于位运算

同余符号

\(a\equiv1\pmod{n}\) 这个三条横线的符号表示\(a\)对\(n\)取模等于1对\(n\)取模

单位元 \(a\equiv1\pmod{n}\)

在一个集合中，对于某种运算，如果对于任何的集合元素 \(a\)，和元素 \(e\) 运算，得到还是集合元素 \(a\) 本身，则称 \(e\) 为这个运算下的单位元。