分数同余

同余也适用于分数（即有理数）以及整数。例如，注意

(1)

所以

(2)

要找到 (mod )，其中 （即， 和 是互质），使用类似于贪婪算法的算法。令 并找到

(3)

其中 是向上取整函数，然后计算

(4)

迭代直到 ，然后

(5)

此方法总是适用于 素数的情况，有时甚至适用于 合数的情况。但是，对于合数 ，此方法可能会失败，最终达到 0 (Conway and Guy 1996)。

找到分数同余等价于解相应的线性同余方程

(6)

单位分数的分数同余被称为模逆元。可以在 Wolfram 语言中使用以下函数找到分数同余

  FractionalMod[r_Rational, m_Integer] := Mod[
    Numerator[r] PowerMod[Denominator[r], -1, m],
    m
  ]

或使用未公开的语法PolynomialMod[r, m]，其中 r 是显式有理数。