1
$\begingroup$

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

$4x \equiv 1 \pmod 5$

$\endgroup$
  • 3
    $\begingroup$ Solve[4 x == 1, x, Modulus -> 5] or Mod[PowerMod[4, -1, 5] * 1, 5] would be the easiest, but it might be more pedagogically useful for you to figure out how to use ExtendedGCD[] for your problem. $\endgroup$ – J. M.'s technical difficulties Jun 8 '16 at 18:16
  • $\begingroup$ @J.M. Whoa, that's cool. I see what this is doing in Mathematica now after looking up PowerMod, but I'm not entirely sure what's going on mathematically. Mind giving this with an explanation as an answer? $\endgroup$ – Elem-Teach-w-Bach-n-Math-Ed Jun 8 '16 at 18:20
  • $\begingroup$ I can't spend enough time to write a sufficiently expository answer at the moment, but you might try looking up the extended Euclidean algorithm in a number theory textbook, like Rosen's. $\endgroup$ – J. M.'s technical difficulties Jun 8 '16 at 18:22
  • $\begingroup$ @J.M. K, thanks! $\endgroup$ – Elem-Teach-w-Bach-n-Math-Ed Jun 8 '16 at 18:23
4
$\begingroup$

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
| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! I really was unsure of what even to look up to figure this out as I'm new to Mathematica. Apparently tho, this was a poor question as others have voted to close it? I really didn't know this was a modular inverse (nor even what a modular inverse was), and without that knowledge, I'm not sure what else I could have done to find an answer on my own. Could you suggest how I could have found this out without asking a poor question? $\endgroup$ – Elem-Teach-w-Bach-n-Math-Ed Jun 9 '16 at 5:04
  • $\begingroup$ As I already said in a comment, you could've at least tried to look through an elementary number theory textbook before anything else. If you can't or won't read Rosen's, there certainly are others. This is even before trying to use Mathematica (as with a lot of other mathematical problems). Do you at least have access to a decent library? $\endgroup$ – J. M.'s technical difficulties Jun 9 '16 at 5:07
  • $\begingroup$ Yes, I suppose I mean that, before your comment, I didn't know the type of book to look it up in, much less the heading/chapter in the book, and was unsure of anything to Google or search for via the mathematica documentation as well. All I knew was that the problem somehow dealt with modular arithmetic. Guess I'm just not well read enough to ask on this site. $\endgroup$ – Elem-Teach-w-Bach-n-Math-Ed Jun 9 '16 at 5:19
  • $\begingroup$ Thanks again tho for taking the time to put together such a great answer! $\endgroup$ – Elem-Teach-w-Bach-n-Math-Ed Jun 9 '16 at 5:20
  • $\begingroup$ Anyway, consider this a learning experience at the least; considering the common thread of your last few questions, you would be well-served with a read-through of elementary number theory. (FWIW, number theory is far from my expertise, but I know enough to get me into trouble. ;)) $\endgroup$ – J. M.'s technical difficulties Jun 9 '16 at 5:21

Not the answer you're looking for? Browse other questions tagged or ask your own question.