Sunday, November 24, 2019

elementary number theory - Finding modular inverse (wrong approach)




I'm trying to find the modular inverse of 30(mod7)

I have tried using the Euclidean algorithm and it gave me the right answer, which is x6(mod7). However, I tried using another approach that I thought would be simpler, but it resulted in a wrong answer. These were my steps:



Suppose x is the modular inverse of 30 mod 7. 30x1(mod7)


(74+2)x1(mod7)

2x1(mod7)

<- I have a feeling it's the previous line of simplification that's causing the problem.) So the inverse of 2 mod 7 is 4. Thus the resulting answer is x4(mod7), which is wrong. Could anyone point out what is the problem here?


Answer



First, write 30=2(mod7) , and now use the Euclidean algorithm with this, which is way easier.




By the way, the answer indeed is 4 , since 304=120=1+177 , or simpler: 24=1+7


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...