※ 引述《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 之下討論的

弄懂了！謝謝你們的幫忙！