5
$\begingroup$

This question already has an answer here:

Suppose we have $$\frac{2}{3} \equiv x \bmod 5$$

I understand that the first step that needs to be made is: $$2 \equiv 3x \bmod 5$$

But from there I'm having a hard time understanding the logic of how to solve for $x$. Obviously, with simple numbers like this example, the answer is $4$, but how can I abstract the process to solve for $x$ when the numbers become very large?

$\endgroup$

marked as duplicate by Bill Dubuque modular-arithmetic Nov 14 at 1:51

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ $x \equiv 2/3$ is already solved for $x$. I think the question you should be asking is not about doing algebra, but about doing arithmetic. Keywords: "modular division" and "modular inverse". $\endgroup$ – user14972 Sep 5 '16 at 0:34
  • $\begingroup$ Hurkyl. Well, except what does 2/3 mod 5 "mean", if anything if our terms must be in Z_5? $\endgroup$ – fleablood Sep 5 '16 at 0:42
  • $\begingroup$ 3x = 5k +2 => x =k + 2 (k+1)/3. Let 3|k+1 by letting k =2 and you get x=4. $\endgroup$ – fleablood Sep 5 '16 at 0:58
9
$\begingroup$

Modulo arithmetic generally deals with integers, not fractions. Instead of division, you multiply by the inverse. For instance, you would not have $\frac2 3\equiv x\mod 5$, you would have $2*3^{-1}\equiv x\mod 5$. In this case, $3^{-1}\equiv 2\mod 5$, so you would have $2*2\equiv 4\mod5$. The inverse of a number $a$ in modular arithmetic is the number $a^{-1}$ such that $a*a^{-1}\equiv 1\mod n$.

$\endgroup$
  • 1
    $\begingroup$ And how does one find the inverse? And does the inverse always exist? $\endgroup$ – fleablood Sep 5 '16 at 3:12
  • 1
    $\begingroup$ The inverse only exists when $a$ and $n$ are coprime. $\endgroup$ – AlgorithmsX Sep 5 '16 at 3:16
  • $\begingroup$ @fleablood: finding the inverse for $x$ mod $n$ amounts (by definition) to finding some integers $y$, $k$ such that $xy = kn + 1$ — or, rearranged, $xy - kn = 1$. (So $y$ is then them multiplicative inverse.) This can be found by the extended Euclid’s algorithm, which simultaneously computes the gcd of $x$ and $n$ (hence works out whether they’re coprime), and if they’re coprime, finds suitable $y$ and $k$. $\endgroup$ – Peter LeFanu Lumsdaine Sep 5 '16 at 7:21
  • $\begingroup$ I was asking rhetorically. It seemed to me these issues are at the heart of the OP and need to be addressed. $\endgroup$ – fleablood Sep 5 '16 at 18:11
3
$\begingroup$

First it's important to know if anyone does use a statement $\frac 23 \equiv x \mod 5$ it is only notation for the solution (if any) to $2 \equiv 3x \mod 5$ and has nothing to do with the rational number $\frac 23$.

Second $ax \equiv b \mod N$ will not have any solutions unless $\gcd(a,N)|b$. Which means either $N$ and $a$ are coprime or $\frac ab$ was not in lowest terms.

If $ax \equiv b \mod N $ then $a/\gcd (a,N)x \equiv b/\gcd (a,N) \mod N/\gcd (a,N) $

So suffices to assume $N$ and $a$ are coprime:

$ay \equiv 1 \mod N$ that will suffice as $x \equiv ab \mod N$ will solve our original equation. We call $y$ so that $ay \equiv \mod N$ $a^{-1}$ and it only exists if $N$ and $a$ are coprime.

First thing to try is Fermats Little Theorem .

$a^{\phi (N)}\equiv 1 \mod N $ so $a^{-1}\equiv a^{\phi (N)-1}\mod N $.

But if that isn't practical....

$ay = 1 \mod N$

$ay = wN + 1$

$wN = ay -1$

$wN \equiv -1 \mod a$

Repeat to try to solve for $w$.

So for example:

$27x \equiv 35 \mod 71; x = 35y \mod 71$

$27y \equiv 1 \mod 71; 27y = 71z + 1$

By Fermats Little Theorem $27^{70} = 1 \mod 71$ so $y \equiv 27^{69}$ but there's no way we are doing that.

$71z \equiv -1 \mod 27$

$17z \equiv -1 \mod 27; 17z = 27w -1$

$27w \equiv 1 \mod 17$

$10w \equiv 1 \mod 17; 10w = 17a +1$

$17a \equiv -1 \mod 10$

$7a \equiv -1 \mod 10; 7a = 10b -1$

$10b \equiv 1 \mod 7$

$3b \equiv 1 \mod 7; $3b =7c + 1$

$7c \equiv -1 \mod 3$

$c \equiv - 1 \mod 3$

$3b = -7 + 1; b=-2$

$7a = 10(-2) -1; a = -3$

$10w = 17(-3) +1; w = -5$

$17z = 27(-5) -1=-136; z = -8$

$27y = 71(-8) + 1=-68; y = -21$

So $y=27^{-1}=50$

$x \equiv 35(-21) \mod 71 \equiv 46 \mod 71$

And lets check $27*46 = 1242 \equiv 35 \mod 71$

$\endgroup$
  • $\begingroup$ Strictly speaking, Fermat's Little Theorem only applies if the modulus is prime, for the general case we want Euler's theorem, aka the Fermat–Euler theorem or Euler's totient theorem. $\endgroup$ – PM 2Ring Sep 5 '16 at 8:46
  • $\begingroup$ I always get the names of those two mixed up. I meant, and did quote it as, the Euler's totient theorem. Thanks for the correction. $\endgroup$ – fleablood Sep 5 '16 at 17:56
1
$\begingroup$

If $a$ and $N$ are coprime, then (at least in $\mathbb Z$ and other rings in which division with remainder holds), one can use Euclide's algorithm to fingd numbers $y,b$ such that $a\;y + N\;b =1$, so $a\;y \equiv 1 \bmod N$.

$\endgroup$

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