Tuesday, May 10, 2016

elementary number theory - Find the Inverse Modulus using Euclid's algorithm

I asked this before, but unfortunately, I didnt know the methods, nor was the questions phrased properly.



Find the inverse of $4258 \pmod{147}$ Using Euclidean Extended Algorithm.



Begin By Stating the remainders (Euclid's Algorithm):



$4258 = 28(147) + 142$



$147 = 1(142) + 5$




$142 = 28(5) + 2$



$5 = 2(2) + 1$



Then BACK substitution starting with $1$:



$1 = 5 - 2\cdot 2$



$1 = 5 - 2\cdot \bigg(142 - 28(5)\bigg ) = -279 + 2\cdot 28(5)$




$1 = -279 + 2\cdot 28\bigg( 147 - 142 \bigg)$



$1 = -279 + 56 \cdot \bigg( 147 - 4258 + 28(147) \bigg)$



But how would I proceed?

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...