Monday, 29 June 2015

discrete mathematics - inverse modulo, modulo arithmetic




I was given following example in the book, however I am not sure how can the result of 27 be calculated. I realise that -13 + 40 gives 27, however how 27 ≡ −13 (mod 40) is the same as 3·(−13) ≡ 1 (mod 40) I dont really follow.



Moreover I don't really see how by Theorem ab≡cd(mod n) 3·27 ≡ 3·(−13) ≡ 1 (mod 40),
I guess 3=a and c=3 by following example, ab≡cd. However it does not make much sense really.



find a linear combination of 3 and 40 that equals 1.



Step1: Divide 40 by 3 to obtain 40=3·13+1.This simples that 1=40−3·13.
Step 2: Divide 3 by 1 to obtain 3 = 3·1 + 0. This implies that gcd(3, 40) = 1.

Step 3: Use the result of step 1 to write



3·(−13) = 1 + (−1)40.



This result implies that −13 is an inverse for 3 modulo 40.
In symbols, 3·(−13) ≡1 (mod 40).
To find a positive inverse, compute 40 − 13. The result is 27, and 27 ≡ −13 (mod 40)
because 27 − (−13) = 40. So, by Theorem ab≡cd(mod n)
3·27 ≡ 3·(−13) ≡ 1 (mod 40),
and thus by the transitive property of congruence modulo n, 27 is a positive integer that is an inverse for 3 modulo 40. ■




Thank you for your help in advance


Answer



Since 40=313+1,
40313=140+133=1



Thus,

1331(mod40)
Hence, -13 is a multiplicative inverse of 3 \pmod{40}. However, so is any integer that is equivalent to -13 \pmod{40}. Those integers have the form -13 + 40k, where k \in \mathbb{Z}. To see this, observe that
(-13 + 40k) \cdot 3 \equiv -13 \cdot 3 + 40 \cdot 3k \equiv -13 \cdot 3 \equiv 1 \pmod{40}
In particular, if k = 1, then
(-13 + 40 \cdot k) \cdot 3 \equiv (-13 + 40) \cdot 3 \equiv 27 \cdot 3 \equiv 1 \pmod{40}
Hence, 27 is an inverse of 3 \pmod{40}. Since 0 \leq 27 < 40, it is the positive inverse we seek.



Check: 27 \cdot 3 = 81 = 2 \cdot 40 + 1 \Rightarrow 27 \cdot 3 \equiv 1 \pmod{40}, so 3^{-1} \equiv 27 \pmod{40}.


No comments:

Post a Comment

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

How to find \lim_{h\rightarrow 0}\frac{\sin(ha)}{h} without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...