How would I get Mathematica to solve something like this for $x$?
$4x \equiv 1 \pmod 5$
1
$\begingroup$
$\endgroup$
asked Jun 8 '16 at 18:12
closed as off-topic by MarcoB, Artes, user9660, m_goldberg, bbgodfrey Jun 9 '16 at 2:49
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question arises due to a simple mistake such as a trivial syntax error, incorrect capitalization, spelling mistake, or other typographical error and is unlikely to help any future visitors, or else it is easily found in the documentation." – MarcoB, Artes, Community, m_goldberg, bbgodfrey
4
$\begingroup$
$\endgroup$
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
answered Jun 9 '16 at 0:38
-
$\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. is away♦ 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. is away♦ Jun 9 '16 at 5:21
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. is away♦ Jun 8 '16 at 18:16