28
$\begingroup$

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?

Thanks in advance!

$\endgroup$

4 Answers 4

36
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – monalisa
    Commented Jul 23, 2018 at 14:04
12
$\begingroup$
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)

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

$\endgroup$
1
  • $\begingroup$ 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 $$ $\endgroup$ Commented Apr 24, 2022 at 4:42
3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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! $\endgroup$
    – Alonso
    Commented Nov 30, 2013 at 9:32
  • $\begingroup$ But it can be suggested that 1/3 * 3= 1. $\endgroup$
    – Alonso
    Commented Nov 30, 2013 at 9:32
  • $\begingroup$ Take the numbers from $0$ to $7$, and multiply them by $3$. Are any of those products equal to $1$ mod $8$? $\endgroup$ Commented Nov 30, 2013 at 9:52
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .