# Finding modular of a fraction

Im really into cryptography and to find the private key of a message 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?

Thanks in advance!

## 4 Answers

Writing fractions like $\frac{1}{3} \pmod{8}$ is the same as writing $3^{-1}$ 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. – monalisa Jul 23 at 14:04

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! – Alonso Nov 30 '13 at 9:32
• But it can be suggested that 1/3 * 3= 1. – Alonso Nov 30 '13 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$? – Henry Swanson Nov 30 '13 at 9:52
n ≡ (1/3)  (mod 8)
3n   ≡ 1  (mod 8)
try n= 1,2,3
when n=1 3 mod 8 is zero
when n=2, 6 mod 8 is zero
when n=3, 9 mod 8 is 1, (this is our answer)


So answer is 3

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

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