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

4x≡1(mod5)4x \equiv 1 \pmod 5

=================

=================

1 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 mm and nn, one can always find integers pp and qq such that pm+qn=\gcd(m,n)pm+qn=\gcd(m,n) The procedure for finding pp and qq 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 54x \equiv 1 \pmod 5 can be recast into the BÃ©zout form as 4x-5q=14x-5q=1, where we already have \gcd(4,5)=1\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=-1x=-1 does solve the problem, since -4 \equiv 1 \pmod 5-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

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?

– Elem-Teach-w-Bach-n-Math-Ed

Jun 9 at 5:04

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?

– J. M.♦

Jun 9 at 5:07

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.

– Elem-Teach-w-Bach-n-Math-Ed

Jun 9 at 5:19

Thanks again tho for taking the time to put together such a great answer!

– Elem-Teach-w-Bach-n-Math-Ed

Jun 9 at 5:20

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. ;))

– J. M.♦

Jun 9 at 5:21