Congruence

Author

Eric W. Weisstein
October 4, 2004

This notebook downloaded from http://mathworld.wolfram.com/notebooks/NumberTheory/Congruence.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/Congruence.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Code

Best but undocumented

MyMod[r_,m_]:=Polynomial[r,m]

Straightforward

SetAttributes[MyMod,Listable];
MyMod[r_Rational,m_Integer]:=Mod[Numerator[r]PowerMod[Denominator[r],-1,m],m]

More kludgy version using Conway and Guy's algorithm

MyMod[r_Rational,m_Integer]:=With[{p=Numerator[r],q=Denominator[r]},Module[{qi=q,pi,prod=1},While[qi>1,pi=Ceiling[m/qi];
prod*=pi;
qi=Mod[qi pi,m];
];
Mod[p prod,m]]
]

Usage

?PowerMod

Examples of Fractional Congruences

MyMod[#,7]&/@{1/2,1/4,2/3,1/6}

Mod[Numerator[#] PowerMod[Denominator[#],-1,7],7]&/@{1/2,1/4,2/3,1/6}

p/q (mod m) for (q,m)≠0

MyMod[2/7,14]

GCD[7,14]

2PowerMod[7,-1,14]