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$5 Answers
$\begingroup$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}$.
$\endgroup$ 1 $\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$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$Calculating modulo 8, we have $\frac{1}{3} = \frac{3}{9} = \frac{3}{1} = 3$.
$\endgroup$ $\begingroup$The definition of $$x\mod y=x-y\left\lfloor \frac xy\right\rfloor, \lfloor x+yi\rfloor=\lfloor x\rfloor +i\lfloor y\rfloor$$
which almost looks like the $y$s can cancel and then the $x$s
Next substitute $\left(\frac13,8\right)$
Therefore: $$\frac13\mod 8=\frac13-8\left\lfloor \frac {\frac13}8\right\rfloor=\frac13-8・0=\frac13$$
In fact:
$$x\mod y=x-y\left\lfloor \frac xy\right\rfloor,\mathop=^{0\le\frac xy<1}x-y ・ 0=x$$
Here are $32$ other closed forms of the Modulus function. Please correct me and give me feedback!
$\endgroup$
