TOPICS
Search

Fractional Congruence


Congruences apply to fractions (i.e., rational numbers) as well as integers. For example, note that

 2×4=1    3×3=2    6×6=1 (mod 7),
(1)

so

 1/2=4    1/4=2    2/3=3    1/6=6 (mod 7).
(2)

To find p/q (mod m) where (q,m)=1 (i.e., q and m are relatively prime), use an algorithm similar to the greedy algorithm. Let q_0=q and find

 p_0=[m/(q_0)],
(3)

where [x] is the ceiling function, then compute

 q_1=q_0p_0 (mod m).
(4)

Iterate until q_n=1, then

 p/q=pproduct_(i=0)^(n-1)p_i (mod m).
(5)

This method always works for m prime, and sometimes even for m composite. However, for a composite m, the method can fail by reaching 0 (Conway and Guy 1996).

Finding a fractional congruence is equivalent to solving a corresponding linear congruence equation

 ax=b (mod m).
(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 r an explicit rational number.


See also

Congruence, Modular Inverse

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Fractional Congruence." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/FractionalCongruence.html

Subject classifications