Fractional Congruence

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.