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 = 3 \cdot 13 + 1$,
\begin{align*}
40 - 3 \cdot 13 & = 1\\
40 + -13 \cdot 3 & = 1\\
\end{align*}



Thus,

$$-13 \cdot 3 \equiv 1 \pmod{40}$$
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}...