Congruences apply to fractions (i.e., rational numbers) as well as integers. For example, note that
(1)
|
so
(2)
|
To find (mod ) where (i.e., and are relatively prime), use an algorithm similar to the greedy algorithm. Let and find
(3)
|
where is the ceiling function, then compute
(4)
|
Iterate until , then
(5)
|
This method always works for prime, and sometimes even for composite. However, for a composite , the method can fail by reaching 0 (Conway and Guy 1996).
Finding a fractional congruence is equivalent to solving a corresponding linear congruence equation
(6)
|
A fractional congruence of a unit fraction is known as a modular inverse. A fractional congruence can be found in the Wolfram Language using the following function:
FractionalMod[r_Rational, m_Integer] := Mod[ Numerator[r]PowerMod[Denominator[r], -1, m], m]
or using the undocumented syntax PolynomialMod[r, m] for an explicit rational number.