# Fractions in Modular Arithmetic [duplicate]

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?

• $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". – user14972 Sep 5 '16 at 0:34
• Hurkyl. Well, except what does 2/3 mod 5 "mean", if anything if our terms must be in Z_5? – fleablood Sep 5 '16 at 0:42
• 3x = 5k +2 => x =k + 2 (k+1)/3. Let 3|k+1 by letting k =2 and you get x=4. – fleablood Sep 5 '16 at 0:58

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\cdot 3^{-1}\equiv x\mod 5$$. In this case, $$3^{-1}\equiv 2\mod 5$$, so you would have $$2\cdot 2\equiv 4\mod5$$. The inverse of a number $$a$$ in modular arithmetic is the number $$a^{-1}$$ such that $$a\cdot a^{-1}\equiv 1\mod n$$.

• And how does one find the inverse? And does the inverse always exist? – fleablood Sep 5 '16 at 3:12
• The inverse only exists when $a$ and $n$ are coprime. – AlgorithmsX Sep 5 '16 at 3:16
• @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$. – Peter LeFanu Lumsdaine Sep 5 '16 at 7:21
• I was asking rhetorically. It seemed to me these issues are at the heart of the OP and need to be addressed. – fleablood Sep 5 '16 at 18:11

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 + 17c \equiv -1 \mod 3c \equiv - 1 \mod 33b = -7 + 1; b=-27a = 10(-2) -1; a = -310w = 17(-3) +1; w = -517z = 27(-5) -1=-136; z = -827y = 71(-8) + 1=-68; y = -21$So$y=27^{-1}=50x \equiv 35(-21) \mod 71 \equiv 46 \mod 71$And lets check$27*46 = 1242 \equiv 35 \mod 71$• 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. – PM 2Ring Sep 5 '16 at 8:46 • 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. – fleablood Sep 5 '16 at 17:56 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\$.