# Finding modular of a fraction

In the context of cryptography, I need to find the private key of a message and I need to use modular arithmetic. I understand how modular arithmetic using a clock with whole numbers. But I get really stuck when I get to fractions, for example:

1/3 mod 8

How do I find a modular of a fraction? Is there a method for finding this?

Writing fractions like $$\frac{1}{3} \pmod{8}$$ is the same as writing $$3^{-1} \pmod{8}$$ which is the inverse of $$3$$ modulo $$8$$.

In other words, when you write $$\frac{a}{b} \pmod{n}$$ you're referring to a number $$k$$ such that $$bk \equiv a \pmod {n}$$ but you should pay attention that this fraction is defined if and only if $$\gcd(b,n)=1$$. In other words, the denominator must be relatively prime to the modulus.

To find what number modulo $$n$$ this fraction represents, you need to evaluate $$b^{-1}$$. You can do that by using the Euclidean algorithm to solve the Bézout equation $$bx + ny = 1$$. The $$x$$ in this equation will give you $$b^{-1}$$. If you know the factorization of $$n$$ you can also use Euler's totient function by noting that $$b^{-1} \equiv b^{\varphi(n)-1} \pmod{n}$$. After you know what $$b^{-1}$$ is you will see that $$k \equiv a \dot b^{-1} \pmod {n}$$.

• One of the best way to explain the concept. I loved your way of explaining, I was searching for something related to this and got this answer. Thanks a lot. Commented Jul 23, 2018 at 14:04
n  ≡ (1/3)  (mod 8)
3n ≡ 1      (mod 8)
try n= 1,2,3
when n=1, 3 mod 8 is 3
when n=2, 6 mod 8 is 6
when n=3, 9 mod 8 is 1, (this is our answer)


This method can be used for any fractions Another example: 2/5 mod 3

 5n mod 3 = 2
try group of {0, 1, 2} which satisfy the above,


result n=1

• Note: (1) If $0\leq a < k$ and $a \equiv b ~~(\text{mod }k)$ then $a = b~\text{mod }k$ (i.e., the remainder of $b$ when divided by $k$). | (2) $a \equiv b ~~(\text{mod }k) \iff b \equiv a ~~(\text{mod }k)$. So: $$\frac{2}{5}~~(\text{mod }3) \iff 5n \equiv 2~~(\text{mod }3)\iff 2\equiv 5n~~(\text{mod }3) \implies 2 = 5n ~\text{mod }3$$ Commented Apr 24, 2022 at 4:42

The important property of $1/3$ is that $1/3 \cdot 3 = 1$. So, what number, when multiplied by $3$, is $1$ mod $8$?

Showing when $x^{-1} \pmod n$ exists and that it is unique is not too terrible either

EDIT: I didn't see "finding it". Check out the Extended Euclidian algorithm.

• is the number 1? Because 1 mod 8 = 1 as 1 < 8. But I don't get how what number, when multiplied by 3 corresponds to 1. as 1x3 =3. Thanks! Commented Nov 30, 2013 at 9:32
• But it can be suggested that 1/3 * 3= 1. Commented Nov 30, 2013 at 9:32
• Take the numbers from $0$ to $7$, and multiply them by $3$. Are any of those products equal to $1$ mod $8$? Commented Nov 30, 2013 at 9:52

Calculating modulo 8, we have $\frac{1}{3} = \frac{3}{9} = \frac{3}{1} = 3$.