※ 引述《yoyotvyoo (yoyotvyoo)》之铭言：
: 题目：
: Find the inverse of 4 modulo 7.
: 解答：
[步骤一] 利用 Euclidean algorithm 求 4 与 7 的线性组合
7 = 1 x 4 + 3
4 = 1 x 3 + 1
[步骤二] 利用上述的结果由下往上整理出 1 = xxx
4 = 1 x 3 + 1 //从最后一条式子开始推导
=> 1 = 4 - (1 x 3) //把 1 留在等号左边，其余丢到右边
= (-1) x 3 + 4 //观察上一条式子([步骤一]第一式)的最右边是 3
所以你的下一个步骤会把 3 代换掉
把 3 移到前面，待会会比较好整理
= (-1) x (7 - (1 x 4)) + 4 //利用[步骤一]第一式把 3 换成 7 - (1 x 4)
然后带入上式
= 4 x 2 + 7 x (-1) //将上式整理之后就会得到此式
[步骤三] 写答案
因为 7 x (-1) 在 mod 7 之下为 0
所以[步骤二]的式子会变成 1 = 4 x 2 (记得都是在 mod 7 的情况下讨论的)
=> 4 x 2 ≡ 1 (mod 7)
所以 2 为 4 在 mod 7 下的一个乘法反元素
Ans：4 在 mod 7 下的所有乘法反元素为 2 + 7k ,∀k∈R

谢谢你！但是最后面 7 x (-1) 消掉之后1 = 4 x 2 (mod 7) 这条怎么变成 4 x 2 ≡ 1 (mod 7)?

其实写等号是有问题的，严谨一点应写成≡. 不过既然已强调是在mod 7下讨论，倒也无妨。但如果是初学者仍应避免。你可以把倒数第四行略过，我想这样看反而比较清楚。

这一行只是为了让原po容易理解，考试时不用写出来当题目要求的是 mod 7 的时候，注意你接下来的解题步全部都是在 mod 7 之下讨论的

弄懂了！谢谢你们的帮忙！