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:
325(mod7)
The way I am solving the problem:
325mod
(((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...