模反元素

一整数a對模数n之模反元素是指滿足以下公式的整數 b

$a^{-1} \equiv b \pmod{n}.$

也可以寫成以下的式子

$ab \equiv 1 \pmod{n}.$

整数 a 對模数 n 之模反元素存在的充分必要條件是 a 和 n 互質，若此模反元素存在，在模数 n 下的除法可以用和對應模反元素的乘法來達成，此概念和實數除法的概念相同。

求法 [编辑]

可以用扩展欧几里得算法求模反元素。

设egcd扩展欧几里得算法的函数，它接受两个整数a,b，输出三个整数g,x,y。g,x,y满足等式ax+by=g，且g是a,b的最大公约数。

现在，求a关于模n的模反元素（a<n）。egcd(a,n)={g,x,y}。若g=1，则该模反元素存在，为n+x；若g不等于1，则该模反元素不存在。

求540关于1769的模反元素。利用Mathematica的ExtendedGCD函数，得该模反元素为1769-95=1674。容易验证540*1674 mod 1769=1。

這是與数学相關的小作品。你可以通过编辑或修订扩充其内容。