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!

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

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

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.