Fractions in Modular Arithmetic

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$.

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$