逆元是一個數學概念,在模運算中尤為重要。
逆元的定義基於模運算,如果存在一個數( x ),使得( a \times x \equiv 1 \pmod{n} )(即( ax )除以( n )的餘數為1),那麼稱( x )是( a )模( n )的逆元。這裡的「模」指的是模數,用於限制數值的範圍,逆元通常用於模運算中的除法轉換,即將除法運算轉換為乘法運算,避免因數值過大而導致精度損失。
求逆元的方法有多種,包括費馬小定理、擴展歐幾里得算法和線性遞推法等。費馬小定理適用於模數為素數的情況,擴展歐幾里得算法適用於一般情況,而線性遞推法則是一種高效的求逆元方法。