仿射密碼 - 最大公約數

關於仿射密碼的非常簡單的問題。

誰能告訴我怎麼做 $ 3^{-1} $ 應該在下面的解釋中導致 9？

如果要找到整數a (mod n ) 的乘法逆元，可以使用擴展的歐幾里得算法。對於兩個整數a和b，Extendend Euclidean Algorithm 不僅計算最大公約數d，而且計算滿足以下等式的兩個整數x和y：

ax + by = d = gcd( a,b ) （其中 gcd 是最大公約數）

所以如果a和b互質(gcd(a,b)=1)，x是a (mod y)的乘法逆元， y是 b (mod x) 的乘法逆元。

維基百科似乎對算法提供了很好的解釋

希望我有幫助！

引用自：https://crypto.stackexchange.com/questions/33567