Get Mathematica to solve Modular Arithmetic problem [closed]

Question

How would I get Mathematica to solve something like this for $x$?

$4x \equiv 1 \pmod 5$

Answer 1

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