Saturday, December 30, 2017

modular arithmetic - Modulus of Fraction




I just want to confirm I am doing this problem correctly.



The problem asks to compute without a calculator:
$$
3 * \frac{2}{5} \pmod 7
$$

The way I am solving the problem:
$$
3 * \frac{2}{5} \bmod 7 \\
3 * 2 * \frac{1}{5} \bmod 7\\

\gcd(5,7) = 1 (\text{inverse exists})
$$

$$
(((3 \bmod 7) * (2 \bmod 7) * (1 \bmod 7)) \bmod 7) \\
(3 * 2 * 1) \bmod 7
$$

$$
6 \bmod 7 = 6
$$




Am I doing this correctly? Just started learning this in class. This is an even number practice problem out the book so I cannot check the answer lol.


Answer



We want to find $(3)(2)(x)\pmod{7}$, where $x$ is the inverse of $5$ modulo $7$, that is, where $5x\pmod 7=1$.



There are general procedures for finding inverses modulo $m$, but $7$ is a very small number, so we can do it efficiently by trial and error. Note that $(5)(3)$ has remainder $1$ on division by $7$. So $x\pmod 7=3$.



Thus we want to compute $(3)(2)(3)\pmod 7$. This is $4$.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...