Fractions in Modular Arithmetic 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? 
 A: 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$
A: 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$.
A: 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$. 
