How would I get Mathematica to solve something like this for $x$?
$4x \equiv 1 \pmod 5$
Mathematica Stack Exchange is a question and answer site for users of Wolfram Mathematica. It only takes a minute to sign up.
Sign up to join this communityHow would I get Mathematica to solve something like this for $x$?
$4x \equiv 1 \pmod 5$
The lazy user just looking to solve equations can simply use Solve[4 x == 1, x, Modulus -> 5]
and be done with it. However, one should recognize that this is in fact a modular inversion problem, and that there are specialized number-theoretic tools for dealing with this directly. All of this hinges on Bézout's identity, which says that for two nonzero integers $m$ and $n$, one can always find integers $p$ and $q$ such that $$pm+qn=\gcd(m,n)$$ The procedure for finding $p$ and $q$ is an extension of the usual Euclidean algorithm for the greatest common divisor, which is built-in as ExtendedGCD[]
.
What all this has to do with the modular inverse is that $4x \equiv 1 \pmod 5$ can be recast into the Bézout form as $4x-5q=1$, where we already have $\gcd(4,5)=1$ (otherwise, there is no modular inverse at all!). Thus,
{g, {x, q}} = ExtendedGCD[4, 5]
{1, {-1, 1}}
Note that $x=-1$ does solve the problem, since $-4 \equiv 1 \pmod 5$, but one often wants to get the least positive result, thus necessitating another operation:
x = Mod[x, 5]
4
All this is more or less done within the built-in function PowerMod[]
, which is used for directly generating the modular inverse:
PowerMod[4, -1, 5]
4
Solve[4 x == 1, x, Modulus -> 5]
orMod[PowerMod[4, -1, 5] * 1, 5]
would be the easiest, but it might be more pedagogically useful for you to figure out how to useExtendedGCD[]
for your problem. $\endgroup$ – J. M.'s ennui♦ Jun 8 '16 at 18:16