# 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
Commented Sep 5, 2016 at 0:34
• Hurkyl. Well, except what does 2/3 mod 5 "mean", if anything if our terms must be in Z_5? Commented Sep 5, 2016 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. Commented Sep 5, 2016 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? Commented Sep 5, 2016 at 3:12
• The inverse only exists when $a$ and $n$ are coprime. Commented Sep 5, 2016 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$. Commented Sep 5, 2016 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. Commented Sep 5, 2016 at 18:11
• @joseville In a finite field, there is no difference between 2 and 5. We treat any two numbers whose difference is in $3 \mathbb{Z}$ as the same object. If you're interested in these topics, you should check out this series: cantorsparadise.com/… or look up the term "Quotient group". Commented Nov 16, 2022 at 10:32

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. Commented Sep 5, 2016 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. Commented Sep 5, 2016 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\$.